我要招人

去企业版

首页 > 试题广场 >

一棵124个叶结点的完全二叉树,最多有()个结点

[单选题]

```
247
```
```
248
```
```
249
```
```
250
```
```
251
```

查看正确选项

天山二侠

叶节点即出度为0 的点，树每加出度为1的点则叶节点数和出度为2的点数不增加，所以叶节点总是比出度为2的节点多一个。由于是完全二叉树，出度为1的点有0或1个，所以有123（出度为2点）+124（叶节点）+0/1（出度为1）=247/248,最多有248个点！

发表于 2015-10-28 17:47:43 回复(0)

DJL箫氏

完全二叉树有如下性质，

n=n0+n1+n2

n:节点总数

n0:度为0的节点个数，也就是叶子节点

n1:度为1的节点个数，在完全二叉树中值有0和1这两种情况

n2:度为2的节点个数

又因为 n0=n2+1 所以n2=123,n1取较大的1

结论 n=n0+n1+n2=124+1+123=248

发表于 2016-07-12 16:35:08 回复(1)

eagle

因为每层的节点数必然为 1， 2， 4， 8， 16， 32， 64， 128， 256。。。

倒数第二层有64个

最后一层最少120，最多121，这样可以保证有124个叶子

所以最多248个节点

编辑于 2021-01-14 15:54:39 回复(4)

未知尤他

n0=n2+1,n0=124,则n2=123;完全二叉树最多有一个度为1的n1节点，且为左孩子，故124+123+1=248

发表于 2017-04-08 22:37:54 回复(0)

左庶长

由叶子节点个数，可知除最后两行，各行节点个数为：1，2，4，8，16，32

对于最后两行：

设倒数第二行具有双子节点的节点个数为n，则

1.若全部为具有双子节点的节点：2n+(64-n)=124 n=60, 总节点个数为：1+2+4+8+16+32+64+120=247

2.若有1个只含一个子节点的节点以及含有两个子节点的节点： 2(n-1)+1+(64-n)=124 n=61 ,总节点个数为 1+2+4+8+16+32+64+121=248

即最多为248

发表于 2018-01-10 09:36:50 回复(0)

huixieqingchun

要分析最后一层和倒数第二层的叶子结点数。

发表于 2016-05-27 09:40:48 回复(0)

那年的风景

叶子结点是双分支节点数加1。所以双分支节点数为123，单分支节点数为1或者0，最多则选择1。124+123+1=248.

发表于 2015-08-12 17:15:17 回复(5)

GZyoco

二叉树的度为0，1，2

度为0的节点数为度为2的节点数加1，

度为1 的结点数为0 或1，

因为题目要求最多节点，也就是度为1的节点数为1，

124+（124-1）+1=248

发表于 2019-09-03 18:45:16 回复(0)

GYT0313

式1：总节点数N = n0 + n1 + n2

式2：n0 = n2 + 1

代入：N = n0 + n1 + n0 - 1，得N = 124 +n1 + 123。

n1 取0 或 1，得N = 248。

发表于 2019-05-03 11:56:31 回复(0)

Jiang锋

根据完全二叉树的性质可知：

度为2的结点数比度为0的结点数少1，

度为1的结点数要么是以要么是0，

因为有124个叶子节点，则度为2的结点数为123

最少的情况：124+123+0=247

最多的情况：124+123+1=248

发表于 2018-11-22 19:10:51 回复(0)

wishboy

这题有点挖坑，咋一看，叶子节点124个，可能会理所当然的认为这124个叶子节点都在最后一层，从而得出度为1的节点数n1=0；从而由n0=n2+1得出n=n0+n2=247；以上为进坑后的答案。

问题在于，这124个叶子节点可以出现在k或k-1层上，当这两层中的叶子节点的个数都为偶数的时候，答案仍然是247，但是当这两层上的叶子节点均为奇数的时候，那么就有了n1=1的情况了，此时节点数为248.

都是进坑的人，分析了好久，见笑了！

发表于 2018-07-23 15:16:15 回复(0)

麦加

由于该树是完全二叉树，所以叶子节点只会存在于第h层跟第h-1层，假设第h-1层的叶子节点数为x，第h层的叶子结点数为y，那么有x + y=124。根据完全二叉树的性质，可以得知第h-1层的数量是2的N次方，那么可以确定h-1层的节点数有64个，可以得到x + y/2(向上取整)=64，可以解得y=120或y=121，取y=121，可以有1 + 2 + 4 + 8 +16 +32 + 64 +121 = 248。

发表于 2018-03-23 11:15:40 回复(0)