我要招人

去企业版

首页 > 试题广场 >

若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是

[单选题]

若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是（）。

```
257
```
```
258
```
```
384
```
```
385
```

查看正确选项

不会真有人不僵硬吧

使用三元一次方程：

设：
有两个孩子的节点个数为a；
有一个孩子的节点个数为b；
没有孩子（即叶子结点）的节点个数为c；
由条件知：
1. a + b + c = 768；
2. 由完全二叉树定义，可以知道只有一个孩子的节点b个数为0或1，由于总节点个数为768，所以可以知道b=1；
3. 除了叶子结点，所有节点的个数都对应一条边的个数，而边的个数，又是 两个孩子的节点个数×2+一个孩子的节点个数×1，即为 768-1 = a * 2 + b;

所以：

768-1 = a * 2 + b;
a + b + c = 768；
b = 1;

得到 c = 384。

编辑于 2021-03-04 10:46:41 回复(0)

billows2929

最后一层的叶子节点数：768 - 511 = 257

倒数第二层的叶子节点数：256 - (257+1) / 2 = 127

总共叶子节点个数：257 + 127 = 384

发表于 2021-04-04 12:40:17 回复(0)

卖萌小伙张三

二叉树的节点个数与层数 $n$ 的关系为： $2^{n}-1$ ，本题中树的节点个数为768个，易知树的层数 $n=10$ 。

而二叉树某一层的节点个数为 $2^{n-1}$ ，所以第9层的节点个数为 $2^{9-1}=256$ ，前9层的节点个数为 $2^{9}-1=511$ ，则第10层有 $768-511=257$ 个节点，则易知这257个节点全部是叶子节点，接下来看看第9层的叶子节点的个数，因为第10层有257个节点，又因为这棵树是完全二叉树，所以这257个节点的父亲节点除了最右边的那个之外，其余的都有两个孩子，所以第9层不是叶子节点的节点个数为 $256\div2+1=129$ 个，则第9层的叶子节点个数为 $256-129=127$ ，所以第9层与第10层的叶子节点个数之和 $127+257=384$ ，则整个二叉树的叶子节点个数就是 $384$

发表于 2021-03-09 14:39:45 回复(0)

Eclipse0827

倒数第二层最后一个有子节点的节点编号=768/2=384

也就是说，编号为385~768的节点都是叶子节点

所以总叶子节点个数=768-384=384

编辑于 2021-03-09 18:43:40 回复(0)

一笑而过2222

在完全二叉树中，有特定的节点关系。度为 2 的节点个数等于度为 0（叶子节点）的个数减 1 。设叶子节点个数为 n0 ，度为 2 的节点个数为 n2 ，那么 n2 = n0 - 1 。同时，在二叉树中，节点总数 n = n0 + n1 + n2 ，这里 n1 是度为 1 的节点个数，并且完全二叉树中度为 1 的节点个数要么是 0 ，要么是 1 。已知节点总数 n = 768 。当 n1 = 0 时，由 n = n0 + n2 可得 n = n0 + (n0 - 1) = 2n0 - 1 ，也就是 768 = 2n0 - 1 ，解得 n0 = 384.5 ，但节点个数不能是小数，所以 n1 不等于 0 。当 n1 = 1 时，由 n = n0 + n2 + 1 可得 n = n0 + (n0 - 1) + 1 = 2n0 ，即 768 = 2n0 ，解得 n0 = 384 。所以，该二叉树中叶结点的个数是 384 ，答案选 C 。【4.2.6 选择题[14] 若一棵完全二叉树有-哔哩哔哩】 https://b23.tv/w004ZeL

编辑于 2024-11-09 13:40:50 回复(0)

提交观点

问题信息

C++工程师 golang工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师游戏研发工程师 2021 数据库工程师远景测试开发工程师大数据开发工程师 Java工程师

上传者：小小

难度：

5条回答 25收藏 3089浏览

若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是

使用三元一次方程：

问题信息

热门推荐

相关试题