哈夫曼树的构造规则_哈夫曼树的构造_哈夫曼树的构造方法

在给定权值为w 1 ， w 2… w n的 n 个叶结点所构成的所有扩充二元树中，WPL = ∑wj · l j最小的称为huffman树

哈夫曼树的构造算法：

1 由给定的 n 个权值 {w0, w1, w2, …, wn-1}，构造具有 n 棵扩充二元树的森林 F = { T0, T1, T2, …, Tn-1 }，

其中每棵扩充二叉树 Ti 只有一个带权值 wi 的根结点, 其左、右子树均为空。

2重复以下步骤, 直到 F 中仅剩下一棵二元树为止：

① 在 F 中选取两棵根结点的权值最小的扩充二元树, 做为左、右子树构造一棵新的二元树，且

置新的二元树的根结点的权值为其左、右子树上根结点的权值之和。哈夫曼树的构造

② 在 F 中删去这两棵二元树。

③ 把新的二元树加入 F。哈夫曼树的构造

*/

#include<stdio.h>

#define n 5

#define m 2*n-1

typedef struct {

double weight;

int lchild;

int rchild;

int parent;

}HTNODE;

/*静态三叉链表表示，又是游标表示即使用整型变量标记/指向节点*/

typedef HTNODE HuffmanT[m];

/*初始值，依据教材的例子，存放相应数据P116*/

void InitHT(HuffmanT T)

{

/*每个节点就是一个树，因此是森林F，共有n棵二叉树*/

T[0].weight = 0.12;T[0].parent=-1;T[0].lchild=-1;T[0].rchild=-1;/*书中代码从1开始，不良习惯！*/

T[1].weight = 0.40;T[1].parent=-1;T[1].lchild=-1;T[1].rchild=-1;

T[2].weight = 0.15;T[2].parent=-1;T[2].lchild=-1;T[2].rchild=-1;

T[3].weight = 0.08;T[3].parent=-1;T[3].lchild=-1;T[3].rchild=-1;

T[4].weight = 0.25;T[4].parent=-1;T[4].lchild=-1;T[4].rchild=-1;/*可以只存放前5个节点，后面的是为了与结果比较*/

T[5].weight = 0;T[5].parent=-1;T[5].lchild=-1;T[5].rchild=-1;

T[6].weight = 0;T[6].parent=-1;T[6].lchild=-1;T[6].rchild=-1;

T[7].weight = 0;T[7].parent=-1;T[7].lchild=-1;T[7].rchild=-1;

T[8].weight = 0;T[8].parent=-1;T[8].lchild=-1;T[8].rchild=-1;

/*打印HuffmanT[m]数组元素，每个元素是一个哈夫曼树的结构体*/

void PrintHT(HuffmanT T)

{

int i;

for(i=0;i<m;i++)

if(T[i].weight!=0)

printf("%d weight %3.2f parent %d lchild %d rchild %d\n",

i, T[i].weight, T[i].parent,T[i].lchild,T[i].rchild);

}

/*选取两个最小的权值节点，注意指针变量p1,p2的使用：比较自然*/

void SelectMin(HuffmanT T, int nn, int* p1, int* p2)

{

int i,j,temp;

for(i=0;i<=nn;i++)/*找到第一个没有合并的节点，取其位置i为*p1的初始值*/

if(T[i].parent == -1)

{

*p1=i;

break;

}

for(j=i+1;j<=nn;j++)/*找到在i的后面，第二个没有合并的节点，取其位置j为*p2的初始值*/

if(T[j].parent==-1)

{

*p2=j;

break;

}

for(i=0;i<=nn;i++)/*将位置*p1的权值依次与所有节点比较大小，得到最小的*/

if((T[*p1].weight >T[i].weight)/*取较小的*/

&&(T[i].parent==-1)/*没有合并或者合并后双亲指针为空的节点*/ &&(*p2!=i))/*? 与p2不同，取最小的两个节点! 正是因此，导致左右孩子错误 ?*/

*p1=i;

for(j=0;j<=nn;j++)/*同上*/

if((T[*p2].weight>T[j].weight)&&(T[j].parent==-1)&&(*p1!=j))

*p2=j;

/*书中没有此判断代码！确保左子树的权值小于右子树*/

if(T[*p1].weight>T[*p2].weight)

{

temp = *p1;

*p1=*p2;

*p2=temp;

}

}

/*第四版的教材，国家级精品课程还是这样，可怜中国IT，更可悲中国GIS！*/ void CreateHT(HuffmanT T)

{

int i,p1,p2;

InitHT(T);/*初始化*/

PrintHT(T);/*打印初始化后情况*/

for(i=n;i<m;i++)

{

SelectMin(T,i-1,&p1,&p2);/*选择两个最小权值,i-1 所以SelectMin函数内部循环取等*/

T[p1].parent = T[p2].parent = i+1;/*新节点的双亲指针，从n+1开始存放，与P118终态一致*/

T[i].lchild = p1+1;/*新节点的左孩子指针*/

T[i].rchild = p2+1;/*新节点的右孩子指针*/

T[i].parent = -1;/*新节点的双亲指针，可省*/

T[i].weight = T[p1].weight + T[p2].weight;/*新节点的权值*/

printf("===================%d===================\n",i); PrintHT(T);/*打印每次合并的情况*/

}

}

int main(void)

{

HuffmanT T;

printf("Huffman Tree initlization status\n");

CreateHT(T);

printf("Huffman Tree result status\n");

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-35222-1.html