【数据结构】哈夫曼树及哈夫曼编码实现（C语言）

JamesB · 发表于 2023-2-19 14:33

1. 哈夫曼树

1.1 基本概念

路径：指从根结点到该结点的分支序列。
路径长度：指根结点到该结点所经过的分支数目。
结点的带权路径长度：从树根到某一结点的路径长度与该结点的权的乘积。
树的带权路径长度(WPL)：树中从根到所有叶子结点的各个带权路径长度之和。

哈夫曼树是由 n 个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树，又称最优二叉树。如上图中第三棵树就是一棵哈夫曼树。
1.2 构造哈夫曼树

构造哈夫曼树的算法步骤：
① 初始化：用给定的 n 个权值{w1,w2,…,wn}构造 n 棵二叉树并构成的森林F={T1,T2,…,Tn}，其中每一棵二叉树Ti（1<=i<=n）都只有一个权值为 wi 的根结点，其左、右子树为空。
② 找最小树：在森林 F 中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根结点权值为其左、右子树的根结点权值之和。
③ 删除与加入：从 F 中删除被选中的那两棵二叉树，同时把新构成的二叉树加入到森林 F 中。
④ 判断：重复②、③操作，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树就是哈夫曼树。
简单的说就是先选择权小的，所以权小的结点被放置在树的较深层，而权较大的离根较近，这样一来所构成的哈夫曼树就具有最小带权路径长度。
例如给定5个权值{2，3，5，7，8}，构造过程如下：

注意：由于未规定左右子树顺序，因此哈夫曼树不唯一，但树的最小带权路径长度唯一。如下图两棵树都是根据5个权值{2，3，5，7，8}构造的哈夫曼树：

1.3 哈夫曼树的类型定义

哈夫曼树是一种二叉树，其中没有度为1的结点，因此一棵有 n 个叶子的哈夫曼树共有 2n-1 个结点，可以用一个大小为 2n-1 的一维数组来存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。

/*哈夫曼树的类型定义*/#defineN30//叶子结点的最大值#defineM2* N -1//所有结点的最大值typedefstruct{int weight;//结点的权值int parent;//双亲的下标int LChild;//左孩子结点的下标int RChild;//右孩子结点的下标}HTNode, HuffmanTree[M +1];//HuffmanTree是一个结构数组类型，0号单元不用

复制代码

1.4 哈夫曼树创建的算法实现

基于上文中的构造哈夫曼树的步骤，代码如下：

/*在ht[1]至ht[n]的范围内选择两个parent为0且weight最小的结点，其序号分别赋给s1，s2*/voidSelect(HuffmanTree ht,int n,int* s1,int* s2){int i, min1 = MAX, min2 = MAX;*s1 =0;*s2 =0;for(i =1; i <= n; i++){if(ht[i].parent ==0){if(ht[i].weight < min1){
min2 = min1;*s2 =*s1;
min1 = ht[i].weight;*s1 = i;}elseif(ht[i].weight < min2){
min2 = ht[i].weight;*s2 = i;}}}}/*创建哈夫曼树算法*/voidCrtHuffmanTree(HuffmanTree ht,int w[],int n){//构造哈夫曼树ht[M+1],w[]存放n个权值int i;for(i =1; i <= n; i++){//1至n号单元存放叶子结点，初始化
ht[i].weight = w[i -1];
ht[i].parent =0;
ht[i].LChild =0;
ht[i].RChild =0;}int m =2* n -1;//所有结点总数for(i = n +1; i <= m; i++){//n+1至m号单元存放非叶结点，初始化
ht[i].weight =0;
ht[i].parent =0;
ht[i].LChild =0;
ht[i].RChild =0;}/*初始化完毕，开始创建非叶结点*/int s1, s2;for(i = n +1; i <= m; i++){//创建非叶结点，建哈夫曼树Select(ht, i -1,&s1,&s2);//在ht[1]至ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋给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;}}

复制代码

2. 哈夫曼编码实现

2.1 哈夫曼编码

对一棵具有n个叶子结点的哈夫曼树，若对树中的每个左分支赋0，右分支赋1（或左1右0），则从根到每个叶子的通路上，各个分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。哈夫曼编码是最优前缀编码，能使各种报文对应的二进制串的平均长度最短。
例如要传送数据“state,seat,act,tea,cat,set,a,eat”，先统计各个字符出现的次数：

字符	c	s	e	a	t
字符出现的次数	2	3	5	7	8

将出现次数当作权构造哈夫曼树，并按左0右1规则对分支赋值：

则各字符的哈夫曼编码为：

字符	c	s	e	a	t
字符出现的次数	2	3	5	7	8
哈夫曼编码	010	011	00	10	11

可以看出使用频率越高的字符编码长度越短。
哈夫曼编码的代码实现：

/*哈夫曼编码*/voidCrtHuffmanCode(HuffmanTree ht,int n){//从叶子结点到根，逆向求每个叶子结点(共n个)对应的哈夫曼编码char* cd;
cd =(char*)malloc(n *sizeof(char));//分配当前编码的工作空间
cd[n -1]='\0';//从右向左逐位存放编码，首先存放编码结束符for(int i =1; i <= n; i++){//求n个叶子结点对应的哈夫曼编码int start = n -1, c = i, p = ht[i].parent;while(p !=0){--start;if(ht[p].LChild == c)//左分支标0
cd[start]='0';else
cd[start]='1';//右分支标1
c = p;//向上倒堆
p = ht[p].parent;}for(int j =0; j < n; j++){if(cd[j]=='0'|| cd[j]=='1'){printf("%c", cd[j]);//编码输出}}memset(cd,0, n);}}

复制代码

2.2 完整代码

/*哈夫曼树及哈夫曼编码实现*/#include<stdio.h>#include<malloc.h>#include<string.h>#defineN30//叶子结点的最大值#defineM2* N -1//所有结点的最大值#defineMAX99999/*哈夫曼树的类型定义*/typedefstruct{int weight;//结点的权值int parent;//双亲的下标int LChild;//左孩子结点的下标int RChild;//右孩子结点的下标}HTNode, HuffmanTree[M +1];//HuffmanTree是一个结构数组类型，0号单元不用
HuffmanTree ht;/*在ht[1]至ht[n]的范围内选择两个parent为0且weight最小的结点，其序号分别赋给s1，s2*/voidSelect(HuffmanTree ht,int n,int* s1,int* s2){int i, min1 = MAX, min2 = MAX;*s1 =0;*s2 =0;for(i =1; i <= n; i++){if(ht[i].parent ==0){if(ht[i].weight < min1){
min2 = min1;*s2 =*s1;
min1 = ht[i].weight;*s1 = i;}elseif(ht[i].weight < min2){
min2 = ht[i].weight;*s2 = i;}}}}/*创建哈夫曼树算法*/voidCrtHuffmanTree(HuffmanTree ht,int w[],int n){//构造哈夫曼树ht[M+1],w[]存放n个权值int i;for(i =1; i <= n; i++){//1至n号单元存放叶子结点，初始化
ht[i].weight = w[i -1];
ht[i].parent =0;
ht[i].LChild =0;
ht[i].RChild =0;}int m =2* n -1;//所有结点总数for(i = n +1; i <= m; i++){//n+1至m号单元存放非叶结点，初始化
ht[i].weight =0;
ht[i].parent =0;
ht[i].LChild =0;
ht[i].RChild =0;}/*初始化完毕，开始创建非叶结点*/int s1, s2;for(i = n +1; i <= m; i++){//创建非叶结点，建哈夫曼树Select(ht, i -1,&s1,&s2);//在ht[1]至ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋给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;}}/*哈夫曼编码*/voidCrtHuffmanCode(HuffmanTree ht,int n,char str[]){//从叶子结点到根，逆向求每个叶子结点(共n个)对应的哈夫曼编码char* cd;
cd =(char*)malloc(n *sizeof(char));//分配当前编码的工作空间for(int i =1; i <= n; i++){//求n个叶子结点对应的哈夫曼编码int start = n -1, c = i, p = ht[i].parent;while(p !=0){--start;if(ht[p].LChild == c)//左分支标0
cd[start]='0';else
cd[start]='1';//右分支标1
c = p;//向上倒堆
p = ht[p].parent;}printf("%c的编码：", str[i -1]);for(int j =0; j < n; j++){if(cd[j]=='0'|| cd[j]=='1'){printf("%c", cd[j]);//编码输出}}printf("\n");memset(cd,-1, n);}}intmain(){int i, w[5]={2,3,5,7,8};char str[5]={'c','s','e','a','t'};CrtHuffmanTree(ht, w,5);printf("哈夫曼树各结点值：\n");for(i =1; i <=9; i++)printf("%d ", ht[i].weight);printf("\n");CrtHuffmanCode(ht,5, str);return0;}

复制代码

2.3 运行结果

参考：耿国华《数据结构——用C语言描述（第二版）》
更多数据结构内容关注我的《数据结构》专栏：https://blog.csdn.net/weixin_51450101/category_11514538.html?spm=1001.2014.3001.5482

		自动登录	找回密码
密码			立即注册

【数据结构】哈夫曼树及哈夫曼编码实现（C语言）

本帖子中包含更多资源