哈夫曼算法的实现及应用

摘要：哈夫曼树是带权路径长度（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

2 正文：

2.1 算法的基本思想：

（1）由给定的m个权值｛w1,w2,…wm｝，构造一棵由空二叉树扩充得到的扩充二叉树｛T1,T2,…,Tm｝。每个Ti（1

的权值置为w1。

（2）在已经构造的所有扩充二叉树中，选取根结点的权值最小和次最小的两棵，将它们作为左、右子树，构造成一棵新的扩充二叉树，它的根结点（新建立

的内部结点）的权值为其左、右子树根结点权值之和。

（3）重复执行步骤（2），每次都使扩充二叉树的个数减少一，当只剩下一棵扩充二叉树时，它便是所要构造的哈夫曼树。

一棵二叉树要使其WPL最小，必须使权值的外部结点离根越近，权值越小的离根越远。2.1.1 程序实现：

/*哈夫曼树的构造方法*/

#include

#include

#define MAXINT 50

#define MAXNUM 50 /* 数组w中最多容纳的元素个数，注意m<=MAXNUM */

#define MAXNODE 100 /* 哈夫曼树中的最大结点数，注意2*m-1

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 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｝,按照上述方法构造出来的哈夫曼树如下图所示：