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

[单选题]

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

```
2m-1
```
```
2m
```
```
2m+1
```
```
4m
```

查看正确选项

璎珞-沐

哈夫曼树不存在入度为1 的结点，所以n0=n2+1

设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（2m）个空指针域; n0=m

树的二叉链表存储结构就是孩子-兄弟表示法。

孩子-兄弟表示法:数据域是结点，如A; 有两个指针域：1）指向长子 2）指向右兄弟

哈夫曼树的孩子-兄弟表示法的空指针域有三种情况：（1）叶子结点长子域一定为空m个（2）根节点的右兄弟域一定为空 1个（3）除去根节点外，哈夫曼树的其余结点个数中有一半结点的右兄弟域为空（n总-1）/2=n2

所以空指针域=m+1+n2=2m

发表于 2017-05-22 21:12:24 回复(0)

zurp

首先哈夫曼树仅有度为0（n₀个）、2（n₂个）的节点，然后二叉树中有n₀=n₂+1；

二叉树一个节点对应两个指针域，n个节点的二叉树有2n个指针域、2n-(n-1)=n+1个空指针域；

所以当前哈夫曼树有2m-1个节点，2m个空指针域

发表于 2018-04-21 16:59:02 回复(0)

Slun夜心

哈夫曼树只有度为0和2的结点(二叉树的结点数满足n0=n2+1)，二叉链表存储结构是：lchild-data-rchild(表示一个结点，其中data是数据域，lchild和rchild是指针域，分别指向左右孩子结点)。显然度为0的叶子结点的两个指针域都是空指针域，有m个叶子结点，就有2m个空指针域。

发表于 2018-07-19 15:19:38 回复(2)