我要招人

去企业版

首页 > 试题广场 >

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

[单选题]

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

结点个数最多是 ( )。

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

查看答案及解析

阿狸不是猫

如果第六层是满的话，那么第6层将会有32个节点，题目说只有8个叶节点，那只有两种情况：

1.6层只有8个节点，都是叶节点

2.6层节点满了，但有8个节点没有子节点，只能作为叶节点。

由于题目求更多：所以考虑第2钟情况：

这时候前6层节点数为32+16+...+1 =63

第7层节点数：（32-8）*2=48 ——第6层节点数共32个，减去8个叶节点数，每个再带有两个子节点，相加——111

发表于 2017-05-31 23:43:16 回复(3)

咕噜1101

题目说第 6 层有8个叶节点，存在两种情况：

（1）树总共6层，且6层只有8个节点，都是叶节点

（2）树有7层，但是第6层有8个节点没有子节点，只能作为叶节点。

对于（1），n0=8，则n2=n0-1=7,n1=2^1+2^2+2^3+2^4=30,则n=n0+1+n2=45

对于（2），这时候，前6层节点数为32+16+...+1 =63，第7层节点数：（32-8）*2=48 (第6层节点数共32个，减去8个叶节点数，每个再带有两个子节点),，则n=63+48=111

求最多，则为情况（2），最多111个

编辑于 2019-02-26 21:28:01 回复(0)

RenaissanceWhy

完全二叉树的结点个数最多

第1层:1

第2层:2

第3层:4

第4层:8

第5层:16

第6层:32（ 8 个叶结点+24个度为2的节点）

第7层:48 （ 24个度为2的节点的子节点）

相加为111个

编辑于 2017-05-18 18:22:43 回复(0)

捂耳听风

需要认真考虑的一道题。第六层有八个叶节点，其实有两种情况：

1、第六层只有六个节点，且为叶节点（常想到的）——节点最少情况；

2、第六层满节点，但是其中的八个节点没有孩子节点，因此其也是叶节点（不易想到）——节点最多情况；

本题正是考察第二种情况。

首先，前六层满节点，那么节点个数为：2⁶-1=63

其次，第六层有2^6-1 =32个节点，其中有8个没有孩子节点，说明第七层有（32-8）*2=48个节点。

因此，最多情况下共有：63+48=111个节点

发表于 2018-01-30 19:26:35 回复(0)

牛客76440056号

这题有个最少的结点的问法，最少的问法时候只有6层，即为2^5-1+8=39，这些都是网上有的。我突然又想到这个题的另一个问法😀

已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则完全二叉树的结点个数不可能是以下哪些情况？A：39，B：110，C：111，D：xxx(这样出题会不会爆杀😅)

答案D

发表于 2022-03-09 20:29:47 回复(0)

小小offer收割机

华讯网络的软件开发笔试题

发表于 2021-06-20 10:19:21 回复(0)

fisher_yu

可以有第七层，为啥不能有第八层、第九层。。。。。

发表于 2019-04-10 10:57:58 回复(2)

小毛孩子

2^0+2^1+2^2+2^3+2^4+2^5+（2^5-8）*2
=1+2+4+8+16+32+24*2
=111

发表于 2018-04-28 12:40:15 回复(0)

一个锤子

想错了没有想到可以有第七层

发表于 2018-03-22 14:04:49 回复(0)

Krfsky<3Offer

6层为满有32个节点，其中24个还有叶节点，8个没有

由此为63 + 24* 2 = 111

发表于 2017-08-31 14:43:58 回复(0)

提交观点

问题信息

树

上传者：阿奻_

难度：

10条回答 131收藏 17627浏览

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

问题信息

热门推荐

相关试题