我要招人

去企业版

首页 > 试题广场 >

224个叶子节点的完全二叉树,最多有几个结点（）

[单选题]

224个叶子节点的完全二叉树, 最多有几个结点（）

```
447
```
```
448
```
```
449
```
```
450
```

查看正确选项

雁过无痕2019

二叉树具有性质：

1、度为0的结点个数=度为2的结点个数+1，即n0=n2+1（其中n0表示度为0的结点个数，n2表示度为2的结点个数）。注：二叉树的度代表某个结点的孩子或者说直接后继的个数。

2、完全二叉树中度为1的结点个数要么0个，要么1个。

3、二叉树结点个数n=n0+n1+n2

综合性质，结合题目有 n0=224，故224=n2+1，得n2=224-1=223。

当为度0的结点存在时，结点总数为n=n0+n1+n2=224+0+223=447。

当为度1的结点存在时，结点总数为n=n0+n1+n2=224+1+223=448。

故最多为448个，选B

发表于 2020-06-02 08:51:15 回复(0)

邢哈哈_

刚开始想错了，其实这个题还有一种比较麻烦一些的做法，利用满二叉树的性质，每层有2的n次方-1个结点，第9层则为256个叶子，比224大，因此需要减。第9层减2个，第8层多1个，最终凑成224需要第9层减64个，剩192个，前8层共有2的8次方减1，也就是255个，加起来为447个，还可以再加一个叶子，第8层则少一个叶子，答案为448.

发表于 2020-07-22 10:30:48 回复(0)

克己守心

2、完全二叉树中度为1的结点个数要么0个，要么1个。

3、二叉树结点个数n=n0+n1+n2

综合性质，结合题目有 n0=224，故224=n2+1，得n2=224-1=223。

当为度1的结点不存在时，结点总数为n=n0+n1+n2=224+0+223=447。

当为度1的结点存在时，结点总数为n=n0+n1+n2=224+1+223=448。

故最多为448个，选B

发表于 2020-06-28 11:59:41 回复(0)

悦宝知恩offer我都要

根据完全二叉树特性及叶子节点数推断：该树共有9层，若为满二叉树，则最后一层为256个节点，目前叶子节点为224，所以可以知道第8层和第9层均有叶子节点。设最后一层叶子节点数x，倒数第二层叶子节点数y，那么(x + y) = 224, 满二叉树的话每个y都有两个子孩子，(x + 2y) = 256。求得y = 32，x = 192。前八层肯定为满二叉树，

则共有2的8次方减1，255个。所以192 + 255 = 447，但是考虑到求最多节点数，第八层的叶子节点可以转化为一个度为1的节点，使得总节点数再加1，叶子结点数不变，所以答案为448。

发表于 2020-12-24 14:07:15 回复(0)

Louis.Liu1

当为度0的节点存在节点总数 n=n0+n1+n2=4+0+3=7

当为度1的节点存在节点总数 n=n0+n1+n2=4+1+3=8

我怎么看不出有8个节点啊

发表于 2020-12-08 11:04:07 回复(0)

提交观点

问题信息

C++工程师测试开发工程师小红书 2020 Java工程师

上传者：小小

难度：

5条回答 128收藏 1944浏览

224个叶子节点的完全二叉树,最多有几个结点（）

问题信息

热门推荐

相关试题