我要招人

去企业版

首页 > 试题广场 >

设哈夫曼树中的结点总数为49，若用二叉链表作为存储结构，则该

[单选题]

设二叉树中的结点总数为49，若用二叉链表作为存储结构，则该二叉树中总共有多少个空指针域（）

```
51
```
```
52
```
```
50
```
```
49
```

查看答案及解析

IT工作

一共有 n个节点。那么每一个节点都有两个域，共有2n个。一共有多少个分支呢？每一个节点都有父节点(除了根节点)那么就会有n-1个分支。那么空指针的域就是2n - (n-1) = n+1;那么就会有n+1个空指针域。也就是50个。不管是不是满二叉树，这个结论都是正确的。

发表于 2016-04-10 19:50:54 回复(1)

超小白

这不就是二叉树的性质么，和哈夫曼树都没多大关系，只要是二叉树，有n个节点，就一定是有n+1个空指针域，这在学线索二叉树的时候有详细推理过程的。
1. n个结点，每个结点有两个指针共2n个指针，
2. n个结点，除根结点外的n-1个结点都有一个指向父结点的线，即非空指针，共n-1条非空指针
3. 控指针数 = 总指针数-非空指针数 = 2n-(n-1) = n+1
推到完毕

发表于 2016-08-20 08:58:57 回复(2)

hyhappy

哈夫曼树只有度为2的结点和叶子结点，并且n0=n2+1，由此计算可知，叶子结点有25个，而每个叶子结点有两个空指针，所以共有50个

发表于 2016-04-09 23:53:36 回复(2)

__sgf__

背结论：二叉树有 n 个节点，就一定是有 n +1个空指针域。特殊值法：假设是完全二叉树，度数为0的节点个数比度数为2的节点个数多1。因此有25个叶子节点，24个度数为2的节点，0个度数为1的节点。此时空指针域都来自于叶子结点，所以有50个空指针域。

发表于 2022-03-14 01:46:35 回复(0)

testestest

n个结点二叉树有2n个指针域，
除了头结点没有指针指向它，
剩下的n-1个结点都有一个指针域指向它，
所以要使用n-1个指针域，还剩 n+1 个。

编辑于 2016-04-12 21:13:09 回复(0)

thfeng

总共有2*49 = 98个指针域，非空指针也就是说两个结点间有边相连，边数 = 结点总数-1，得非空指针数为49-1 = 48

所以空指针的个数为98-48 = 50

发表于 2016-08-15 10:53:18 回复(0)

main方法栈帧

假设这棵树是完全二叉树
则空指针数全部集中在叶子节点上
(叶子节点的2个域全部为空)

这道题给出节点数为49
所以度为1的节点 n1 = 0
n2 = n0 - 1
则 2n0 - 1 = 49
n0 = 25
所以一一共有25个叶子节点
则空指针域的个数 = 25 * 2 = 50

发表于 2021-11-14 15:31:34 回复(0)

东风街大饼

一共有n个节点。那么每一个节点都有两个域，共有2n个。一共有多少个分支呢？每一个节点都有父节点(除了根节点)那么就会有n-1个分支。那么空指针的域就是2n - (n-1) = n+1;那么就会有n+1个空指针域。也就是50个。不管是不是满二叉树，这个结论都是正确的。

发表于 2021-07-26 12:19:08 回复(0)

放弃幻想，放弃安逸

空指针域和空指针有什么区别那

发表于 2020-03-18 20:52:45 回复(0)

安科15计爱玲

假设这个树是一个链状树，除了叶节点外所有的节点都只有左子树，那么空域的数目就是48+2，叶节点有两个，其他节点都只有一个

发表于 2018-05-16 09:39:05 回复(0)

Dominic-Tse

假设度为2，1，0的节点数为年n2，n1，n0,那么

总结点数为n2 + n1 + n0 = 49
n0 = n2 + 1,因此，2 * n2 + n1 = 48
空指针树为 n1 + 2 * n0
2 * n0 = 2 * n2 + 2 → n1 + 2 * n0 = n1 + 2 * n2 + 2 = 50

发表于 2018-05-14 15:53:12 回复(0)

Sc0tt

对于一棵又N个节点的二叉树，有N+1个空指针域，N-1个非空指针域。

发表于 2018-05-07 09:04:36 回复(0)

牛客452770号

哈夫曼树只有度为2的结点和叶子结点，并且n0=n2+1，由此计算可知，叶子结点有25个，而每个叶子结点有两个空指针，所以共有50个

这不就是二叉树的性质么，和哈夫曼树都没多大关系，只要是二叉树，有n个节点，就一定是有n+1个空指针域，这在学线索二叉树的时候有详细推理过程的。
1. n个结点，每个结点有两个指针共2n个指针，
2. n个结点，除根结点外的n-1个结点都有一个指向父结点的线，即非空指针，共n-1条非空指针
3. 控指针数 = 总指针数-非空指针数 = 2n-(n-1) = n+1
推到完毕

发表于 2017-05-11 09:51:32 回复(0)

666662

哈夫曼树结点个数=2*n-1

n为叶子节点个数。

发表于 2016-09-03 19:22:22 回复(0)

潇湘蛮人

哈夫曼树只有度为2的结点和叶子结点，并且n0=n2+1，由此计算可知，叶子结点有25个，而每个叶子结点有两个空指针，所以共有50个。或者这样理解，除了根节点这层只有一个结点外，其他层都有两个节点。根据题目，有49个节点，所以除了根节点外，有48个节点，也就是24层，最底层的有两个叶子节点，其它层有一个叶子节点，所以一个有25个叶子节点，而一个叶子节点有两个空指针，所以共有50个。

发表于 2016-08-11 22:31:23 回复(0)

牛客450995号

有n个权值的节点集合，总共节点个数为2 * n - 1，所以本题n = 25；所以空指针为25 * 2 = 50；

发表于 2016-05-22 16:46:51 回复(0)

不想打工的沸羊羊很坦荡

个人观点：对完全二叉树如果有n个结点，则n/2是最小非叶子结点，而且当n%2 ！= 0时该位置处的结点有右子树，剩下的数数就出来了

发表于 2016-04-11 19:40:45 回复(0)

提交观点

问题信息

树

来自：美丽联合2017校园招...

难度：

17条回答 636收藏 16195浏览

设哈夫曼树中的结点总数为49，若用二叉链表作为存储结构，则该

问题信息

热门推荐

相关试题