我要招人

去企业版

首页 > 试题广场 >

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

[单选题]

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

```
112
```
```
111
```
```
107
```
```
109
```

推荐

SunburstRun

答案是D

这个题目第六层有9个叶结点,问最多有多少个结点,那我们可以想到可以有第7层,但是第7层少了18个结点,那么第六层就剩下9个叶子节点所以答案为:1+2+4+8+16+32+64-18=109

编辑于 2016-11-30 22:22:56 回复(3)

美团到店招聘

第一层：1

第二层：2

第三层：4

第四层：8

第五层：16

第六层：32

第七层：2*(32-9)

共计：109个结点

发表于 2017-02-23 10:58:46 回复(1)

牛客小小菜鸟

第六层有9个叶结点，题目要求最多的结点数，可以推测还有第7层。第6层一共的结点数为32，减去9个叶子结点，（考虑最多结点情况下）剩下23个结点都有左右子树，故第7层一共有23*2=46个结点，最后加上前6层的结点数2⁶-1=63, 46+63=109，因此最多的结点数为109.

发表于 2017-08-12 20:20:19 回复(2)

吭哧吭哧埋头干

答案是D

七层总节点数-第六层叶子节点数*2：（2⁷-1）-9*2=109

发表于 2017-02-09 10:02:14 回复(0)

tla001

叶子节点之存在于最大的两层，即第六层和第七层。则前六层为满二叉树，共有2^6-1=63个节点

第七层最多节点数（2^(6-1)-9）*2=46，所以一共最多有109个节点

编辑于 2017-03-06 14:43:58 回复(1)

ziCrazy

利用二叉树的性质 2^(i-1)，

第一层1个、

第二层2个、

第四次4个、

第五层16个、

第六层有 32个、

第七层2*（32-9）

总共有109个结点

发表于 2022-04-15 14:43:07 回复(0)

这个大叔不太冷_

结点个数最少的情况是总共六层，且第六层有9个结点，前五层全满，则总节点个数最少2⁵-1+9=40个。

结点个数最多的情况是总共七层，但是第七层并没有满，还差9*2=18个(因为是完全二叉树，存在第六层的叶子节点树为9个)，在七层全满的情况下总的结点的个数为2⁷-1=127个，所以当前情况下节点个数最多为127-18=109个

发表于 2019-12-04 23:08:23 回复(0)

牛客670767258号

最多的情况是：高度为7的满二叉树少2*9个结点，即2⁷-1-18=109

发表于 2021-05-07 11:37:25 回复(0)

karaysn

这个题目要是最少的话，应该就是第六层没有排满吧，只有9个节点这样子，然后一共的个数是40吧

发表于 2017-09-08 22:01:35 回复(0)

acadf

不能有第八层?第九层?

发表于 2023-12-11 12:34:48 回复(0)

强无畏

本题选择D!一共有七层，前六层包括第六层为满，其中第六层有九个叶结点，说明第七层有(32-9)✘2=46个叶结点，总共为109个结点个数

发表于 2022-02-01 14:35:12 回复(0)

恶寒轻轻

如果按照我们最基本的思路，他有6层，然后第六层有9个叶结点，这是符合题意的，BUT！这里是问最多情况下，我们应该要想到有第7层且第6层有9个叶结点也是符合题意的。所以第六层有9个叶结点，剩余2^5-9=23个结点，由于是完全二叉树，故第七层应有23*2=46个结点，综述：46+2^6-1=109

编辑于 2021-11-23 18:47:41 回复(0)

TT珑

第六层有9个叶子节点，那么最多的情况就是第七层这9个叶子节点的儿子们都被删去了。
所以应该是2^7-1-18=109个。

发表于 2021-01-13 10:19:23 回复(0)

Simon..

第6层为满节点 32个，最右边9个为叶节点，第7层有46个叶节点，共有63+46=109个节点。 但考虑最多的情况，在第六层的最左边叶节点应有一个左子树，此时不改变叶节点数量，但节点总数为110

发表于 2020-11-25 21:33:52 回复(0)

天尊墨宇

选D

编辑于 2020-07-05 09:13:38 回复(0)

你的offer对我打了烊

一颗满二叉树的公式是2的n次方减1，n代表层数，根结点算第一层，所以这题就是2的7次方-1然后减掉9*2

发表于 2020-05-02 22:41:54 回复(0)

呱201808031156147

第7层全满2^n-1 = 127,6层9个叶子，7层-18

发表于 2018-08-26 16:29:44 回复(0)

NB响当当

我觉得这道题出的有问题，既然可以有第7层为什么不能有第8层，你们那(32 - 9)个第7层节点为什么不能再 *2 出来，他对层数有没有限制，所以我感觉这道题答案按他的叙述应该是无穷。内心是拒绝凑答案的……

发表于 2018-03-08 10:55:39 回复(2)

梦境迷离

看成9 个节点硬是找不到答案

发表于 2018-02-01 14:45:30 回复(0)

hahahha123

根据二叉树的性质，二叉树的第i层上的节点数最多2^i,（i>=0,即第一层i=0），第六层的节点数最多为2^5=32,第七层节点数=2*（32-9）,总数即数每层节点数相加，2^0+2^1+2^2+..+2^5_2*(32-9)=109

发表于 2017-11-29 10:03:16 回复(0)

AlexNeverStop

2^6-1+(2^5-6)*2代公式

发表于 2017-07-09 12:08:29 回复(0)

提交观点

问题信息

来自：职能类模拟题1

上传者：牛100

难度：

22条回答 456收藏 8207浏览

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

问题信息

热门推荐

相关试题