摘要：哈夫曼树是带权路径长度（WPL）最小的二叉树，通过对哈夫曼算法的研究，提出一种求取哈夫曼树带权路径长度的计算方法和应用。
关键词：哈夫曼算法、二叉树、WPL、编码
1 引言：
哈夫曼树是一种特殊的二叉树，又称最优二叉树：假设有一组（无序）实数｛w1,w2,w3,w4,…,wm｝，现要构造一棵以wi（i=1，2，3，4…，m）为权的m个外部结点的扩充二叉树，使得带权的外部路径长度WPL最小。
满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。
若l表示从根到第i个外部结点的路径长度，m为外部结点的个数，wi 为第i个外部结点的权值，则有WPL=∑wili（0<i<=m）。
2 正文：
2.1 算法的基本思想：
（1）由给定的m个权值｛w1,w2,…wm｝，构造一棵由空二叉树扩充得到的扩充二叉树｛T1,T2,…,Tm｝。
每个Ti（1<i<m）只有一个外部结点（也是根结点），它
的权值置为w1。
（2）在已经构造的所有扩充二叉树中，选取根结点的权值最小和次最小的两棵，将它们作为左、右子树，构造成一棵新的扩充二叉树，它的根结点（新建立
的内部结点）的权值为其左、右子树根结点权值之和。
（3）重复执行步骤（2），每次都使扩充二叉树的个数减少一，当只剩下一棵扩充二叉树时，它便是所要构造的哈夫曼树。
一棵二叉树要使其WPL最小，必须使权值的外部结点离根越近，权值越小的离根越远。
2.1.1 程序实现：
/*哈夫曼树的构造方法*/
#include<stdlib.h>
#include<stdio.h>
#define MAXINT 50
#define MAXNUM 50 /* 数组w中最多容纳的元素个数，注意m<=MAXNUM */
#define MAXNODE 100 /* 哈夫曼树中的最大结点数，注意2*m-1<MAXNODE */
structHtNode { /* 哈夫曼树结点的结构*/
intww;
intparent,llink,rlink;
};
structHtTree {
int root;/* 哈夫曼树根在数组中的下标*/
structHtNodeht[MAXNODE];
};
typedefstructHtTree *PHtTree; /* 哈夫曼树类型的指针类型*/
/* 构造具有m个叶结点的哈夫曼树*/
PHtTreehuffman(int m, int *w) {
PHtTreepht;
int i, j, x1, x2, m1, m2;
pht = (PHtTree)malloc(sizeof(structHtTree)); /* 创建空哈夫曼树*/
if (pht == NULL) {
printf("Out of space!! \n");
returnpht;
}
for (i = 0; i < 2*m-1; i++) {/* 置初态*/
pht->ht[i].llink = -1;
pht->ht[i].rlink = -1;
pht->ht[i].parent = -1;
if (i < m)
pht->ht[i].ww = w[i];
else
pht->ht[i].ww = -1;
}
for ( i = 0; i < m-1; i++) {/* 每循环一次构造一个内部结点*/
m1 = MAXINT;
m2 = MAXINT;/* 相关变量赋初值*/
x1 = -1;
x2 = -1;
for (j = 0; j <m+i; j++) /* 找两个最小权的无父结点的结点*/ if (pht->ht[j].ww< m1 &&pht->ht[j].parent == -1) {
m2 = m1;
x2 = x1;
m1 = pht->ht[j].ww;
x1 = j;
}
else if (pht->ht[j].ww< m2 &&pht->ht[j].parent == -1) {
m2 = pht->ht[j].ww;
x2 = j;
}
pht->ht[x1].parent = m+i; /* 构造一个内部结点*/
pht->ht[x2].parent = m+i;
pht->ht[m+i].ww = m1+m2;
pht->ht[m+i].llink = x1;
pht->ht[m+i].rlink = x2;
pht->root = m+i;
}
returnpht;
}
int main() {
int m = 0, j = 0, i = 0, parent = 0;
int* w;
PHtTreepht;
printf("please input m = ");/*输入外部结点个数*/
scanf("%d", &m);
if (m < 1) {
printf("m is not reasonable!\n");
return 1;
}
w = (int *)malloc(sizeof(int)*m);
if (w == NULL) {
printf("overflow!\n");
return 1;
}
printf("please input the %d numbers：\n",m);/*输入权值*/
for (j = 0; j < m; j++)
scanf("%d", w+j);
pht = huffman(m, w);
for (j = 0; j < m; j++) {
printf("the Reverse code of the %d node is:", j+1);/*得到的编码应倒过来*/
i = j;
while (pht->ht[i].parent != -1) {
parent = pht->ht[i].parent;
if (pht->ht[parent].llink == i)
printf("0");
else
printf("1");
i = parent;
}
printf("\n");
}
return 0;
}
2.1.2 例子：
下面以w=｛2,3,5,7,11,13,17,17,19,23,29,31,37,41｝,按照上述方法构造出来的哈夫曼树如下图所示：
用哈夫曼算法构造的哈夫曼树
2.2 哈夫曼树的应用：
2.2.1 哈夫曼编码：
哈夫曼树可以直接应用于通信及数据传送中的二进制编码。
设：
D=｛d1,d2,d3…dn｝为需要编码的字符集合。
W=｛w1,w2,w3,…wn｝为D中各字符出现的频率。
现要对D中的字符进行二进制编码，使得：
（1）按给出的编码传输文件时，通信编码的总长最短。
（2）若di不等于dj，则di的编码不可能是dj的编码的开始部分（前缀）。
满足上述要求的二进制编码称为最优前缀编码。
上述要求的第一条是为了提高传输的速度，第二条是为了保证传输的信息在译码时无二性，所以在字符的编码中间不需要添加任意的分割符。
对于这个问题，可以利用哈夫曼树加以解决：用d1,d2,d3…dn作为外部结点，用w1,w2,w3…wn作为外部结点的权，构造哈夫曼树。
在哈夫曼树中把从每个结点引向其左子结点的边标上二进制数“0”，把从每个结点引向右子节点的边标上二进制数“1”，从根到每个叶结点的路径上的二进制数连接起来，就是这个叶结点所代表字符的最优前缀编码。
通常把这种编码称为哈夫曼编码。
例如：
D=｛d1,d2,d3,d4,d5,d6,d7,d8,d9,d10,d11,d12,d13｝
W=｛2,3,5,7,11,13,17,19,23,29,31,37,41｝
利用哈夫曼算法构造出如下图所示的哈夫曼树：
用于编码的哈夫曼树
从而得到各字符的编码为：
d1:1011110 d2:1011111
d3:101110 d4:10110
d5:0100 d6:0101
d7:1010 d8:000
d9:001 d10:011
d11:100 d12:110
d13:111
编码的结果是，出现频率大的字符其编码较短，出现频率较小的字符其编码较长。
3 小结：
由于哈夫曼编码是一种最优前缀编码，所以在解码时也十分容易。
只要从二叉树的根结点开始，用需要解码的二进制位串从头开始与二叉树根结点到子结点边上标的0、1相匹配，确定一条到达树叶结点的路径。
一旦达到树叶结点，则译出一个字符。
然后再回到根结点，从二进制串中的下一位开始继续解码。
参考文献：
【1】张乃孝. (2011.6). 算法与数据结构--C语言描述(第3版). 高等教育出版社.。