我要招人

去企业版

首页 > 试题广场 >

已知一棵完全二叉树中共有626个结点,叶结点的个数应为()

[单选题]

已知一棵完全二叉树中共有626个结点，叶结点的个数应为（）

```
311
```
```
312
```
```
313
```
```
314
```
```
其他
```

查看正确选项

TPU-Lee

可知n2=n0-1;

得626=n2+n1+n0--626=2n0-1+n1;

n1=1,则n0=313，可知叶子节点数为313+1=314。

发表于 2016-01-15 14:41:37 回复(1)

养兔子的熊

完全二叉树最后一个结点的编号为n，则它的父结点编号为[n/2]，则叶结点个数为n-[n/2]。

626-[626/2]=313

发表于 2015-08-19 01:37:42 回复(1)

Baymax

1有定理n2 = n0 -1;

2 因为该树的节点数为偶数，所以n1必为1.

所以由以上可得：n0+n1+n2 = 626 => n0 + n0-1 + 1 = 626 =>n0 = 313

发表于 2015-09-04 11:17:36 回复(1)

jranzjm

我的算法是，因为是完全二叉树，所以与它最接近的满二叉树的节点数是512-1=511

所以最后一层的叶节点会有 626-511=115个

别忙，因为最后一层的叶节点会覆盖倒数第二层的“原叶节点”，所以，实际上增加的叶节点数是：115/2=57（向下取整）

所以叶节点是：256+57=313个

发表于 2018-01-08 22:27:47 回复(0)

eagle

完全二叉树，除了最后一行外，前面的行可以形成（国内定义的）满二叉树。

满二叉树每层的节点个数是 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.....

因为总节点626，显然前面的行到256就截止了。所以除去最后一行的节点个数为 512-1=511

最后一行的叶子节点为 626-511=115

倒数第二行的节点中不是叶子节点的个数为 115 / 2 = 57

倒数第二行中叶子节点数为256-57 = 199

所以总的叶子节点为115+199=314

发表于 2015-01-06 10:17:28 回复(7)

w逸泽

发表于 2018-08-17 21:10:42 回复(0)

__sgf__

度数为0的节点个数比度数为2的节点个数多1。因此626个节点的完全二叉树中度数为0的节点数是313，度数为2的节点个数为312，度数为1的节点个数是1

发表于 2022-03-14 01:04:43 回复(0)

指尖凉hsz

首先n₂ + n₁ + n₀ = 626,n₀ = n₂ + 1,所以根据两式得2n₀ + n₁ = 627,在完全二叉树中n₁只能为0或1，这里不能为0，否则n₀变成小数了，所以n₁ = 1，n₀ = 313。

发表于 2017-09-14 17:12:34 回复(0)

JamesXia

满二叉树,度为1的节点数量只有两种情况,要么为0,要么为1

而且由二叉树性质,度为2的节点=叶子节点-1

而题目二叉树节点数为偶,所以度为1的节点有1个

则n0+n1+n2 = n0+1+n0-1 = 626 => n0=313,选C

发表于 2017-03-07 03:10:36 回复(0)

yu钿

由626除以2取整，求得最后一个分支结点为313，则从314开始都是叶子结点，所以叶子结点个数为626-313得313。

发表于 2015-09-03 20:55:59 回复(0)

張三同学

n：总结点数
n0：叶子结点数
n1：度（孩子个数）为1结点数
n2：度（孩子个数）为2结点数

公式
① n = n0 + n1 + n2
② n0 = n2 + 1
③ n为奇数，n1 = 0，n为偶数，n1 = 1，
④ 由①②可以推出 n = n1 + 2*n2

题目解析
1.已知总结点数n为626，为偶数
2.所以n1 = 1
3.由④ n = n1 + 2*n2 可得 n2 = 312
4.由② n0 = n2 + 1 可得 n0 = 313

发表于 2023-01-09 23:24:09 回复(0)

牛客90237887号

完全二叉树度为1的结点只有1个

发表于 2022-09-28 21:11:22 回复(0)

陳丶奕丶迅

完全二叉树里要考虑是否含有度为1的节点(完全二叉树中度为1的节点可能不存在或者有一个)。这题通过计算可知该树有一个度为一的节点。

发表于 2022-08-02 10:46:44 回复(0)

请给offer我要offer

你们的方法都不行，关于这种题直接除以2后向上取整！

发表于 2022-05-24 19:27:09 回复(0)

许你清安L

首先 2 ^ 9 - 1 < 626 < 2 ^ 10 - 1,所以这棵树有10层，它的第十层有 626 - （2 ^ 9 - 1）[前九层的所有节点数] = 115个叶子节点

而这115个叶子节点是第九层中的非叶子节点的子节点

也就是在第九层中的非叶子节点数为 [115/2](向上取整，只有一个孩子的节点也是非叶子节点)，也就是 58个非叶子节点。

而在第九层中在不考虑第十层最多有2^8 = 256个叶子节点，去掉那些非叶子节点，最后就是256 - 58 = 198个叶子节点

最后的结果就是115 + 198 = 313个叶子节点。

发表于 2021-11-03 11:26:01 回复(0)

漫越

1，节点数=度数+1

n0+n1+n2=n1+2*n2+1 => n0=n2+1

2，no+n1+n2=626

由1,2 => 2*n2 + 1 + n1 = 626

3, 完全2叉数，n1=0 or 1

由2,3 => n1 = 1

代入得 n2=312 ,n0=313

发表于 2018-03-31 10:16:19 回复(0)

and疯子一起打怪升级

定义：叶子节点为度为0的节点
定理：树中的节点数等于所有节点度数加1
设度为2的节点个数为n2，度为1的节点个数为n1，度为0的节点个数为n0，所以总结点数N=n2+n1+n0，根据定理N=2n2+1n1+0*n0,所以有n0=n2+1,根据题意N=626，合并以上式子，解得n0=313

发表于 2018-03-23 11:10:37 回复(0)

wangChaoNK

解析:假设父节点的位置i则其左右子节点的位置分别为2*i 2*1+1
当子节点的位置为626时:其父节点的位置为626/2=313
所以在313以后的节点都是叶子节点所有叶子节点总数为:626-313=313

发表于 2017-05-17 15:19:20 回复(0)

提交观点

问题信息

树

难度：

18条回答 351收藏 10843浏览

已知一棵完全二叉树中共有626个结点,叶结点的个数应为()

问题信息

热门推荐

相关试题