快捷搜索:

哈夫曼树详细讲解(带例题和C语言代码实现——全注释)

哈夫曼树详细讲解(带例题和C语言代码实现——全注释)

  1. 定义
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)
  1. 计算公式
树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+WnLn) ,N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n)。 可以证明哈夫曼树的WPL是最小的
  1. 运算过程
一、对给定的n个权值{W1,W2,W3,…,Wi,…,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,…,Ti,…,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。) 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步,直到集合F中只有一棵二叉树为止
  1. 图解过程
  2. 例题讲解(重点) 如例:已知某通讯系统在通讯联络中只可能出现8中字符,其概率分别别是0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11, 试设计赫夫曼编码 根据所占比例列出权值解答 注:A是0111 一共有八个节点,则数组中需要构建的节点 m = 2*n – 1 则为15个 给八行生成树,余下的记录过程 最终结果:

C语言实现代码

(记录人的姓名,成绩,按照成绩作为权值编码将上文中字母作为名字,比例作为成绩(权值))
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define n  6//叶子结点数目
#define m  (2*n-1) //总结点数目,可证明
#define MAXVALUE 10000 //最大权值
#define MAXBIT 20 //哈夫曼编码最大长度
typedef struct{
	char name[5];
	int weight;
	int parent;
	int Lchild,Rchild;
}Htreetype;
typedef struct{
	int bit[n];//保存位串
	int start;//编码起始位置
	char name[5]; 
}Hcodetype;
void select(Htreetype tree[],int position,int *node1,int *node2);//选择两个权值最小的点(代价最小) 
void HuffmanTree(Htreetype t[]);//构造哈夫曼树,用到了select选择节点 
void HuffmanCode(Hcodetype code[],Htreetype tree[]);//开始编码 
void show(Htreetype tree[],Hcodetype code[]);//显示编码 
int main(){
	Htreetype tree[m];//有m个位置的空树
	Hcodetype code[n];//n个编码位置
	
	HuffmanCode(code,tree);//编码完成
	

	show(tree,code);//输出 
	
	return 0;
} 

void select(Htreetype tree[],int position,int *node1,int *node2){
	//tree是哈夫曼树 position是到 第几个节点之前的都要检索 node1 和node2 保存两个权值最小的节点的位置
	//一共n个待记录点,n -- m里面的是生成树的时候新根节点,里面放的是权值,当生成了新根节点,查找最小就要从头到新构成的位置
	*node1 = *node2 = 0;
	int min1,min2; 
	min1 = min2 = MAXVALUE;
	int i;
	for(i = 0; i < position; i++){
		if(tree[i].parent == -1){//如果没有父节点说明还没有成为树的一部分 
			if(tree[i].weight < min1){//维护min1 < min2 也就是 node1的权值小 
				min2 = min1;//min2记录min1的权值 
				min1 = tree[i].weight;//min1的值更新
				*node2 = *node1;//抛弃当前两个节点中大的那个重新记录 
				*node1 = i; 
			}else if(tree[i].weight < min2){//前面的min1没有这个小但是min2比这个小所以直接用min2记录,这样就不用对两个节点都比较之后才换节点 
				min2 = tree[i].weight;
				*node2 = i; 
			} 
			
		}
	}
}
void HuffmanTree(Htreetype tree[]){
	int i;//for循环的计数器
	int node1,node2;//找权值最小的两个节点位置
	node1 = node2 = 0;
	
	char name[5];//暂存姓名 
	int now_weight;//暂存权值 
	for(i = 0; i < m; i++){//一共n个节点,则需要构建m个点存储信息 m = (2*n - 1) 
		tree[i].weight = 0;//没有权值 
		tree[i].parent = -1;
		tree[i].Lchild = -1;
		tree[i].Rchild = -1;
	}
	
	printf("一共有%d个人
",n);//构造节点信息
	
	for(i = 0; i < n; i++){//输入基本信息 
		printf("请输入姓名:");
		scanf("%s",&name);
		printf("请输入成绩:");
		scanf("%d",&now_weight);
		strcpy(tree[i].name,name); 
		tree[i].weight = now_weight;
	}
	
	for(i = n; i < m; i++){//构造哈夫曼树 
		select(tree,i,&node1,&node2);//选好两个节点 
		tree[node1].parent = i;//选好的两个节点形成了树 
		tree[node2].parent = i;//生成的节点放在当前位置
		tree[i].Lchild = node1;//node1权值小,也就是左子树权值都小
		tree[i].Rchild = node2;
		tree[i].weight = tree[node1].weight + tree[node2].weight;//生成新树完成 
	}
}
void HuffmanCode(Hcodetype code[],Htreetype tree[]){//code存放每个节点的编码对应0 --- (n - 1)个节点编码 
	int i;//计数器
	
	int parent_position,now_position;
	
	Hcodetype cd;//暂时存放编码 
	
	HuffmanTree(tree);//构造好霍夫曼树了在 tree里面
	
	for(i = 0; i < n; i++){//给n个节点编码 
		cd.start = n;//最长为n
		strcpy(cd.name,tree[i].name);//将名字也放进里面,可省略换其余方式输出
		now_position = i;//从每个节点向上 
		parent_position = tree[i].parent;//找到对应的父节点看自己当前编码为0还是1
		while(parent_position != -1){//没有到最底层的树
			cd.start--;
			if(tree[parent_position].Lchild == now_position){//当前位置的是父节点的左孩子则为0 
				cd.bit[cd.start] = 0;
			}else
				cd.bit[cd.start] = 1;
				
			now_position = parent_position;//向上移动 一定要移动 
			parent_position = tree[now_position].parent;
		} 
	
	code[i] = cd;//对第i个节点编码完成后放进code中 	 
		 
	} 
} 
void show(Htreetype tree[],Hcodetype code[]){//显示编码 
	int i,j;//计数器
	for(i = 0; i < n; i++){
		printf("%s          ",code[i].name);
		for(j = code[i].start; j < n; j++)
			printf("%c ",code[i].bit[j]);
		
		printf("
");
	} 
}

输出结果

与贴图不同的原因在于此代码将同级较小权值的字母放在了左面
经验分享 程序员 微信小程序 职场和发展