10、哈夫曼树（下）：哈夫曼编码的C语言实现、文件压缩与解压的简单原理
上一节我们把哈夫曼树的理论讲透了，从带权路径长度到构造算法，都梳理了一遍。但说实话，光懂理论是不够的——你面试时写不出代码，项目里用不上，那等于白学。
这一节，我们来点实在的。我会带你手写哈夫曼编码的C语言实现，然后聊聊文件压缩与解压的简单原理。嗯，这部分内容我当年在做一个嵌入式日志系统时用过，压缩率虽然比不上zlib，但胜在代码可控、原理透明。
10.1 从哈夫曼树到哈夫曼编码
先理清一个概念：哈夫曼树是数据结构，哈夫曼编码是它的应用。说白了，我们构造哈夫曼树的目的，就是为了给每个字符分配一个独一无二的二进制编码。
编码规则很简单：
- 从根节点出发，往左走记作
0，往右走记作1 - 走到叶子节点时，路径上的0/1序列就是该字符的编码
- 因为每个字符都是叶子节点，所以编码是前缀码——没有一个编码是另一个编码的前缀
举个例子，假设我们有四个字符 A、B、C、D，频率分别是 5、9、12、13。构造哈夫曼树后，编码可能是：
| 字符 | 频率 | 哈夫曼编码 |
|---|---|---|
| A | 5 | 110 |
| B | 9 | 111 |
| C | 12 | 10 |
| D | 13 | 0 |
你看，频率最高的 D 只用了 1 位，频率最低的 A 用了 3 位。这就是哈夫曼编码的精髓——让高频字符用短码，低频字符用长码，整体压缩效果最优。
核心要点：哈夫曼编码是变长编码，但解码时不会产生歧义。为什么？因为前缀码特性保证了每个编码的边界是确定的。
10.2 C语言实现：构造哈夫曼树与生成编码表
我个人习惯用数组来模拟哈夫曼树，而不是用指针链表。原因很简单：在嵌入式或文件压缩场景下，数组的内存布局更可控，调试也方便。
先定义数据结构：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEAF 256 // 最多256个字符（ASCII）
#define MAX_NODE (MAX_LEAF * 2 - 1)
typedef struct {
unsigned char ch; // 字符（仅叶子节点有效）
int weight; // 权值（频率）
int parent; // 父节点下标，-1表示无
int lchild, rchild; // 左右孩子下标
} HuffmanNode;
typedef struct {
char code[MAX_LEAF]; // 编码字符串，如"110"
int len; // 编码长度
} HuffmanCode;接下来是构造哈夫曼树的函数。我建议你注意一下选择最小两个节点的逻辑——这是最容易写错的地方。
void buildHuffmanTree(HuffmanNode *tree, int n) {
// 初始化所有节点
for (int i = 0; i < 2 * n - 1; i++) {
tree[i].parent = -1;
tree[i].lchild = -1;
tree[i].rchild = -1;
}
// 循环合并，直到只剩一个根节点
for (int i = n; i < 2 * n - 1; i++) {
// 找两个权值最小且无父节点的节点
int min1 = -1, min2 = -1;
for (int j = 0; j < i; j++) {
if (tree[j].parent != -1) continue;
if (min1 == -1 || tree[j].weight < tree[min1].weight) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || tree[j].weight < tree[min2].weight) {
min2 = j;
}
}
// 合并 min1 和 min2
tree[i].weight = tree[min1].weight + tree[min2].weight;
tree[i].lchild = min1;
tree[i].rchild = min2;
tree[min1].parent = i;
tree[min2].parent = i;
}
}避坑指南：我曾经在找最小两个节点时，忘了处理 min1 和 min2 初始值的问题。如果 n=1（只有一个字符），循环根本不会执行，但后续编码会出问题。建议在调用前先判断 n 是否大于 1。
生成编码表时，我们从每个叶子节点向上回溯，记录路径：
void generateCodes(HuffmanNode *tree, int n, HuffmanCode *codes) {
char temp[MAX_LEAF];
for (int i = 0; i < n; i++) {
int cur = i;
int len = 0;
// 从叶子向上走到根
while (tree[cur].parent != -1) {
int p = tree[cur].parent;
if (tree[p].lchild == cur)
temp[len++] = '0';
else
temp[len++] = '1';
cur = p;
}
// 反转得到正确顺序
codes[i].len = len;
for (int j = 0; j < len; j++) {
codes[i].code[j] = temp[len - 1 - j];
}
codes[i].code[len] = '\0';
}
}你想想看，为什么这里要反转？因为回溯时是从叶子到根，路径是反的。嗯，这个细节我当年第一次写的时候就踩坑了，调试了半天才发现编码顺序反了。
10.3 文件压缩的简单原理
有了编码表，压缩就水到渠成了。基本流程如下：
- 统计频率：读取源文件，统计每个字节出现的次数
- 构造哈夫曼树：根据频率表生成树和编码表
- 写入文件头：把频率表或树结构写入压缩文件，供解压时使用
- 编码数据：逐个字节读取源文件，用编码表替换为二进制位流
- 写入压缩数据：将位流按字节打包写入文件
这里有个关键问题：位操作。C语言的最小存储单位是字节，但哈夫曼编码是变长的位序列。你需要自己维护一个位缓冲区，凑满8位再写入。
typedef struct {
unsigned char buf; // 缓冲区
int bits; // 缓冲区中有效位数
} BitBuffer;
void writeBit(BitBuffer *bb, int bit, FILE *fp) {
bb->buf = (bb->buf << 1) | (bit & 1);
bb->bits++;
if (bb->bits == 8) {
fwrite(&bb->buf, 1, 1, fp);
bb->buf = 0;
bb->bits = 0;
}
}
void flushBits(BitBuffer *bb, FILE *fp) {
if (bb->bits > 0) {
bb->buf <<= (8 - bb->bits); // 左对齐剩余位
fwrite(&bb->buf, 1, 1, fp);
}
}注意：文件头怎么写是个学问。最简单的做法是把频率表原样写入，但这样会占用 256×4=1024 字节（假设频率用 int 存储）。我曾在项目中用变长编码存储频率表，压缩率能再提升 1-2%。不过对于教学来说，直接存频率表更清晰。
10.4 文件解压的简单原理
解压是压缩的逆过程，但有个地方容易绕晕——解码时不需要编码表，只需要哈夫曼树。
流程如下：
- 读取文件头：恢复频率表，重建哈夫曼树
- 逐位读取压缩数据：从根节点开始，读一位就走一步
- 到达叶子节点：输出该叶子对应的字符，然后回到根节点
- 重复直到数据读完
你可能会问：为什么不用编码表解码？因为编码表是字符→编码的映射，而解码时我们拿到的是位流，需要反过来查。用树结构解码，时间复杂度是 O(编码长度)，非常高效。
void decompress(HuffmanNode *tree, int root, FILE *fin, FILE *fout, int totalChars) {
int cur = root;
int decoded = 0;
unsigned char byte;
while (fread(&byte, 1, 1, fin) == 1 && decoded < totalChars) {
for (int i = 7; i >= 0 && decoded < totalChars; i--) {
int bit = (byte >> i) & 1;
if (bit == 0)
cur = tree[cur].lchild;
else
cur = tree[cur].rchild;
if (tree[cur].lchild == -1 && tree[cur].rchild == -1) {
// 到达叶子节点
fwrite(&tree[cur].ch, 1, 1, fout);
decoded++;
cur = root; // 回到根节点
}
}
}
}个人经验：解压时一定要记录原始字符总数 totalChars。为什么？因为最后一个字节可能不足8位，会有填充位。如果不记录总数，解压时会多解出一些垃圾字符。我早期的一个版本就因为这个 bug，解压出来的文件末尾多了几个乱码。
10.5 知识体系总览
下面这张图把哈夫曼编码从树到压缩的完整流程串起来了，你可以对照着理解：
10.6 几点补充与思考
讲到这里，哈夫曼编码的核心实现和压缩原理基本覆盖了。我再补充几个实际开发中会遇到的问题：
- 大文件处理：不要一次性把整个文件读入内存。用缓冲区分块读写，我一般设 64KB 的缓冲区。
- 编码表存储：除了存频率表，也可以直接存哈夫曼树的形状。但存频率表更通用，解压时重建树即可。
- 性能优化：如果追求速度，可以用查表法代替逐位解码。提前建好一个 8 位或 16 位的跳转表，一次处理多个位。
总结一下：哈夫曼编码是「以空间换时间」的典型反例——它用变长编码节省空间，但编解码需要额外计算。不过对于文本文件，压缩率通常能达到 40%-60%，性价比很高。
说实话，哈夫曼编码是我大学时期第一个真正「看懂」的压缩算法。它不复杂，但思想很漂亮——用树的路径来表达编码，用频率来指导树的形状。这种「数据驱动结构」的思路，后来在很多场景都给了我启发。