数组实现哈夫曼树及哈夫曼编码

基本介绍:http://baike.baidu.com/link?url=DDUm7qBwh4XVGlhskrXjpQZx6mu74iy-54mkIBMUIME8o22OKvbi61yHxOz0Ljm5YekqESS70n3rTKSHqPu3Z_

简单的图示介绍:

hewie^_^

用数组实现的哈夫曼树及哈夫曼编码:

#include <cstdio>
#define N 5
#define M 2*N-1
#define MaxInt 666666
//建成的哈夫曼树存放在HTree数组中
//且通过数组元素下标来确定父节点,左节点,右节点
struct 
{
	int weight;//权
	int left;//左节点
	int right;//右节点
	int parent;//父节点
}HTree[M];


//对一篇文章编码,我们假设已经得到了每个字符(c)及它们的出现权重(weight)
struct 
{
	char c;
	int weight;
	int bit[100];//存储每个字符编码的逆序
	int code[100];//存储每个字符的编码
	int len;//存储每个字符的编码的长度
}cc[N]={{'a',1,{0},{0},0},{'b',2,{0},{0},0},{'c',3,{0},{0},0},{'d',4,{0},{0},0},{'e',5,{0},{0},0}};


//初始化成森林
void InitHTree()
{
	int i;
	for(i=0;i<M;i++)
	{
		if(i<N)
		HTree[i].weight=cc[i].weight;
		else
		HTree[i].weight=0;
		HTree[i].left=HTree[i].right=HTree[i].parent=-1;//数组元素以0为第一元素,故将其初始化为-1
	}
}


//建哈夫曼树
void BuidHTree()
{
	int i,j,x,y;
	int min;
	for(i=0;i<N-1;i++)
	{
		min=MaxInt;
		//找最小的两个元素x,y
		for(j=0;j<M;j++)
		{
			if(HTree[j].parent==-1&&HTree[j].weight>0&&min>HTree[j].weight)
			{
				min=HTree[j].weight;
				x=j;
			}
		}
		min=MaxInt;
		for(j=0;j<M;j++)
		{
			if(HTree[j].parent==-1&&HTree[j].weight>0&&j!=x&&min>HTree[j].weight)
			{
				min=HTree[j].weight;
				y=j;
			}
		}
		HTree[x].parent=HTree[y].parent=i+N;//父节点为HTree[i+N]
		HTree[i+N].left=x;
		HTree[i+N].right=y;
		HTree[i+N].weight=HTree[x].weight+HTree[y].weight;
	}
}

//哈夫曼编码:每一个字符都得到一个二进制编码
void HuffCode()
{
	int i,j;
	int pos,child,parent;
	for(i=0;i<N;i++)
	{
		pos=0;
		child=i;
		parent=HTree[i].parent;
		while(parent!=-1)
		{
			if(HTree[parent].left==child)
			cc[i].bit[pos]=0;
			else
			cc[i].bit[pos]=1;
			pos++;
			child=parent;
			parent=HTree[parent].parent;
		}
		cc[i].len=pos;

		//将逆序的结果存到正序中
		pos--;
		for(j=0;j<cc[i].len;j++,pos--)
		cc[i].code[j]=cc[i].bit[pos];
	}
}

int main()
{
	int i,j;
	//初始化森林
	InitHTree();
	//建哈夫曼树
	BuidHTree();
	//测试建树结果
	for(i=0;i<M;i++)
	printf("%d ",HTree[i].weight);
	printf("\n");
	//哈夫曼编码
	HuffCode();
	//测试编码结果:每一个字符都得到一个特定的二进制编码
	for(i=0;i<N;i++)
	{
		printf("%c:",cc[i].c);
		for(j=0;j<cc[i].len;j++)
		printf("%d ",cc[i].code[j]);
		printf("\n");
	}
	return 0;
}

原文地址:http://www.hewie.cn/blog/Home/Article/article/article_id/3.html