哈夫曼算法

用C语言最简单的哈夫曼算法实现

#include <stdio.h>

#include <conio.h>

struct BinaryTree

{

long data;

int lchild,rchild;

};

//定义一个二叉树结构

void sort(struct BinaryTree cc[],int l,int r);

void xx(long kk,struct BinaryTree cc[]);

void zx(long kk,struct BinaryTree cc[]);

void hx(long kk,struct BinaryTree cc[]);

//对函数的声明

main(void)

{

struct BinaryTree Woods[101];

long i,j,n,xs,k;

scanf("%d",&n);

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

{

scanf("%d",&Woods.data);

Woods.lchild=0;

Woods.rchild=0;

} //依次读入权值

k=n;

xs=1;

--n;

while (k>1)

{

sort(Woods,xs,n+1);

Woods[n+2].data=Woods[xs].data+Woods[xs+1].data; //将根结点权值为左子树也右子树权值之和

Woods[n+2].lchild=xs; //对左子树和右子树的设置

Woods[n+2].rchild=xs+1;

++n;

xs=xs+2;

--k;

} //哈夫曼算法

printf("%s","preorder:");

xx(n+1,Woods);

printf("\n%s","inorder:");

zx(n+1,Woods);

printf("\n%s","postorder");

hx(n+1,Woods);

printf("\n"); //输出先序,中序,后序序列

getch();

}

//快速排序

void sort(struct BinaryTree cc[],int l,int r)

{

long x,y;

int i,j,rc,lc;

i=l;

j=r;

x=cc[(l+r)/2].data;

if (r<l)

return;

do

{

while(cc.data<x)

++i;

while(x<cc[j].data)

--j;

if (i<j)

{

y=cc.data;

rc=cc.rchild;

lc=cc.lchild;

cc.data=cc[j].data;

cc.lchild=cc[j].lchild;

cc.rchild=cc[j].rchild;

cc[j].data=y;

cc[j].lchild=lc;

cc[j].rchild=rc;

++i;

--j;

}

}

while(i>j);

if (i<r)

sort(cc,i,r);

if (j>l)

sort(cc,l,j);

}

//先序序列

void xx(long kk,struct BinaryTree cc[])

{

if (cc[kk].data!=0)

{

printf("%d%c",cc[kk].data,' ');

if (cc[kk].lchild!=0)

xx(cc[kk].lchild,cc);

if (cc[kk].rchild!=0)

xx(cc[kk].rchild,cc);

}

}

//中序序列

void zx(long kk,struct BinaryTree cc[])

{

if (cc[kk].data!=0)

{

if (cc[kk].lchild!=0)

zx(cc[kk].lchild,cc);

printf("%d%c",cc[kk].data,' ');

if (cc[kk].rchild!=0)

zx(cc[kk].rchild,cc);

}

}

//后序序列

void hx(long kk,struct BinaryTree cc[])

{

if (cc[kk].data!=0)

{

if (cc[kk].lchild!=0)

hx(cc[kk].lchild,cc);

if (cc[kk].rchild!=0)

hx(cc[kk].rchild,cc);

printf("%d%c",cc[kk].data,' ');

}

}

1.初始化: 根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根结点，左右子树均空。

2. 找最小树:在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

3. 删除与加入:在F中删除这两棵树，并将新的二叉树加入F中。

4. 判断:重复前两步(2和3)，直到F中只含有一棵树为止。该树即为哈夫曼树

从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F中的二叉树的"合并"，最终得到哈夫曼树。

在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，数组元素的结构形式如下:

其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为-1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是-1了。

构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。

下面给出哈夫曼树的构造算法。

const maxvalue= 10000; {定义最大权值}

maxleat=30; {定义哈夫曼树中叶子结点个数}

maxnode=maxleaf*2-1;

type HnodeType=record

weight: integer;

parent: integer;

lchild: integer;

rchild: integer;

end;

HuffArr:array[0..maxnode] of HnodeType;

var ……

procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼树的构造算法}

var i,j,m1,m2,x1,x2,n: integer;

begin

readln(n); {输入叶子结点个数}

for i:=0 to 2*n-1 do {数组HuffNode[ ]初始化}

begin

HuffNode.weight=0;

HuffNode.parent=-1;

HuffNode.lchild=-1;

HuffNode.rchild=-1;

end;

for i:=0 to n-1 do read(HuffNode.weight); {输入n个叶子结点的权值}

for i:=0 to n-1 do {构造哈夫曼树}

begin

m1:=MAXVALUE; m2:=MAXVALUE;

x1:=0; x2:=0;

for j:=0 to n i-1 do

if (HuffNode[j].weight

begin m2:=m1; x2:=x1;

m1:=HuffNode[j].weight; x1:=j;

end

else if (HuffNode[j].weight

begin m2:=HuffNode[j].weight; x2:=j; end;

{将找出的两棵子树合并为一棵子树}

HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;

HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;

HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;

end;

end;