哈夫曼树与哈夫曼编码

 一、最优树的定义：设有 n 个叶子结点，且每个叶子结点有一个权值，则包含这n个叶子结点的所有 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。最优树可能不止一个！

 路径： 从树中一个结点到另一个结点之间的分支所构成的通路 。

 路径长度： 路径上分支的数目。

  结点的带权路径长度：从树根到该结点之间的长度l与结点权值w的乘积 ( l * w ) 。

  树的带权路径长度：树中所有叶子结点的带权路径长度之和：WPL(T) = S wk lk  

二、如何构造最优树（哈夫曼算法）

问题：已知n个权值，用n个权值作为叶子结点，构造一棵二叉树，使该二叉树的带权路径长度最短。

(1)根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合： F = {T1,   T2,  … , Tn}，

其中每棵二叉树中均只含一个带权值为 wi 的根结点,其左、右子树为空树;

(2)在 F 中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;

假设有n个叶子结点，要构造一棵m叉最优树，

如果（n－1）Mod（m－1）＝0，则n个结点正好构成一棵m叉的正则树。

否则，需要补充一些虚叶子结点，构成一棵m叉树。补充的虚结点的个数为 (m－1)－ (n－1)Mod(m－1)。

三、前缀编码指的是，编码字符集中任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

在编码集合对应的二叉树中，所有编码都在叶子节点上。

利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，使所传电文的总长度最短。

举例:    已知某系统在通讯联络中只可能出现八种字符A,B,C,D,E,F,G,H, 其概率分别为:0.05, 0.29, 0.07, 0.08, 0.14, 0.23,0.03,0.11试设计哈夫曼编码.

设权 w = { 5, 29, 7, 8, 14, 23, 3, 11 }

                 A  B   C  D   E    F   G  H

哈夫曼编码:   0110, 10, 1110, 1111, 110,   00,  0111, 010