哈夫曼树的构造过程及算法实现

一、哈夫曼树的构造过程

（1）根据给定的n个权值{w1,w2,...,wn}，构造n棵只有根节点的二叉树，这n棵二叉树构成森林F。

（2）在森林F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。

（3）在森林F中删除这两棵树，同时将新得到的二叉树加入F中。

（4）重复（2）和（3），直到F只含一棵树为止。这棵树便是哈夫曼树。

例：给定权值2,2,3,5,6

二、哈夫曼树的算法实现

由于哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的二维数组中。

1、树中每个节点要包含其双亲信息和孩子结点的信息。

typedef struct{
	int wei,par,lch,rch;
}HT;

2、初始化数组，将数组中所有parent、lchild、rchild置为0。

void Init(HT ht[]){
	for(int i=1;i<SIZE;i++){
		ht[i].par=ht[i].rch=ht[i].lch=0;
	}
}

3、构建哈夫曼树，其中1--n存储初始结点权重，n+1--2n-1存储存储权值最小的两个根节点之和，并更新parent、lchild、rchild，存储序号。

void Create(HT ht[],int n){
	for(int i=n+1;i<=2*n-1;i++){
		int s1=0,s2=0,min1=INF,min2=INF;
		for(int j=1;j<i;j++){//找到两个最小权重 
			if(ht[j].par==0){
				if(min1>ht[j].wei){
					min2=min1;min1=ht[j].wei;
					s2=s1;s1=j;
				}else if(min2>ht[j].wei){
					min2=ht[j].wei;
					s2=j;
		    //最小的权重存入min1，第二小的权重存入了min2
			//最小权重的序号存入s1，第二小权重的序号存入s2 
				}
			}
		}
		ht[s1].par=ht[s2].par=i;
		//两个最小权重结点父节点设置为当前节点 
		ht[i].wei=ht[s1].wei+ht[s2].wei;
		//当前节点权重为两个最小权重之和
		ht[i].lch=s1;ht[i].rch=s2;
		//设置当前节点的左右孩子 
	}
} 

4、输出哈夫曼结构

void Out(HT ht[],int n){
	for(int i=1;i<=2*n-1;i++){
		printf("%d:%5d%5d%5d%5d\n",i,ht[i].wei,ht[i].par,ht[i].lch,ht[i].rch);
	}
} 

5、主函数

int main(){
	HT ht[SIZE];//定义 
	Init(ht);//初始化
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&ht[i].wei);
	}
	Create(ht,n);
	Out(ht,n);
	return 0;
}

6、全部代码

#include<stdio.h>
#define SIZE 101
#define INF 32767
//定义结构体 
typedef struct{
	int wei,par,lch,rch;//结点的权重、父节点、左右孩子 
}HT;
//初始化数组
void Init(HT ht[]){
	for(int i=1;i<SIZE;i++){
		ht[i].par=ht[i].rch=ht[i].lch=0;
		//初始化父节点、左右孩子初值为0 
	}
}
//构建哈夫曼树
void Create(HT ht[],int n){
	for(int i=n+1;i<=2*n-1;i++){
		int s1=0,s2=0,min1=INF,min2=INF;
		for(int j=1;j<i;j++){//找到两个最小权重 
			if(ht[j].par==0){
				if(min1>ht[j].wei){
					min2=min1;min1=ht[j].wei;
					s2=s1;s1=j;
				}else if(min2>ht[j].wei){
					min2=ht[j].wei;
					s2=j;
		    //最小的权重存入min1，第二小的权重存入了min2
			//最小权重的序号存入s1，第二小权重的序号存入s2 
				}
			}
		}
		ht[s1].par=ht[s2].par=i;
		//两个最小权重结点父节点设置为当前节点 
		ht[i].wei=ht[s1].wei+ht[s2].wei;
		//当前节点权重为两个最小权重之和
		ht[i].lch=s1;ht[i].rch=s2;
		//设置当前节点的左右孩子 
	}
} 
//输出哈夫曼树的结构
void Out(HT ht[],int n){
	for(int i=1;i<=2*n-1;i++){
		printf("%d:%5d%5d%5d%5d\n",i,ht[i].wei,ht[i].par,ht[i].lch,ht[i].rch);
	}
} 
int main(){
	HT ht[SIZE];//定义 
	Init(ht);//初始化
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&ht[i].wei);
	}
	Create(ht,n);
	Out(ht,n);
	return 0;
}