我要招人

去企业版

首页 > 试题广场 >

一棵完全二叉树上有1001个结点,其中叶结点的个数是()

[单选题]

一棵完全二叉树上有1001个结点，其中叶结点的个数是（）

```
250
```
```
500
```
```
254
```
```
505
```
```
以上答案都不对
```

查看答案及解析

Breeze Mao

完全二叉树的最后一个结点的编号一定是1001，则它的父结点的编号为1001/2=500，则叶子结点个数为1001-500=501.

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

发表于 2016-04-25 15:45:01 回复(14)

倒悬的橙子

图片说明

发表于 2016-12-26 08:53:52 回复(10)

忆梦＆....

设二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0 + n1 + n2 = 1001

根据二叉树性质：n0 = n 2 + 1，代入得到，2n2 + n1 = 1001

由于完全二叉树的n1 只能是0或者1，为满足2n2 + n1 = 1001，n1 = 1，因此n2 = 500

所以n0 = 501，即叶子个数是501个

编辑于 2021-01-14 15:52:06 回复(7)

王俊超

答案是501

按出度算：树中只有出度为2（记n2）和出度为0（记n0）的结点。

有n2 + n0 = 1001;

有多少个出度就有多少个入度（出度一共有2*n2），只有根结点没有入度，其它结点都有入度，入度为1（入度一共有n2-1+n0）

2*n2 = （n2-1）+n0

解得:n0=501

发表于 2015-08-03 16:03:56 回复(0)

红尘梦断都城

法1：结点总数为1001，奇数，故n1=0。由n=n0+n1+n2；n2=n0-1得：n=n0+n1+n0-1,即1001=2*n0-1,得 n0=1002/2=501.

法2：完全二叉树的最后一个结点编号为1001，由于其为奇数，因此其双亲结点编号为(1001-1)/2=500（若为偶数则直接除以2），双亲之后的结点都是叶结点，因此总叶结点n0=最后一个编号-其双亲编号=1001-500=501.

法3：此完全二叉树深度为:log2(n)向下取整+1=10.其前9层满数，第9层结点数为2^(9-1)=256，则前9层的总结点数为：(2^9)-1=511，因此第10层的叶结点数为：1001-511=490，则第9层非叶结点个数为490/2=245（2对1），则第9层结点个数为：256-245=11。因此总叶结点为：第9层的+第10层的=11+490=501

发表于 2017-08-16 13:57:49 回复(0)

萱萱是个好姑娘

结点数为奇数,所以度为1的结点有0个,度为2的节点数=度为0的节点数-1,所以2*度为0的节点数-1 = 1001,所以度为0的节点数为501

发表于 2016-06-05 10:53:57 回复(0)

张佃鹏

对于完全二叉树来说，n为偶数，叶子节点的个数为n/2,如果n为奇数，叶子节点的个数为n/2+1

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

牛客246513132号

因为 : n0+n1+n2 = 1001;
又因 : n0 = n2 + 1;
故 : 2n0+n1 = 1002;

因为 : n1 = 0；

所以 : 2n0 = 1002:

即 : n0 = 501;

发表于 2020-07-05 15:41:40 回复(1)

如是说如是

n = n。+ n1 + n2
( n: 总结点个数
n。:无孩纸的结点个数（即叶子结点）
n1:有一个孩纸的结点个数
n2:有两个孩纸的结点个数
结点要么有两个孩纸，要么一个，要么没有）
由完全二叉树性质可知，若给每个结点依次序标上1~n序号，序号为 i 的结点（假设有两个孩纸存在）其左孩纸序号为 2i（皆为偶数），右孩纸序号为 2i + 1 （皆为奇数）
故 1001 为右孩子，其父结点序号为 500 （ 2i + 1 = 1001 解得 i = 500 ）
故n2 = 500 （按规律501的孩纸序号应为501 * 2 = 1002 和 1003，此题一共只有1001个结点，故501 没有孩纸）
n1要么为 0 要么为 1 ，奇数个结点时为最后一个叶子结点为右孩纸，偶数个结点时最后一个为左孩纸
此时 n1 = 0 (1001是右孩纸)
n = n。+ n1 + n2
1001 = n。+ 0 + 500
n。= 501

发表于 2019-05-29 21:28:01 回复(0)

桀骜猴子

高度为h的满二叉树节点数目为 2^h-1 个节点，现在512-1<1001<1024-1，那么1001-511=490，说明这颗二叉树的最后一层有490个叶子节点；

若为满二叉树，最后一层叶子节点为512，现在少了22个，说明倒数第二层还有11个叶子节点。

所以一共 490+11=501 个叶子节点。

不同的思路，分享一下，欢迎指正！

发表于 2017-09-07 09:25:26 回复(0)

牛客280427523号

n0=n2+1

发表于 2021-08-30 14:16:57 回复(0)

段小编程师

n0＝n2+1带入1001＝n0+n1+n2，得到1001＝2n0+n1，再根据是完全二叉树，1001是没有n1的（自己用1001减去第一项到第n-1项的和，判断是奇数还是偶数，奇数就是n1＝1，偶数就是n1＝0）然后就可以求出叶子节点

编辑于 2024-04-10 21:54:43 回复(0)

sanfenl

完全二叉树具有1001个结点，判断出2^9-1<1001<2^10-1，树的深度为10。

假设此时是深度为10的满二叉树那么总结点数为：1023，不是满二叉树的情况下有,第9层的结点是没有孩子的也就是有(1023-1001)/2=11是叶子结点。

在深度为9的满二叉树结点数为511，1001-511=490。

叶子结点个数为：490+11=501

发表于 2022-12-29 00:55:26 回复(0)

用心的柠檬精许愿简历通过

501个叶子结点。

发表于 2022-07-03 16:02:19 回复(0)

回不去的过去

个人观点：先算最接近的满二叉树为1024，第9层为512，所有要成为满二叉树就要加512个节点，现在有1001个节点，所有叶子节点应该是512-（1024-1001）/2

编辑于 2020-05-28 22:34:01 回复(0)

fangqi_方其

怎么发不了图片

发表于 2018-10-19 09:43:12 回复(0)

叶子、树与风的故事

结点数：2^(n-1)

叶子结点数:2^n - 1

2^n-1=1001 2^n=1002

2^(n-1)=1/2*2^n=1002 =501

发表于 2018-09-10 13:46:21 回复(1)

lwxl

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

发表于 2018-04-13 17:07:34 回复(0)

sc111

n为奇数，则度为1的节点n1=0;

n0=n2+1;

n0+n2=1001;

联立得到n0=501

发表于 2017-04-28 16:45:13 回复(0)

码有农

二叉树中度为0的叶子结点个数为n0，度为1结点个数为n1，度为2结点个数为n2，于是n0 + n1 + n2 = 1001
根据二叉树性质：n0 = n 2 + 1，代入得到，2n2 + 1+ n1 = 1001
由于完全二叉树的n1 只能是0或者1，为满足2n2 + 1 + n1 = 1001，n1 =0，因此n2 = 500
所以n0 = 501，即叶子个数是501个

发表于 2017-04-06 09:56:41 回复(0)

提交观点

问题信息

树

难度：

25条回答 396收藏 46332浏览

一棵完全二叉树上有1001个结点,其中叶结点的个数是()

问题信息

热门推荐

相关试题