博客

一、定义

哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

二、代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 30
#define Max 2*N-1

typedef char **HuffmanCode;
typedef struct HTNode
{
	double weight;
	int parent;
	int lchild,rchild;
}HTNode,*HuffmanTree;
//在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1权值小于s2 
void Select(HuffmanTree HT,int n,int s1,int s2)
{
	int i = 1;
	int min;//找第一个最小值 
	for(;i<=n;i++)
	{
		if(HT[i].parent == 0)
		{
			min = i;
			break;
		}
		for(i = min+1;i<=n;i++)
		{
			if(HT[i].parent == 0 && HT[i].weight < HT[min].weight )
			min = i;
		}
		s1 = min;//第一个最小值赋值给s2
		//寻找第二个最小值
		for(i = 1;i <= n;i++)
		{
			if(HT[i].parent == 0 && i != s1)
			{
				min = i;
				break;
			}
		}
		for(i = min+1;i<=n;i++)
		{
			if(HT[i].weight <HT[min].weight &&HT[i].parent == 0 && i!=s1)
			min = i;
		}
		s2 = min;
	}
}
//构建哈夫曼树
void CreateHuff(HuffmanTree HT,double *w,int n)
{
	int m = 2*n-1;
	HT = (HuffmanTree)malloc(2*n*sizeof(HTNode));
	int i;
	for(i = 1;i <= n;i++)
	{
		HT[i].weight = w[i-1];//赋权值 
	}
	for(i = n+1;i <= n;i++)
	{
		int s1,s2;
		Select(HT,i-1,s1,s2);
		HT[i].weight = HT[s1].weight +HT[s2].weight ;
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;	
	}
	printf("哈夫曼数为：\n");
	printf("下标   权值   父结点   左孩子   右孩子\n");
	printf("0                                     \n");
	for(i = 1;i <= m;i++)
	{
		printf("%-4d  %lf  %d %d %d\n",i,HT[i].weight ,HT[i].parent ,HT[i].lchild ,HT[i].rchild );
	} 
	printf("\n");
} 
//生成哈夫曼编码
void HuffCoding(HuffmanTree HT,char HC,int n)
{
	int i;
	HC = (HuffmanCode)malloc(sizeof(char*)*(n+1));
	char* code = (char*)malloc(sizeof(char)*n);
	code[n-1] = '\0';
	for(i = 1;i<=n;i++)
	{
		int start = n-1;
		int c = i;
		int p =HT[c].parent ;
		while(p)
		{
			if(HT[p].lchild == c)
			code[--start]= '\0';
			else
			code[--start]= '\1';
			c = p;
			p = HT[c].parent ;
		}
		HC[i] = (char*)malloc(sizeof(char)*(n-start));
		strcpy(HC[i],&code[start]);
	}
	free(code);
 } 
 int main()
 {
 	int i;
 	int n= 0;
 	printf("请输入数据个数：");
 	scanf("%d",&n);
 	char* w = (char*)malloc(sizeof(char)*n);
 	if(w==NULL)
 	{
 		printf("malloc fail\n");
 		exit(-1);
	 }
	 printf("请输入数据:");
	 for(i = 0;i<n;i++)
	 {
	 	scanf("%lf",&w[i]);
	  } 
	  HuffmanTree HT;
	  CreateHuff(HT,w,n);
	  char HC;
	  HuffCoding(HT,HC,N);
	  for(i = 1;i<=n;i++)
	  {
	  	printf("数据%.2lf的编码为%s\n",HT[i].weight ,HC[i]);
	  }
	  free(w);
	  return 0;
}
	
	

三、运行结果