哈夫曼树基本概念

哈夫曼树的基本概念：

（1）路径：由一结点到另一结点间的分支所构成
（2）路径长度：路径上的分支数目a→d的路径长度＝ 2
（3）树的路径长度：从树根到每一结点的路径长度之和。 例图：10
（4）权：赋予某个实体的一个量，是对实体的属性的数值化描述。若树的结点带有权值，即为带权树。
（5）结点的带权路径长度：结点到根的路径长度与结点上权值的乘积d的带权路径长度＝72=14
（6）树的带权路径长度：树中所有叶子结点的带权路径长度之和。例图：27+25+22+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，则从根到每个叶子的路径上，分别构成一个二进制串，该二进制串称为哈夫曼编码。
进行哈夫曼编码，先建哈夫曼树。
哈夫曼编码是前缀编码，且是最优前缀编码。