哈夫曼树的构造规则是什么，哈夫曼编码有什么特点?

核心考点

哈夫曼树构造过程、带权路径长度WPL、前缀编码特点及哈夫曼编码的典型考法。

参考答案(答题要点)

1.哈夫曼树构造规则：给定n个权值，先把每个权值看成只有根结点的单结点树，构成森林;每次从森林中选两棵根结点权值最小的树合并，新根结点权值为两棵子树根权值之和;删除原两棵树，把新树加入森林;重复上述过程n-1次，直到只剩一棵树，即为哈夫曼树。

2.构造要点：每次合并后产生的新权值要重新参与比较和排序;左右孩子顺序通常不唯一，小权值放左或放右不影响WPL;哈夫曼树中不存在度为1的结点。

3.哈夫曼编码特点：是一种前缀编码，任一字符的编码都不是另一字符编码的前缀，因此解码不会产生歧义;是不等长编码，权值大的字符编码较短，权值小的字符编码较长;能使带权路径长度WPL最小，即平均码长最短;哈夫曼编码不唯一，但最优WPL相同。

4.常见结论：n个叶子的哈夫曼树共有2n-1个结点;n个叶子需合并n-1次;WPL等于所有叶子权值乘其路径长度之和，也等于所有合并产生的新结点权值之和。

5.适合考题：构造哈夫曼树、求WPL、给字符权值设计哈夫曼编码、判断是否为前缀码、计算平均码长、判断哈夫曼树结点数等。

6.总结：构造抓“每次选两个最小权值合并”，编码抓“前缀编码、不等长、WPL最小”。看到权值构造和最短平均码长优先想到哈夫曼树。

易错提醒

每次合并后新权值必须参与后续排序，不能只在初始权值中选。哈夫曼编码不唯一，不能因左右顺序不同判错。WPL是叶子权值乘路径长度，不是权值乘编码位数以外的其他量。前缀码要求任一编码不能是另一编码的前缀。哈夫曼树没有度为1的结点。

今日小测

若哈夫曼树有n个叶子结点，则该哈夫曼树共有多少个结点?

答案：共有2n-1个结点。