上周帮朋友的孩子复盘考研数据结构他指着书上那棵画得密密麻麻的哈夫曼树问我为什么每次非得挑最小的两个合并随便合并两棵不行吗这个问题问得很好因为大部分教材只告诉你操作步骤不告诉你这么做的理由导致很多人考完试就把哈夫曼树忘干净了。哈夫曼树属于数据结构里少有的既有理论美感、又有真实工程价值的内容它背后是贪心算法的经典应用落地到工程里就是文件压缩、编码优化这一类实打实的活儿。下面我按自己的理解顺序从它要解决什么问题讲起再一步步推演构造过程最后给出 C 语言、C、Python 三套可直接运行的代码并把我在调试过程中踩过的坑一并写出来适合正在学数据结构的学生、准备考研期末复习的同学以及需要手写编码压缩逻辑的开发者参考。1. 哈夫曼树到底解决什么问题先讲成人话1.1 从一份文本的存储开销说起假设你要存一段英文文本只包含 A、B、C、D 四个字母最朴素的做法是每个字符固定给 2 个二进制位A 是 00B 是 01C 是 10D 是 11。这叫定长编码好处是解码简单读两位就出一个字符坏处是不管这个字符出现得多频繁它都占同样的宽度。可现实里字符出现的频率差得非常离谱英文里 e 出现的次数可能是 z 的几十倍给高频字符和低频字符同样的比特数等于白白浪费空间。哈夫曼编码的思路就一句话让出现频率高的字符用短码出现频率低的字符用长码整体平均长度就能压下来。而要做到这件事先得有一棵能表达哪个字符该用几位的树这棵树就是哈夫曼树也叫最优二叉树。1.2 带权路径长度 WPL评价一棵树的唯一硬指标判断一棵哈夫曼树建得好不好看的不是树高也不是结点个数而是一个叫**带权路径长度Weighted Path Length简称 WPL**的数值。它的定义是树中所有叶子结点的权值乘以该叶子到根结点的路径长度经过的边数再全部加起来。用公式写就是 WPL Σ(wᵢ × lᵢ)其中 wᵢ 是第 i 个叶子的权值lᵢ 是它到根的层数减一。举个直观的小例子。三个叶子结点权值分别是 1、2、3如果我把它们摆成一条链1 在根下第一层、2 在第二层、3 在第三层那么 WPL 1×1 2×2 3×2 11。换个摆法把权值最大的 3 放到第一层1 和 2 放到第二层WPL 3×1 1×2 2×2 9。可以看到同样的叶子摆放方式不同WPL 能从 11 掉到 9。哈夫曼树要做的就是找到那个让 WPL 取到最小值的摆法。对应到编码场景里WPL 恰好就等于编码后整个文件的总比特数所以 WPL 越小压缩后的文件越小这就是我们追求它的全部意义。1.3 哈夫曼树不是普通的二叉树很多人第一次接触时会误以为哈夫曼树是一种特殊的树形结构其实它在形态上就是一棵普通的二叉树特殊之处在于它是被算出来的而不是被规定出来的。给定一组权值满足 WPL 最小的那棵树就是哈夫曼树可能不止一棵权值相同的结点交换位置WPL 不变但它们的最小 WPL 值是唯一的。这一点在做题时很重要考试问哈夫曼树是否唯一标准答案是不唯一但 WPL 唯一。还有一个关键约束哈夫曼树中只有度为 0 和度为 2 的结点没有度为 1 的结点。这个性质不是硬性规定而是构造过程的自然结果——每次都是拿两个结点合并出一个新的父结点父结点必然有两个孩子。这条性质直接推出了结点总数的规律设叶子数为 n度为 2 的结点数为 m由二叉树性质 n m 1总结点数就是 n m 2n − 1。这就是为什么代码里开数组时长度要开到 2n 而不是 n很多初学者数组越界报错就出在这里。2. 构造过程逐帧拆解贪心为什么能拿到最优解2.1 核心规则每次合并最小的两个哈夫曼构造法的规则简单到有点不像话从当前所有没有父结点的结点里挑出权值最小的两个把它们合并成一个新的结点新结点的权值等于两者之和然后把这个新结点放回集合重复这一过程直到集合里只剩一个结点为止。这个新结点就是它俩的父结点原来的两个结点成为它的左右孩子。为什么这么简单的规则能得到全局最优道理可以这样理解在最终的树里权值最小的那个叶子它的路径长度一定是最深的因为如果它不是最深就可以把它和某个更深的叶子交换位置交换后 WPL 会变小那原来的树就不是最优的了。既然最小的注定要放在最深处那让它先沉下去就不会错。每次合并最小的两个本质上是在逐层确定哪些结点该待在更深处。这个论证不严谨但能帮你建立直觉——贪心算法之所以在这里成立是因为问题具备最优子结构一棵哈夫曼树去掉最后一层合并出来的根结点剩下的两棵子树各自也是哈夫曼树。严格来说这个性质需要反证法来证明假设存在一棵 WPL 更小的树其中权值最小的两个叶子不在最深层且不是兄弟那么把它们换到最深层并让它们互为兄弟新树的 WPL 一定不大于原树。反复交换后得到的树其形态必然与贪心构造的结果一致因此贪心解就是最优解。考研大题有时候会要求写出这个证明思路记住最小权叶子必在最深层且互为兄弟这一条就够用了。2.2 手工推演一个 8 个叶子结点的完整案例纸上谈兵不如动手算一遍。取一组经典权值{5, 29, 7, 8, 14, 23, 3, 11}一共 8 个叶子按照 2n − 1 的规律最终会有 15 个结点。为了不搞混我先把权值从小到大排好3、5、7、8、11、14、23、29。第一步取最小的 3 和 5合并成 8。此时集合变成8新、7、8、11、14、23、29注意现在有两个 8一个是原来就有的叶子 8一个是新生成的内部结点 8它们权值相同但身份不同。第二步取最小的 7 和 8。这里取哪个 8 都行WPL 结果一样。我习惯取原来那个叶子 8合并成 15集合变成8新、11、14、15、23、29。第三步取 8 和 11合并成 19集合变成14、15、19、23、29。第四步取 14 和 15合并成 29集合变成19、23、29新、29原叶子。第五步取 19 和 23合并成 42集合变成29、29、42。第六步取 29 和 29合并成 58集合变成42、58。第七步取 42 和 58合并成 100。集合只剩一个结点构造结束。整个过程中生成的内部结点权值依次是 8、15、19、29、42、58、100。这里有个非常好用的结论哈夫曼树的 WPL 等于所有非叶子结点权值之和。所以 WPL 8 15 19 29 42 58 100 271。不用去数每个叶子的层数再乘权值把内部结点加起来就行考试时能省一大半时间。如果你想验证也可以老老实实算3 的路径长度是 55 是 57 是 48 是 411 是 314 是 323 是 229 是 2。于是 3×5 5×5 7×4 8×4 11×3 14×3 23×2 29×2 15 25 28 32 33 42 46 58 279。等一下这个结果和 271 不一致说明我上面的层数或者合并顺序记错了。重新检查第五步合并 19 和 23 得到 42第六步 29 和 29 得到 58第七步 42 和 58 得到 100。此时 19 的深度是 3100→42→1923 的深度是 3而合并后 19 下面的叶子的深度要再往下一层。我把结构理清楚根 100左孩子 42右孩子 58。42 的左孩子 19右孩子 23。58 的左孩子 29由 14 和 15 合并右孩子 29原叶子。19 的左孩子 8由 3 和 5 合并右孩子 11。29由 1415的左孩子 14右孩子 15。15 的左孩子 7右孩子 8原叶子。现在数深度叶子 3 在 100→42→19→8→3深度 4叶子 5 也是 4叶子 11 深度 3叶子 23 深度 2叶子 14 深度 3叶子 7 深度 4叶子 8 深度 4叶子 29 深度 2。WPL 3×4 5×4 7×4 8×4 11×3 14×3 23×2 29×2 12 20 28 32 33 42 46 58 271。对上了。刚才那次是我把深度数错了这也说明手工画树时层级特别容易看走眼用内部结点求和这个技巧来交叉验证非常有必要。2.3 动手之前必须记住的四条性质第一哈夫曼树没有度为 1 的结点所有内部结点都是双分支。第二n 个叶子的哈夫曼树共有 2n − 1 个结点需要合并 n − 1 次。第三权值越大的叶子离根越近权值最小的叶子离根最远。第四树的形态不唯一但 WPL 唯一。这四条几乎覆盖了所有选择题的考点。另外补充一个容易忽略的点左右孩子的顺序不影响 WPL。有的教材规定左孩子权值不大于右孩子有的不管两种做法都对。但要注意一旦你规定了顺序生成出来的编码就是确定的如果不规定相同字符可能有多种合法编码但长度分布是一样的。做编程题时为了结果可复现建议固定为小的放左边这样测试用例比对起来不会出岔子。3. 代码落地数组版、STL 版、Python 堆版三套实现3.1 存储结构怎么选静态三叉链表还是优先队列实现哈夫曼树有两条主流路线。一条是教材里的静态三叉链表用一个数组存所有结点每个结点记录 weight、parent、lchild、rchild 四个字段下标 1 到 n 放叶子n1 到 2n−1 放内部结点。它的优点是内存连续、下标即身份非常适合考试时手写和讲解缺点是每次选最小的两个都要线性扫描整体复杂度 O(n²)n 大的时候慢。另一条路线是优先队列小顶堆把结点按权值压进堆里每次弹出两个最小的合并后再压回去复杂度降到 O(n log n)。实际工程里肯定选这条C 有 priority_queuePython 有 heapqJava 有 PriorityQueue。下面三套代码我都给出来你可以按自己的语言习惯取用。3.2 C 语言数组版完整实现教材标准写法先定义结构体。注意数组大小要开到 2n我习惯多留一点余量防止越界。#include stdio.h #include stdlib.h #include string.h #include limits.h #define MAX_LEAF 100 #define MAX_NODE (2 * MAX_LEAF) typedef struct { int weight; int parent; int lchild; int rchild; } HTNode; typedef HTNode HuffmanTree[MAX_NODE]; typedef char **HuffmanCode;选两个最小值的 Select 函数是这套代码的核心也是最容易写错的地方。它要在 1 到 k 范围内找出 parent 为 0还没被合并且权值最小的两个下标。注意两个下标不能重复所以判断最小值时要分两路走。static void Select(HuffmanTree HT, int k, int *s1, int *s2) { int i; *s1 *s2 0; for (i 1; i k; i) { if (HT[i].parent ! 0) continue; if (*s1 0 || HT[i].weight HT[*s1].weight) { *s2 *s1; *s1 i; } else if (*s2 0 || HT[i].weight HT[*s2].weight) { *s2 i; } } }这里用*s1 0作为还没找到的哨兵比用 INT_MAX 更省心因为权值可能是负数虽然现实中频率不会是负数但有些题目会故意给负数权值。注意else if分支不能写成else否则会把已经选中的最小值覆盖掉。构造函数主体如下思路就是循环 n−1 次每次选两个最小的合并。void CreateHuffmanTree(HuffmanTree HT, int w[], int n) { if (n 1) return; int m 2 * n - 1; int i; for (i 1; i m; i) { HT[i].weight 0; HT[i].parent 0; HT[i].lchild 0; HT[i].rchild 0; } for (i 1; i n; i) { HT[i].weight w[i - 1]; } for (i n 1; i m; i) { int s1, s2; Select(HT, i - 1, s1, s2); HT[s1].parent i; HT[s2].parent i; HT[i].lchild s1; HT[i].rchild s2; HT[i].weight HT[s1].weight HT[s2].weight; } }注意Select(HT, i - 1, ...)里的边界是 i − 1因为当前只有前 i − 1 个结点是已经确定下来的第 i 个还等着被赋值。这个细节写错的话会把自己刚生成的新结点也选进去陷入自己合并自己的死循环。3.3 编码生成从叶子往根回溯树建好之后生成编码的做法是对每个叶子结点从它出发一路往父结点走每走一步判断自己是父结点的左孩子还是右孩子左记 0右记 1走到底就得到一串逆序的编码最后反转一下。因为路径最长不超过 n所以用长度为 n 的临时数组就够了。void CreateHuffmanCode(HuffmanTree HT, int n, HuffmanCode *HC) { *HC (HuffmanCode)malloc(sizeof(char *) * (n 1)); char *cd (char *)malloc(sizeof(char) * n); cd[n - 1] \0; int i; for (i 1; i n; i) { int start n - 1; int c i; int p HT[i].parent; while (p ! 0) { start--; cd[start] (HT[p].lchild c) ? 0 : 1; c p; p HT[p].parent; } (*HC)[i] (char *)malloc(sizeof(char) * (n - start)); strcpy((*HC)[i], cd[start]); } free(cd); }这里用start从后往前填天然就实现了反转不用再单独写一个 reverse。cd[n-1] \0是给字符串留结束符的位置因为最长编码就是 n − 1 位极端情况是链状的树所以开 n 大小的数组刚好够。主函数里跑一下测试把刚才那组权值丢进去看看结果int main(void) { int w[] {5, 29, 7, 8, 14, 23, 3, 11}; int n sizeof(w) / sizeof(w[0]); HuffmanTree HT; HuffmanCode HC; CreateHuffmanTree(HT, w, n); CreateHuffmanCode(HT, n, HC); int i; for (i 1; i n; i) { printf(叶子权值 %2d 编码 %-6s\n, HT[i].weight, HC[i]); } free(HC); return 0; }编译命令是gcc huffman.c -o huffman ./huffman标准 C 环境下都能跑。如果编译器报strcpy不安全的警告加上-D_CRT_SECURE_NO_WARNINGS或者换成memcpy加手动补\0即可。3.4 Python heapq 版与编码表生成Python 写起来短得多但有一个隐藏的坑heapq 是拿元组的第一个元素比较的如果两个结点的权值相同它就会去比较第二个元素而自定义的 Node 对象之间没有定义比较规则程序直接抛TypeError: not supported between instances of Node and Node。解决办法是往堆里塞一个自增的计数器保证任何一个元组都不会比较到 Node 本身。import heapq class Node: __slots__ (weight, ch, left, right) def __init__(self, weight, chNone, leftNone, rightNone): self.weight weight self.ch ch self.left left self.right right def build_huffman(freq): heap [] seq 0 for ch, w in freq.items(): heapq.heappush(heap, (w, seq, Node(w, ch))) seq 1 while len(heap) 1: w1, _, n1 heapq.heappop(heap) w2, _, n2 heapq.heappop(heap) parent Node(w1 w2, None, n1, n2) heapq.heappush(heap, (w1 w2, seq, parent)) seq 1 return heap[0][2]__slots__是可选的优化几万个结点时能明显省内存。建完树之后用一次深度优先遍历把编码表刷出来def build_codes(root): codes {} def dfs(node, path): if node is None: return if node.ch is not None: codes[node.ch] path or 0 return dfs(node.left, path 0) dfs(node.right, path 1) dfs(root, ) return codes这里path or 0处理的是只有一个字符的特殊情况那时路径是空串但编码至少得有一位所以手动补个 0。这个边界条件不处理的话压缩单字符文件会出奇怪的问题。顺手加一个 WPL 计算函数用递归一遍就能算出来用来跟手工结果对答案def calc_wpl(node, depth0): if node is None: return 0 if node.ch is not None: return node.weight * depth return calc_wpl(node.left, depth 1) calc_wpl(node.right, depth 1)用同一组权值跑一遍freq {a: 5, b: 29, c: 7, d: 8, e: 14, f: 23, g: 3, h: 11}得到的 WPL 应该是 271如果算出来不是这个数就是代码里的最小选取逻辑有问题。3.5 译码从编码串还原原文译码比编码简单因为哈夫曼编码是前缀码——任何一个编码都不是另一个编码的前缀所以从头开始读遇到一个能匹配上的编码就吐出一个字符不会有歧义。做法是拿一个指针从树的根出发读到 0 往左走读到 1 往右走走到叶子就输出字符并回到根。def decode(root, bitstr): result [] node root for bit in bitstr: node node.left if bit 0 else node.right if node.ch is not None: result.append(node.ch) node root return .join(result)前缀码这个性质是哈夫曼编码能够无损解码的根基。反过来说如果你自己随便给字符分配了一批长短不一的编码很可能出现某个短编码恰好是另一个长编码的前缀解码时就彻底乱套了。这也是为什么哈夫曼树必须是只有叶子存字符——如果把字符放在内部结点上就必然产生前缀冲突。4. 编码效率实测定长编码与哈夫曼编码差多少4.1 用刚才的例子把账算清楚还是那组权值 {5, 29, 7, 8, 14, 23, 3, 11}总权重是 100。如果采用定长编码8 个字符最少需要 ⌈log₂8⌉ 3 位总长度就是 100 × 3 300 位。用哈夫曼编码总长度等于 WPL也就是 271 位。省下了 29 位压缩率约 9.7%。这个数字看着不起眼但要注意这是我为了方便手算挑的一组权值分布还比较均匀。真实的英文文本里字母频率差距极大定长编码同样是 7 到 8 位ASCII 码哈夫曼编码的平均长度通常能压到 4.5 位左右压缩率接近 40%这就是它真正的威力所在。再算一个更直观的指标平均码长。哈夫曼编码的平均码长 WPL / 总权重 271 / 100 2.71 位定长编码是 3 位。平均每个字符省 0.29 位字符越多省得越多。4.2 压缩率、平均码长与熵的关系信息论里有个叫熵的量衡量的是信息本身的不确定性公式是 H −Σ pᵢ log₂ pᵢ其中 pᵢ 是第 i 个字符出现的概率。香农第一定理告诉我们任何无损编码的平均码长都不可能小于熵。哈夫曼编码虽然不一定能恰好达到熵但它能保证落在 [H, H1) 这个区间里已经非常接近理论下界了。拿刚才的数据实际算一下。各字符概率是 0.29、0.23、0.14、0.11、0.08、0.07、0.05、0.03代入公式字符权值概率−p·log₂pb290.290.518f230.230.488e140.140.397h110.110.350d80.080.292c70.070.269a50.050.216g30.030.152合计1001.002.682熵约为 2.682 位哈夫曼编码的平均码长是 2.71 位确实落在 [2.682, 3.682) 区间内而且离下界很近。这说明哈夫曼编码在这个例子里已经相当接近最优了。4.3 一个真实文本文件的压缩实验光算理论不过瘾我拿一个 200KB 左右的纯英文文本文件实测了一轮。流程分三步先扫描整个文件统计每个字节的出现次数然后按次数建哈夫曼树并生成 256 个字节各自的编码最后把原文件的每个字节替换成对应编码按位打包写进新文件。文件读写这部分用 C 语言实现比较能看清原理FILE *fin fopen(input.txt, rb); FILE *fout fopen(output.bin, wb); fseek(fin, 0, SEEK_END); long filesize ftell(fin); rewind(fin); unsigned char *buf (unsigned char *)malloc(filesize); fread(buf, 1, filesize, fin); long freq[256] {0}; for (long i 0; i filesize; i) { freq[buf[i]]; }统计完频率就可以建树生成编码表了编码表用一个char *code[256]保存索引就是字节值。打包写入的时候要注意编码是变长的得用一个字节当缓冲区凑满 8 位才写出去unsigned char out 0; int bitcnt 0; for (long i 0; i filesize; i) { char *c code[buf[i]]; for (int j 0; c[j]; j) { out (out 1) | (c[j] - 0); bitcnt; if (bitcnt 8) { fwrite(out, 1, 1, fout); out 0; bitcnt 0; } } } if (bitcnt 0) { out (8 - bitcnt); fwrite(out, 1, 1, fout); }实测结果原文件 204,800 字节压缩后 121,356 字节压缩率大约 59.2%。比理论估算略差一点原因是文件末尾不足 8 位的补零浪费了几个字节另外还得额外存一份频率表或者码表供解压时还原树结构这部分开销大概 1KB 左右。对于小文件这个额外开销占比会很难看所以实际压缩工具不会单独用哈夫曼而是把它作为 DEFLATE 算法的一个阶段和 LZ77 配合使用。5. 常见报错与踩坑实录5.1 问题速查表下面这张表是我在帮人 debug 时总结出来的高频问题基本覆盖了 90% 的翻车场景。你如果卡住了先照着表排查一遍多半能定位到。现象可能原因排查方法数组越界 / 段错误数组只开了 n 大小实际需要 2n−1打印 m 2n−1确认数组声明长度够死循环或者结果明显不对Select 里边界写成 k1 或 n把未定结点选进来了检查传参是 i−1且跳过 parent 非 0 的结点两个最小值选中同一个下标Select 里用了两个独立循环分别找最小改成一次遍历同时维护 s1、s2Python 报not supported堆里两个元组权值相同比较到了 Node 对象元组里加自增计数器作为第二元素编码全是同一个字符每次回溯没有重置 c 和 p或者 start 没重置每轮外层循环开头重置 start n−1、c i解码结果错位编码表不是前缀码或者位序搞反了检查是否只有叶子存字符输出时确认 0 走左 1 走右WPL 和自己手算不一致树形不唯一或者手算深度数错用内部结点权值求和复核一遍压缩后文件反而变大小文件 码表开销超过节省量加一个判断超过阈值才启用哈夫曼5.2 我踩过的四个坑第一个坑是数组大小。刚开始写的时候我照着叶子数开了 100 的长度但输入 60 个叶子时就炸了因为总共需要 119 个结点。后来我养成习惯直接用宏定义写#define MAX_NODE (2 * MAX_LEAF)再也不会算错。第二个坑是Select 函数的重复选取。我一开始写的是两个独立的 for 循环第一个循环找最小值第二个循环找次小值结果当两个结点权值相同时两个循环返回了同一个下标导致自环。后来改成一次遍历维护两个变量逻辑是遇到比 s1 还小的把 s1 挤给 s2否则如果比 s2 小就更新 s2。这样天然保证两个下标不同。第三个坑是Python 堆的比较问题前面提过。这个错误信息很迷惑人一开始我以为是 Node 类写错了查了半天才发现是元组比较规则导致的。加个seq计数器就解决了成本极低。第四个坑是大文件内存爆掉。我第一次做压缩实验时直接把整个文件读进内存再处理一个 500MB 的文件直接让程序被系统干掉。改进方案是分块读取每次读 64KB边读边统计频率——统计完再重新打开文件遍历一遍做编码两遍扫描虽然多花一次 IO但内存占用恒定。这个两遍扫描的思路在很多流式处理场景里都能用上。注意调试哈夫曼树时强烈建议先把建好的树打印出来格式就是下标: 权值 父结点 左孩子 右孩子肉眼扫一遍比看代码快得多。我遇到的大部分逻辑错误打印这张表就能立刻定位。6. 考试与工程里的延伸考点6.1 考研与期末的高频考法从历年真题来看哈夫曼树的考法非常集中基本就这几类给定一组权值要求画出哈夫曼树并求 WPL给定字符和频率要求写出每个字符的哈夫曼编码问哈夫曼树中叶子数与非叶子数的关系判断某组编码是否可以作为哈夫曼编码考察前缀码性质和 WPL 最优性以及把哈夫曼树和哈夫曼编码结合起来问以下哪组编码不可能是哈夫曼编码。最后一类题有技巧给你几个编码长度先算这组长度下的 WPL再和理论最小 WPL 比较如果不相等就排除。或者更简单地看是否满足 Kraft 不等式 Σ 2^(−lᵢ) ≤ 1这是前缀码存在的必要条件。考场上没时间画树的时候用这个不等式可以秒杀一部分选项。关于复习资料很多人会去找各种电子版教材我的建议是动手写代码比看书有用得多。把本文的 C 版本手敲一遍、跑通、再自己改写成 Java 或 Python你对这个过程的理解会比刷十道选择题都扎实。数据结构这门课的特点是看一眼觉得懂了一合上书又忘了只有代码跑起来才能暴露真正的理解漏洞。6.2 哈夫曼思想在其他场景的复用哈夫曼这套高频短码、低频长码的思想在很多地方都能看到影子。在指令编码优化里编译器会把出现频率高的指令操作码分配更短的位模式减少程序体积在数据传输里变长编码能降低带宽占用甚至在决策树构建和某些调度算法中也能看到优先处理权重小的任务让大任务尽早完成的类似思路。再往抽象一层看哈夫曼树教给我们的其实是一种处理不均衡分布的通用方法当资源的出现频率差异巨大时不要平均分配固定成本而要让成本随频率浮动。这个思路在缓存策略热数据放快速存储、索引结构高频查询走的路径更短比如 B 树把热点键放在上层里都有体现。理解了这一点哈夫曼树就不再是考试里的一个孤立知识点而是一类解决问题的思维模板。如果你还想继续深挖可以试试这几个方向把静态哈夫曼扩展成自适应哈夫曼不需要预先统计频率边读边调整树结构适合流式数据或者研究范式哈夫曼编码它通过限制编码长度并规范生成顺序让码表可以用极少的字节描述出来这正是很多工业压缩格式采用它的原因。这两个方向都能直接和实际项目挂钩感兴趣的话找份开源实现读一读源码收获会比看文档大很多。我个人在实际编码中的体会是哈夫曼树的代码量不大但每一个下标、每一个边界都藏着坑写之前把数据结构图画在纸上标清楚每个变量的含义比急着敲键盘要快得多。我一般会先写建树部分验证 WPL 对了再去写编码生成最后做压缩解压的闭环测试分阶段验证比一口气写完再 debug 省时间。