5.9 哈夫曼树及其应用
5.9 哈夫曼树及其应用
哈夫曼树（Huffman Tree）也是一种特殊的二叉树，这种树的所有叶子节点都带有权值，从中构造出带权路径长度最短的二叉树，即哈夫曼树。
5.9.1 什么是哈夫曼树
设二叉树具有n个带权值的叶子节点，那么从根节点到各个叶子节点的路径长度与相应节点权值的乘积的和，叫做二叉树的带权路径长度，记作：
|
图5-30 带权二叉树
|
其中，wi为第i个叶子节点的权值；li为第i个叶子节点的路径长度。如图5-30所示的二叉树，它的带权路径长度值WPL=1×3+ 3×3+2×2+4×1=20。
如果给定一组具有确定权值的叶子节点，可以构造出不同的带权二叉树，它们的带权路径长度并不相同，其中具有最小带权路径长度的二叉树称为哈夫曼树。
【例5-6】如图5-31所示的4棵二叉树具有相同的叶子节点，计算出它们的带权路径长度。
图5-31 具有相同叶子节点和不同带权长度的二叉树
解：它们的带权路径长度分别如下。
（a）WPL=1×2+3×2+5×2+7×2=32
（b）WPL=1×2+3×3+5×3+7×1=33
（c）WPL=7×3+5×3+3×2+1×1=43
（d）WPL=1×3+3×3+5×2+7×1=29
其中图5-31（d）所示的二叉树就是一棵哈夫曼树。
5.9.2 哈夫曼树的构造
根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子节点越靠近根节点，而权值越小的叶子节点越远离根节点。那么如何构造一棵哈夫曼树呢？其方法如下：
（1）由给定的n个权值{W1,W2,…,Wn}构造n棵只有一个叶子节点的二叉树，从而得到一个二叉树的集合F={ T1,T2,…,Tn }。
（2）在F中选取根节点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根节点的权值为其左、右子树根节点权值之和。
（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中。
（4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
【例5-7】对于一组给定的叶子节点{a,b,c,d,e}，它们的权值集合为W={4,2,1,7,3}，给出由此集合构造哈夫曼树的过程。
解：构造哈夫曼树的过程如图5-32所示。
图5-32 哈夫曼树的构造过程
为了实现构造哈夫曼树的算法，设计哈夫曼树中每个节点类型如下：
typedef struct
{
char data; /*节点值*/
float weight; /*权重*/
int parent; /*双亲节点*/
int lchild; /*左孩子节点*/
int rchild; /*右孩子节点*/
} HTNode;
用ht[ ]数组存放哈夫曼树，对于具有n个叶子节点的哈夫曼树，总共有2n-1个节点。其算法思路是：n个叶子节点只有data和weight域值，先将所有2n-1个节点的parent、lchild和rchild域置为初值-1。处理每个非叶子节点ht[i]（存放在ht[n]～ht[2n-2]中），从ht[0]～ht[i-2]中找出根节点（即其parent域为-1）最小的两个节点ht[lnode]和ht[rnode]，将它们作为ht[i]的左右子树，ht[lnode]和ht[rnode]的双亲节点置为ht[i]，并且ht[i].weight=ht[lnode]. weight+ht[rnode].weight。如此这样直到所有2n-1个非叶子节点处理完毕。构造哈夫曼树的算法如下：
void CreateHT(HTNode ht[],int n)
{
int i,j,k,lnode,rnode;
float min1,min2;
for(i=0;i<2*n-1;i++) /*所有节点的相关域置初值-1*/
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n;i<2*n-1;i++) /*构造哈夫曼树*/
{
min1=min2=32767; /*lnode和rnode为最小权重的两个节点位置*/
lnode=rnode=-1;
for(k=0;k<=i-1;k++)
if(ht[k].parent==-1) /*只在尚未构造二叉树的节点中查找*/
{ if(ht[k].weight<min1)
{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k;
}
}
ht[lnode].parent=i;ht[rnode].parent=i;
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode;
}
}
5.9.3 哈夫曼编码
哈夫曼编码具有广泛的应用，利用哈夫曼树构造的用于通信的二进制编码称为哈夫曼编码。例如，有一段电文"CAST?TAT?A?SA"（其中，"?"表示一个空格）。统计电文中字母的频度f('C')=1，f('S')=2，f('T')=3，f('?')=3，f('A')=4。用频度{1,2,3,3,4}为权值生成哈夫曼树，并在每个叶子上注明对应的字符。树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符编码，这就是哈夫曼编码。生成的哈夫曼树如图5-33所示。
为了实现构造哈夫曼编码的算法，设计存放每个节点哈夫曼编码的类型代码如下：
typedef struct
{
char cd[N]; /*存放当前节点的哈夫曼编码*/
int start; /*start指向cd数组中哈夫曼编码最开始字符*/
} HCode;
|
C |
S |
T |
? |
A |
|
011 |
010 |
00 |
10 |
11 |
图5-33 由编码生成的哈夫曼树
由于哈夫曼树中每个叶子节点的哈夫曼编码长度不同，为此采用HCode类型变量的cd[start]～cd[n]存放当前节点的哈夫曼编码，只需对叶子节点求哈夫曼编码。对于当前叶子节点ht[i]，先将对应的哈夫曼编码hcd[i]的start域值置初值n，找其双亲节点ht[f]，若当前节点是双亲节点的左孩子节点，则在hcd[i]的cd数组中添加0，若当前节点是双亲节点的右孩子节点，则在hcd[i]的cd数组中添加1，将start域减1。再对双亲节点进行同样的操作，如此这样直到无双亲节点即到达树根节点，最后让start指向哈夫曼编码最开始的字符。
根据哈夫曼树求对应的哈夫曼编码的算法如下：
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for(i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/
{
hc.start=n;c=i;
f=ht[i].parent;
while(f!=-1) /*循环直到无双亲节点即到达树根节点*/
{
if (ht[f].lchild==c) /*当前节点是双亲节点的左孩子节点*/
hc.cd[hc.start--]='0';
else /*当前节点是双亲节点的右孩子节点*/
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent; /*再对双亲节点进行同样的操作*/
}
hc.start++; /*start指向哈夫曼编码最开始字符*/
hcd[i]=hc;
}
}
在建立哈夫曼树和哈夫曼编码后，输出各叶子节点哈夫曼编码的算法如下：
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k;
double sum=0,m=0;
int j;
printf("输出哈夫曼编码:\n"); /*输出哈夫曼编码*/
for(i=0;i<n;i++)
{
j=0;
printf(" %c:",ht[i].data);
for(k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
}