我要招人

去企业版

首页 > 试题广场 >

设一棵完全二叉树共有999个结点，则在该二叉树中的叶子结点数

[单选题]

设一棵完全二叉树共有999个结点，则在该二叉树中的叶子结点数为

```
499
```
```
500
```
```
501
```
```
不唯一
```

推荐

eagle

完全二叉树叶子节点数与其他节点数相等，或者多一个。

因为总结点数是999。奇数，所以叶子节点多一个，为500

编辑于 2015-02-06 11:55:09 回复(1)

天涯寻梦

根据二叉树的性质可知：叶子结点数n0＝n2+1，根据完全二叉树的概念可知，度为1的结点数要么为1，要么为0，二叉树总结点数
N＝n0+n1+n2＝2n0+n1－1，则结果为500

发表于 2015-09-30 16:15:00 回复(0)

小牛快跑233

假设所有结点总数为n，度为0的结点(叶子节点)为n0，度为1的结点n1，度为2的结点为n2。

我们考虑分支线总数的关系，n - 1 = n1 + 2 * n2; //①

而结点总数的数据关系很容易得：n = n0 + n1 + n2;//②

也就是(n0 + n1 + n2) - 1 = n1 + 2 * n2 → n0 = n2 + 1

然后 n = n0 + n1 + (n0 - 1) = 2n0 + n1 - 1;

即no = (n + 1 - n1) / 2，又因为在完全二叉树中，n1不是为0就是为1。而且n0必须是整数，也就是n1 = 0时

n0 = (999 + 1) / 2 = 500个

编辑于 2016-08-21 02:01:18 回复(0)

岁既晏

1.如果深度为10,满二叉树结点有2^k-1=1023个，

2.1023-999=24，即还差24个结点为满二叉树

3.满二叉树第10层结点数为2^(k-1)=512

4.结果为 512-24+(24/2)=500

发表于 2019-10-17 11:25:59 回复(0)

艾伦图灵

完全二叉树非叶子节点个数=n/2向下取整，叶子节点个球=总数-非叶子节点个球！

发表于 2017-04-11 10:47:52 回复(0)

流浪去远方

叶子节点数为: 488

完全二叉树（设高度为N）去掉所有的叶子节点，就是一个满二叉树（高度为N-1）。

则节点数的关系为：高度为(N-1)的满二叉树的节点数<999<高度为(N)的满二叉树的节点数。

所以2^(N-1) - 1 < 999 < 2^(N) -1 ;求得N=10.

所以

完全二叉树(高度为N)的叶子节点数 = 完全二叉树(高度为N)的节点数 - 满二叉树（高度为N-1）节点数

=999 - (2^9 - 1)

=488

发表于 2015-09-07 13:05:10 回复(1)

GYT0313

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

式2：n0 = n2 + 1

代入：999 = n0 + n1 + n0 - 1，得n0 = (1000 - n1) / 2

因为，n1 = 0 或 1，得 n0 = 500。

发表于 2019-05-03 15:46:28 回复(0)

墨白12

这不是个完全二叉树，有问题吧这题？？？

发表于 2019-01-05 22:18:03 回复(0)

Fengzhi志

记住度为1的节点数要么是0，要么就是1，可以根据总节点数N=2n0 + n1 - 1这个公式求得。

发表于 2018-11-10 00:45:56 回复(0)

stu_rt

完全二叉树只有度为0和2。n0=n2+1

发表于 2017-07-28 13:51:11 回复(1)

西门庆庆

利用二叉树边的总数来建立方程，设二叉树的叶子几点数为x，

每个节点有一条边指向父节点，根节点没有父节点，得边数=999-1；

完全二叉树每个非叶子节点都有两个儿子对应两条边：得边数=（999-x）*2;

有（999-1）=（999-x）*2 。解得x=500

发表于 2016-10-27 21:06:10 回复(0)

棉花汤

(999+1)/2=500

发表于 2016-08-08 10:47:12 回复(0)

不想打工的沸羊羊很坦荡

发表于 2016-07-25 10:14:39 回复(0)

提交观点

问题信息

树京东

上传者：马特殊

难度：

13条回答 131收藏 8684浏览

设一棵完全二叉树共有999个结点，则在该二叉树中的叶子结点数

问题信息

热门推荐

相关试题