哈夫曼树：高效压缩数据的秘密武器

引言

在前面的树系列中，我们学习了二叉搜索树、AVL 树和红黑树——它们都是为了高效查找而设计的。今天要讲的哈夫曼树，目的完全不同：它是为了压缩数据而生。

哈夫曼树（Huffman Tree），又称最优二叉树，由 David Huffman 于 1952 年提出。它的核心思想是：让出现频率高的字符用短编码，出现频率低的字符用长编码，从而使整体编码长度最短。这是变长编码的经典应用，广泛用于 ZIP 压缩、JPEG 图片编码、MP3 音频压缩等领域。

第一部分：基本概念

一、相关术语

二、带权路径长度 WPL

第二部分：哈夫曼树的构建

一、构建算法（贪心策略）

构建步骤总结：

1. 将所有带权节点各自作为一棵单节点二叉树，放入集合

2. 从集合中选出权值最小的两棵树

3. 合并成一棵新树（新树根权 = 两子树根权之和）

4. 将新树放回集合

5. 重复 2-4，直到集合中只剩一棵树

二、哈夫曼树的特点

第三部分：哈夫曼编码

一、编码原理

哈夫曼树构建完成后，从根到叶子节点的路径就是该叶子节点的编码：

• 左分支 = 0

• 右分支 = 1

二、前缀编码

哈夫曼编码是前缀编码——任何一个字符的编码都不是另一个字符编码的前缀。

第四部分：完整代码实现

一、数据结构定义

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_NODES 256 #define MAX_CODE_LEN 128 // 哈夫曼树节点 typedef struct { int weight; // 权值（频率） int parent; // 父节点下标 int left; // 左子下标（0 表示无） int right; // 右子下标（0 表示无） } HTNode; // 哈夫曼编码表 typedef struct { char code[MAX_CODE_LEN]; // 编码（如 "110"） int len; // 编码长度 } HuffmanCode;

二、构建哈夫曼树

// 在未选节点中找最小权值的两个 void selectMinTwo(HTNode* ht, int n, int* s1, int* s2) { int min1 = -1, min2 = -1; for (int i = 1; i <= n; i++) { if (ht[i].parent != 0) continue; // 已选过的跳过 if (min1 == -1 || ht[i].weight < ht[min1].weight) { min2 = min1; min1 = i; } else if (min2 == -1 || ht[i].weight < ht[min2].weight) { min2 = i; } } *s1 = min1; *s2 = min2; } // 构建哈夫曼树 // weights: 权值数组, n: 叶子节点数 // 返回构建好的哈夫曼树（共有 2n-1 个节点，下标从 1 开始） HTNode* buildHuffmanTree(int weights[], int n) { if (n <= 1) return NULL; int m = 2 * n - 1; // 总节点数 HTNode* ht = (HTNode*)malloc(sizeof(HTNode) * (m + 1)); // 初始化所有节点 for (int i = 1; i <= m; i++) { ht[i].weight = (i <= n) ? weights[i - 1] : 0; ht[i].parent = 0; ht[i].left = 0; ht[i].right = 0; } // 构建内部节点 for (int i = n + 1; i <= m; i++) { int s1, s2; selectMinTwo(ht, i - 1, &s1, &s2); ht[i].weight = ht[s1].weight + ht[s2].weight; ht[i].left = s1; ht[i].right = s2; ht[s1].parent = i; ht[s2].parent = i; } return ht; }

三、生成哈夫曼编码

// 从叶子向根回溯，生成每个字符的哈夫曼编码 void generateHuffmanCode(HTNode* ht, int n, HuffmanCode* codes) { char temp[MAX_CODE_LEN]; for (int i = 1; i <= n; i++) { int current = i; int parent = ht[i].parent; int codeLen = 0; // 从叶子向根回溯 while (parent != 0) { if (ht[parent].left == current) { temp[codeLen++] = '0'; } else { temp[codeLen++] = '1'; } current = parent; parent = ht[parent].parent; } // 反转编码（回溯得到的是逆序） codes[i].len = codeLen; for (int j = 0; j < codeLen; j++) { codes[i].code[j] = temp[codeLen - 1 - j]; } codes[i].code[codeLen] = '\0'; } }

四、编码与解码

// 编码：将字符串转为哈夫曼编码 void encode(const char* text, HuffmanCode* codes, char* result) { result[0] = '\0'; for (int i = 0; text[i] != '\0'; i++) { int idx = text[i] - 'A' + 1; // 假设字符 A=1, B=2, ... strcat(result, codes[idx].code); } } // 解码：将哈夫曼编码还原为字符串 void decode(const char* encoded, HTNode* ht, int n, char* result) { int root = 2 * n - 1; // 根节点下标 int current = root; int pos = 0; for (int i = 0; encoded[i] != '\0'; i++) { if (encoded[i] == '0') { current = ht[current].left; } else { current = ht[current].right; } // 到达叶子节点 if (ht[current].left == 0 && ht[current].right == 0) { result[pos++] = 'A' + current - 1; // 还原字符 current = root; } } result[pos] = '\0'; }

五、完整测试

int main() { int n = 4; // 4 个字符 A, B, C, D int weights[] = {2, 3, 4, 5}; // 对应频率 // 1. 构建哈夫曼树 HTNode* ht = buildHuffmanTree(weights, n); // 2. 生成编码表 HuffmanCode codes[n + 1]; generateHuffmanCode(ht, n, codes); // 3. 打印编码表 printf("===== 哈夫曼编码表 =====\n"); for (int i = 1; i <= n; i++) { printf("%c: %s\n", 'A' + i - 1, codes[i].code); } // 4. 编码测试 const char* text = "ABCD"; char encoded[512]; encode(text, codes, encoded); printf("\n原文: %s\n", text); printf("编码: %s\n", encoded); // 5. 解码测试 char decoded[128]; decode(encoded, ht, n, decoded); printf("解码: %s\n", decoded); // 6. 压缩率 int originalBits = strlen(text) * 8; int compressedBits = strlen(encoded); printf("\n原始: %d bit, 压缩后: %d bit, 压缩率: %.1f%%\n", originalBits, compressedBits, 100.0 * compressedBits / originalBits); free(ht); return 0; }

运行结果：

===== 哈夫曼编码表 ===== A: 110 B: 111 C: 10 D: 0 原文: ABCD 编码: 110111100 解码: ABCD 原始: 32 bit, 压缩后: 9 bit, 压缩率: 28.1%

第五部分：算法分析

一、时间复杂度

二、空间复杂度

O(n)，需要存储 2n-1 个节点。

三、哈夫曼树的特点总结

第六部分：实际应用

总结

一、核心要点

二、构建步骤记忆

1. 所有节点各自成树，放入森林
2. 选权值最小的两棵合并
3. 新树放回
4. 重复 2-3 直到只剩一棵树

三、一句话记忆

哈夫曼树是一种 WPL 最小的最优二叉树，用贪心策略每次合并权值最小的两棵树构建。左 0 右 1 得到前缀编码，高频短码低频长码，广泛用于无损压缩。