[数据结构与算法]哈夫曼树和哈夫曼编码解析，附源码（C实现）

1.哈夫曼树

1.1概念

通俗来讲，就是在一堆数字中，选取最小的两个当叶子节点，他们的加和为他们的父结点。

如图：

至于怎么构造这看自己心情，因为二叉树得到构造不唯一，这也是它同权不同构的特点。如果是字符A,B,C,D....就看每种字符出现的频率！

1.2创建哈夫曼树

1.21 哈夫曼树结构

typedef struct {
	int weight;
	int parent,lchild,rchild;
}HTNode,HuffmanTree[M+1];

1.22 挑选最小两个权值函数

判断中，父节点的判断起筛选作用，目的是排除已经选过的值

typedef struct {   //定义一个结构体  更直观
	int falg1;
	int falg2;
}MIN;

//挑选 2 个权值最小的结点
MIN select (HuffmanTree ht,int len){
	int k=1;
	MIN check; 
	int min1,min2,falg1,falg2;
	min1=100;
	min2=100;
	//目的是 s1 的权值要不大于 s2 的权值
	for(k;k<=len;k++){
		if((ht[k].weight)<min1&&ht[k].parent==0){  //父节点值得判断起到筛选在集合中选过和没选过得值
			min1=ht[k].weight;
			falg1=k;
		}
	}
	for(int i=1;i<=len;i++)
	{
		if(ht[i].parent==0&&(ht[i].weight<min2)&&(i!=falg1))
		{
			min2=ht[i].weight;
			falg2=i;
	}
} //这里采用结构体的办法   更直观 
	check.falg1=falg1;
	check.falg2=falg2;
	return check;
}

1.23 建立哈夫曼树

//建立哈夫曼树
void CreateHuffmanTree(HuffmanTree &ht,int w[],int n)
{	MIN flag;
	int m=2*n-1;
	int i;
	//初始化
	for(i=1;i<=n;i++){
		ht[i]={w[i-1],0,0,0};
	} 
	for(i=n+1;i<=m;i++){
		ht[i]={0,0,0,0};
	}
	//从第n+1个元素开始创建
	for(i=n+1;i<=m;i++)
	{
		flag=select(ht,i-1);
		ht[i].weight=ht[flag.falg1].weight+ht[flag.falg2].weight;  //权值相加
		ht[i].lchild=flag.falg1;
		ht[i].rchild=flag.falg2;
		ht[flag.falg1].parent=i;
		ht[flag.falg2].parent=i;
	 } 
 } 

1.24 输出哈夫曼树

//输出哈夫曼树
 void show(HuffmanTree ht,int num){
 	for(int i=1;i<=num;i++)
 	{
 		printf("\n结点序号%d，权值为%d,父节点为 %d,左孩子结点为%d,右孩子结点为 %d",i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
	}
 } 

?2.哈夫曼编码

首先得用到这个玩意：

#include<string.h>

2.1创建

//哈夫曼编码的实现
void Huffmanbianma(HuffmanTree ht,Huffmancode hc,int n)

//从叶子节点到根逆向求各叶子结点的编码 
{
	char *cd;
	int c,p;
	int start;
	cd=(char *)malloc(n*sizeof(char)); //临时编码数组
	cd[n-1]='\0';  //从后往前逐位求编码，最后一位是结束符先放
	for(int i=1;i<=n;i++)
	{
		start=n-1;  //因为是逆序，所以指针start从最后开始 
		c=i;        //当前结点，因为后面要进行指针的修改 
		p=ht[i].parent;  //取当前结点的父节点
		while(p!=0)
		{
			--start;
			if(ht[p].lchild==c)
			{
				cd[start]='0';  //左分支0  
			}else{
				cd[start]='1';   //右分支 1 
			}
			c=p; p=ht[p].parent;  //网上一层;	
		}
		hc[i]=(char *)malloc((n-start)*sizeof(char)); 
		strcpy(hc[i],&cd[start]);	
	}
	free(cd);	 
}

2.2 遍历

//遍历哈夫曼编码,也就是译码 
void TraverseCoding(Huffmancode HC, int n) {
	for (int i = 1; i <= n; ++i) {
		printf("哈夫曼编码:");
		puts(*(HC + i));
	}
}

因为没时间做讲解，代码过程都可以实现，所有创建过程我是直接定义数组，因为省事~~~~