我要招人

去企业版

首页 > 试题广场 >

一颗完全二叉树第六层有8个叶结点（根为第一层），则结点个数最

[单选题]

一颗完全二叉树第六层有8个叶结点（根为第一层），则结点个数最多有（）个。

```
39
```
```
72
```
```
104
```
```
111
```

推荐

牛客-007

答案：D

二叉树第k层最多有2的(k-1)次方个节点

第六层最多有32个节点

第五层最多有16个节点

第四层最多有8个节点

第三层最多有4个节点

第二层最多有2个节点

第一层最多有1个节点

完全二叉树的叶节点只可能出现在后两层

如果完全二叉树有6层，则前5层是满二叉树，总节点数目为16+8+4+2+1+8=39

如果完全二叉树有7层，则前6层是满二叉树，

前六层总节点数目为32+16+8+4+2+1=63

第六层有8个叶子节点，则有32-8=24个非叶子节点

第七层最多有24*2个叶子节点

总节点数目为63+24*2=111

编辑于 2015-01-14 11:01:37 回复(2)

牛客-liwei4939

完全二叉树第六层8个叶结点，则第七层缺少16个结点不满，结点个数等于2⁷-1-16=111

发表于 2017-04-22 21:18:52 回复(2)

C.C.

答案是111

最多的情况是

层:节点数

1 : 1

2 : 2

3 : 4

4 : 8

5 : 16

6 : 32

7 : 48

1 + 2 + 3 + 4 + 8 + 16 + 32 + 48 = 111

第七层的节点是第六层的左边24个的子节点（因为最右边8个是叶子节点），所以是48个

发表于 2015-01-13 17:23:54 回复(0)

王俊超

答案是：111个

第6层如果是满的有2^（6-1）=32个结点，现在第6层有8个叶结点，则第6层是倒数第二层，第6层中前（32-8）=24个结点点有叶结点，并且前23个都有2个叶结点，第24个至少有一个左子结点。

所以第七层最多有24*2=48个结点，前6层是满二叉树，所以共有2^6-1=63个结点

一共加起来是48+63=111个结点。

发表于 2015-08-03 16:47:52 回复(1)

邓丽璇

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

发表于 2017-09-03 10:43:26 回复(0)

看我滑雪呀

题目要求节点个数最多，所以第六层的8个叶节点在第六层的右边，因为是完全二叉树，所以第六层左边的24个节点（32-8）都要存在且都有左右2个子树。

所以总的节点个数=前6层节点都满+第七层的节点个数（24*2）=63+48=112

发表于 2020-10-12 10:46:43 回复(0)

牛客9148490号

竟然以为一共就有6层。。。

发表于 2017-08-16 22:06:03 回复(0)

牛客105234193号

“第六层有8个叶结点”==“第六层的节点共有8个下属叶节点”

“第六层有8个叶结点”!=“第六层的节点为8个叶节点”😅

发表于 2022-08-16 19:15:57 回复(1)

逆袭的黑马

没有考虑树可以是七层的情况，唉

发表于 2020-12-27 17:42:20 回复(0)

RMrrrrrr

不要惯性思维以为这道题只有6层，其实有7层，只是说了第6层只有8个叶结点而已。

发表于 2016-05-14 23:46:47 回复(0)

dirty-life

本题的关键是“至多”有多少个节点，题中说明第6层有8个叶节点，有两种可能，第一：第6层就是最深一层，由完全二叉树的定义可知前五层则必须是满树，此时一共有2^5+8 = 32 + 8 = 40个叶节点；第二：第6层是倒数第二层，树一共有7层，第6层最多有2^5个节点，有8个叶节点，则有24个非叶节点，每一个非叶节点之多可以有两个子节点，则此时树中最多有2^6-1+24*2 = 111个节点，如果不是考虑最多的话，则树中节点的可能个数为40 110 111

发表于 2015-08-26 20:33:30 回复(1)

已注销

最多节点七层：1+2+4+8+16+32+(32-8)x2=111

最少节点六层：1+2+4+8+16+8=39

发表于 2023-09-20 09:52:50 回复(0)

牛客574860995号

他这题说的是第6层有8个叶子结点最多的情况那也就是一共可以有7层那就用2^7次方-1求出结点最多的情况然后第6层有8个叶子结点所以第7层就要少掉16个结点就是127-16=111

发表于 2023-03-14 14:15:18 回复(0)

不做人了

这8个节点是叶子节点剩余都不是叶子节点

编辑于 2020-06-05 11:09:08 回复(0)

在看机会的00后

注意是8个叶节点，不是只有8个节点。127-8*2

发表于 2020-05-14 15:09:11 回复(0)

陨陌555

老帖们，是不是刚开始一算2**5-1+8=39，正好有，选上，看清“最多”，那就存在另外一种可能，第六层不是最后一层，只是

有8个叶子节点而已，完全二叉树的叶子节点的差值不能超过1，那也就存在第七层喽。

前六层有2**6-1=63，第六层有2**(6-1)=35个节点，其中8个叶子节点，剩余24个非叶子节点，因为要最多，那么这24都有左右儿子

不好了吗，所以第七层就有24*2=48个，加上前六层的48+63==111。

发表于 2019-03-25 17:32:11 回复(0)

人和动物

第六层有结点，那么最多就是七层。

前6层总结点数=2^6-1=63

第7层本来可以有2^(7-1)=64个结点，但是第6层有8个结点，那么第7层结点数=64-8*2=48

63+48=111

发表于 2018-12-07 20:04:49 回复(0)

laymond

完全二叉树的，也叶子结点可以在最后一层也可以在倒数第二层呀！

发表于 2018-05-13 10:27:57 回复(0)

郎瑶

最多为7层。第六层节点数目若为满是2^5=32个，其中叶子节点8个。非叶子32-8=24个第七层叶子节点数目是2*24=48

1 2 4 8 16 32 48 一共111个

发表于 2018-03-05 20:53:18 回复(1)

Fengzhi志

该完全二叉树至少有39个节点，至多有111个结点。

发表于 2018-01-28 16:04:26 回复(0)

SSSuper是纸兔斯基

叶子节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树叫完全二叉树。因此，根据题意我们可知，这个树要不有6层，第五层和第六层节点不满，要不就有7层，第六层和第七层不满，这道题主要是为了求最多的节点数，因此这个树有7层。第六层满节点的话为32个节点，有8个叶子节点，那么非叶子节点就有24个，24*2=48即为第七层的节点数，总的就是48+2*k-1=111

发表于 2017-09-19 17:08:41 回复(0)

提交观点

问题信息

树

来自：4399游戏2015校...

上传者：小牧魔法袋

难度：

34条回答 822收藏 26010浏览

一颗完全二叉树第六层有8个叶结点（根为第一层），则结点个数最

问题信息

热门推荐

相关试题