数据结构【哈夫曼树】

哈夫曼树的概念

最优二叉树也称哈夫曼 (Huffman) 树，是指对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树。权值是指一个与特定结点相关的数值。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

涉及到的几个概念：
路径:
从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
结点的路径长度:
两结点间路径上的分支数。
树的路径长度:
从树根到每一个结点的路径长度之和。记作: TL。
权(weight):
将树中结点赋给一个有着某种含义的数值则这个数值称为该结点的权。
结点的带权路径长度:
从根结点到该结点之间的路径长度与该结点的权的乘积。
树的带权路径长度:
树中所有叶子结点的带权路径长度之和。
二叉树的带权路径长度 (Weighted Path Length)：
二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。
如果二叉树中的所有叶子结点都具有一个特定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶子结点，那么从根结点到各个叶子结点的路径长度与该叶子结点相应的权值的乘积之和叫做又树的带权路径长度，记为：

其中，wk为第k个叶子结点的权值，Lk为第k个叶子结点的路径长度。

最优树：带权路径长度(WPL)最短的树

注：
“带权路径长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等。

最优二叉树：带权路径长度(WPL)最短的二叉树

因为构造这种树的算法是由哈夫曼教授于 1952 年提出的所以被称为哈夫曼树，相应的算法称为哈夫曼算法。

哈夫曼树的构造

哈夫曼算法(构造哈夫曼树的四句口诀)
(1)根据n个给定的权值{ w1、w2、…、wn}构成n棵二叉树的森林F=(T1、T2、…、Tn}，其中Ti只有一个带权为 wi的根结点。
构造森林全是根
(2)在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
选用两小造新树
(3)在F中删除这两棵树，同时将新得到的二又树加入森林中。
删除两小添新人
(4)重复(2)和(3)，直到森林中只有一棵树为止，这棵树即为哈夫曼树。
重复 2、3 剩单根

可以得出：
1）哈夫曼树的节点的度为0或2，没有度为1的节点。
2）包含n个叶子节点的哈夫曼树中共有2n-1个节点。
3）包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新节点。

构造算法的实现

顺序结构存储–一维结构数组

typedef struct (int weight;int parent, lch, rch;
)HTNode,*HuffmanTree;

先初始化再构造
1.初始化HT[1…2n-1]: lch=rch=parent=0；
2. 输入初始n个叶子结点: 置HT[1…n]的weight值；

3.进行以下n-1次合并，依次产生n-1个结点HT[i]，i=n+1…2n-1:
a) 在HT[1.i-1]中选两个未被选过(从parent ==_0 的结点中选)的weight最小的两个结点HT[s1]和HT[s2],s1、s2为两个最小结点下标;
修改HT[s1]和HT[s2]的parent值: HT[s1] .parent=i; HT[s2] .parent=i;b)修改新产生的HT[i]:
HT[il.weight=HT[s1].weight + HT[s2].weight
HT[i]. lch=s1; HT[i]. rch=s2;

哈夫曼树应用

哈夫曼编码

哈夫曼编码的算法实现

示例：