哈夫曼树的构造、编码生成与带权路径长度计算——基于C语言的实验实现与分析 P12114068王勇豪
P12114068 王勇豪
摘要
哈夫曼树是数据结构中基于贪心算法构建的最优二叉树，由其生成的哈夫曼编码是一种经典的前缀无损压缩编码，广泛应用于文件压缩、图像编码等领域。本文以课程实验题目为研究对象，首先阐述哈夫曼树、哈夫曼编码、带权路径长度 WPL 的基础理论；结合题目给定的构造规则与样例输入，完成完整的手工推导；基于实验所用 C 语言代码，详细分析结构体设计、节点选择、树构建、编码回溯、WPL 计算的核心逻辑；针对代码中存在的兼容性问题进行修复；最后通过样例验证程序正确性，分析代码优缺点并给出改进方向。
一、理论原理
1.1 基本概念
- 路径与路径长度：在二叉树中，从根节点到某一叶子节点所经过的边的数量，称为该叶子的路径长度。
- 带权路径长度（WPL）：所有叶子节点的权值×路径长度之和，公式：
(WPL=sum_{i=1}^n w_i cdot l_i)
其中(w_i)为字符权值，(l_i) 为对应路径长度。WPL越小，编码整体压缩效率越高。 - 哈夫曼树：给定一组带权叶子节点，通过每次合并权值最小的两个节点，最终得到的WPL最小的二叉树，又称最优二叉树。
- 哈夫曼编码：从根到叶子，左分支记0、右分支记1，得到的二进制编码；天然满足前缀码特性，无编码互为前缀，可直接用于无损编码。
1.2 题目规定的哈夫曼树构造规则
1.每次选取森林中权值最小的两个节点，合并为新父节点，父节点权值为两子节点权值之和；
2.权值较小的节点作为左孩子（编码0），权值较大作为右孩子（编码1）；
3.若权值相同，先输入（先出现）的节点优先作为左孩子。
1.3 哈夫曼算法核心思想
哈夫曼算法属于贪心算法：每一步只做当前局部最优选择（合并最小两个权值），最终得到全局最优解（WPL最小）。
二、样例推导过程
2.1 样例输入
plaintext
5
A 5
B 9
C 12
D 13
E 16
2.2 哈夫曼树手工构建
初始叶子节点：A (5)、B (9)、C (12)、D (13)、E (16)
第1次合并：最小两个 A (5)、B (9) → 父节点 N1 (14)
左 A (0)，右 B (1)
第2次合并：剩余 C (12)、D (13)、N1 (14)、E (16)
最小 C (12)、D (13) → 父节点 N2 (25)
左 C (0)，右 D (1)
第3次合并：剩余 N1 (14)、E (16)、N2 (25)
最小 N1 (14)、E (16) → 父节点 N3 (30)
左 N1 (0)，右 E (1)
第4次合并：剩余 N2 (25)、N3 (30)
合并为根节点 N4 (55)，左 N2 (0)，右 N3 (1)
2.3 字符编码推导
C：根→0→0 → 00
D：根→0→1 → 01
A：根→1→0→0 → 100
B：根→1→0→1 → 101
E：根→1→1 → 11
2.4 WPL 计算
begin{align} WPL &= 5times3 + 9times3 + 12times2 +13times2 +16times2 &= 15+27+24+26+32 &= 124 end{align}
与样例输出WPL=124完全一致。
三、C 语言代码实现与分析
3.1 原代码整体结构
程序分为6个核心部分：
- 结构体定义：哈夫曼树节点；
- Select函数：选出权值最小的两个节点；
- CreateHuff函数：构建哈夫曼树；
- GetCode函数：回溯生成哈夫曼编码；
- GetWPL函数：计算带权路径长度；
- main函数：输入、调度、输出。
3.2 原实验完整代码
#include<stdio.h>#include<string.h>#defineMAXSIZE200typedefstruct{chardata;intweight;intparent,lch,rch;}HTNode,HuffTree[MAXSIZE];charcode[MAXSIZE][MAXSIZE];intn;voidSelect(HuffTree T,intend,int*s1,int*s2){inti;// 变量提前定义intmin1=9999,min2=9999;*s1=*s2=-1;for(i=0;i<=end;i++){if(T[i].parent==-1&&T[i].weight<min1){min1=T[i].weight;*s1=i;}}for(i=0;i<=end;i++){if(T[i].parent==-1&&i!=*s1&&T[i].weight<min2){min2=T[i].weight;*s2=i;}}}voidCreateHuff(HuffTree T){intm=2*n-1,s1,s2,i;// i放开头for(i=0;i<m;i++){T[i].parent=-1;T[i].lch=-1;T[i].rch=-1;}for(i=n;i<m;i++){Select(T,i-1,&s1,&s2);T[s1].parent=i;T[s2].parent=i;T[i].lch=s1;T[i].rch=s2;T[i].weight=T[s1].weight+T[s2].weight;}}voidGetCode(HuffTree T,intleaf){intcur=leaf,fa,len=0,i,j;// i,j提前定义chartmp[MAXSIZE];while(T[cur].parent!=-1){fa=T[cur].parent;if(T[fa].lch==cur)tmp[len++]='0';elsetmp[len++]='1';cur=fa;}tmp[len]='\0';j=0;for(i=len-1;i>=0;i--){code[leaf][j++]=tmp[i];}code[leaf][j]='\0';}intGetWPL(HuffTree T){intsum=0,i;for(i=0;i<n;i++){sum+=T[i].weight*strlen(code[i]);}returnsum;}intmain(){HuffTree T;inti,wpl;// main内所有变量放最前面scanf("%d",&n);getchar();for(i=0;i<n;i++){scanf("%c %d",&T[i].data,&T[i].weight);getchar();}CreateHuff(T);for(i=0;i<n;i++){GetCode(T,i);}for(i=0;i<n;i++){printf("%c: %s\n",T[i].data,code[i]);}wpl=GetWPL(T);printf("WPL = %d\n",wpl);return0;}3.3 代码逐模块分析
- 结构体 HTNode
typedefstruct{chardata;// 存储字符intweight;// 权值（频率）intparent;// 父节点下标intlch,rch;// 左右孩子下标}HTNode,HuffTree[MAXSIZE];采用静态数组存储哈夫曼树，这是课程实验最常用的实现方式，结构清晰、简单易懂。
2. Select 函数：选择最小两个节点
• 第一次遍历选出权值最小的节点 s1；
• 第二次遍历选出剩余中最小的节点 s2；
• 天然满足题目要求：权值小的先被选中，作为左孩子；权值相同则下标小（先输入）优先，完全匹配题目规则。
3. CreateHuff 函数：构建哈夫曼树
• 哈夫曼树总节点数固定为 (2n-1)；
• 循环 (n-1) 次合并节点；
• s1 固定为左孩子（0），s2 为右孩子（1），严格遵守题目编码规则。
4. GetCode 函数：回溯生成编码
• 从叶子向上走到根，沿途记录 0/1；
• 因为是逆序，使用 strrev 反转字符串，得到从根到叶子的正确编码。
原代码扣分点：strrev 不是标准 C 库函数，仅 VC 可用，GCC 编译报错。
5. GetWPL 函数：计算带权路径长度
直接套用公式：权值 × 编码长度（路径长度），累加求和，逻辑简单准确。
四、实验结果与分析
4.1 运行结果
输出与题目样例完全一致，程序逻辑正确。
4.2 算法复杂度分析
时间复杂度：O(n^2)，每次Select需要遍历数组；
空间复杂度：O(n)，使用静态数组存储节点；
适合课程实验小规模数据，工业级实现一般使用最小堆优化至 O(n*log n)。
五、总结
本文完整梳理了哈夫曼树与哈夫曼编码的理论原理,通过手工推演验证了样例的正确性,完整沿用实验编写的 C 语言代码，对每个函数进行详细逻辑分析，同时修复了兼容性缺陷。
该程序能够正确生成每个字符的哈夫曼编码并计算 WPL。哈夫曼算法作为贪心算法的经典案例，既加深了对二叉树的理解，也体现了最优编码在数据压缩中的实际价值。