我要招人

去企业版

首页 > 试题广场 >

若一棵完全二叉树有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)

提交观点

问题信息

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

上传者：小小

难度：

4条回答 25收藏 2625浏览

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

使用三元一次方程：

问题信息

热门推荐

相关试题