初步认识哈夫曼树

7.哈夫曼数的基本概念：

（1）路径：由一结点到另一结点间的分支所构成

（2）路径长度：路径上的分支数目a→d的路径长度＝ 2

（3）树的路径长度：从树根到每一结点的路径长度之和。      例图：10

（4）权：赋予某个实体的一个量，是对实体的属性的数值化描述。若树的结点带有权值，即为带权树。

（5）结点的带权路径长度：结点到根的路径长度与结点上权值的乘积d的带权路径长度＝7*2=14

（6）树的带权路径长度：树中所有叶子结点的带权路径长度之和。例图：2*7+2*5+2*2+2*4=36

（7）赫夫曼树（Huffman）：最优二叉树，带权路径长度最小的树

哈夫曼树的特点

–权值大的结点到根结点的路径长度短;

–权值小的结点到根结点的路径长度长。

Ø哈夫曼编码树中没有度为1的结点；

Ø若给定n个权值（n个叶子结点），则哈夫曼树的总结点数为 2n-1；

Ø哈夫曼树的高度不超过n。

哈夫曼数的构造算法：

哈夫曼编码：

v前缀编码：任一字符的编码都不是另一字符编码的前缀。

如：字符a、b、c、d的编码分别为0、1、01、10，则a的编码是c的编码的前缀，b的编码是d编码的前缀，该编码不是前缀编码。

在译码时，对于01011011的译码结果将不唯一。

v哈夫曼编码

对一棵具有n个叶子的哈夫曼树，对每个左分支赋予0，右分支赋予1，则从根到每个叶子的路径上，分别构成一个二进制串，该二进制串称为哈夫曼编码。

进行哈夫曼编码，先建哈夫曼树。

哈夫曼编码是前缀编码，且是最优前缀编码。