我要招人

去企业版

首页 > 试题广场 >

已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个

[单选题]

已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是。

```
39
```
```
52
```
```
111
```
```
119
```

查看正确选项

Sc0tt

一棵完全二叉树的第6层有8个叶节点，最多的情况对应的是这8个叶节点在最右边，又因为第6层总共有2^5=32个节点，因此还有32-8=24个非叶节点，这些非叶节点都对应着两个叶节点，因此下一层即第7层还有48个叶节点，所以最多有2^6-1+48=111个节点。

发表于 2018-05-12 17:06:53 回复(0)

喵大人喵喵喵

完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7 ，显然树高为 7 时结点更多。若第 6 层上有 8 个叶结点，则前六层为满二叉树，而第 7 层缺失了 8× 2= 16 个叶结点，故完全二叉树的结点个数最多为 (2⁷ - 1) - 16=111 个结点。

发表于 2017-05-17 01:53:00 回复(3)

沫遥baby

这道题问的是最多的完全二叉树的节点个数

1 .如果前六层是满二叉树，那么第6层的节点有2⁵=32个，度为2的节点有32-8=24个，第7层的叶子节点为24*2=48个，总节点数=48+2⁶-1=111个

2.如果前五层是满二叉树，那么第6层的叶子节点为8个，总节点数为2⁵-1+8=39个

综上最少是39个最多是111个

编辑于 2017-09-27 17:04:20 回复(0)

sunlight_run

第6层有8节点，就是第七层少了16个叶节点，当然共有7层时节点数最多，所以共有(2^7-1)-16=111

发表于 2017-06-26 20:21:50 回复(0)

Mono_Chrome

注意不要想当然地认为第六层就是这棵树的最后一层。

发表于 2017-12-29 15:26:40 回复(0)

牛客159094368号

叶子节点:"树中最底段的节点，叶子节点没有子节点。"

若第六层的八个叶子节点在最前面

0 RO

1 L1 R1

.....................

6 L1 R2 .... L5 R6

此时获取到的节点是最少的:2^5 - 1 + 8

若第六层的八个叶子节点在最后面

0 RO

1 L1 R1

.....................

6 .......... L24 R25 .... L31 R32

7 L1 R2 .......... L111 R112 后16个为空

此时获取到的节点是最多的:2^7 - 1 - 8 × 2

编辑于 2022-04-30 16:50:56 回复(0)

TowardHope

第 6 层（设根为第 1 层）有 8 个叶结点，本题关键就是，叶节点可能在最后一层，也可能在倒数第二层。正如完全二叉树的定义！

发表于 2018-03-15 19:43:24 回复(0)

提交观点

问题信息

树

上传者：喵大人喵喵喵

难度：

7条回答 156收藏 25587浏览

已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个

问题信息

热门推荐

相关试题