刚学《数据结构》的时候，我把哈夫曼树当成一棵“考试树”——背下构造方法，算对 WPL，画完一棵树交卷，然后就想当然地认为这玩意儿跟实际开发没什么关系。直到后来做文件压缩相关的需求，我才发现自己错得离谱：ZIP、gzip、PNG、JPEG、MP3，这些天天在用的格式，底层几乎都有哈夫曼编码的影子。
这篇文章我把哈夫曼树和哈夫曼编码的构造方法从头到尾拆一遍，包含完整的手算过程、贪心思想为什么成立、一套可以直接跑通的 Python 实现，以及我自己调试时踩过的坑。无论你是正在备考数据结构的学生，还是想真正搞懂压缩原理的开发者，建议跟着手动建一棵树，再跑一遍代码。只要走完这两步，这个知识点基本就焊死在脑子里了。
1. 先搞清楚哈夫曼树到底是什么
1.1 从“路径长度”到“带权路径长度”
要理解哈夫曼树，绕不开两个概念：路径长度和带权路径长度。在二叉树里，从根节点往下走到某个节点所经过的边的条数，就是该节点的路径长度。根节点自己的路径长度是 0，它的左右孩子是 1，再往下是 2，以此类推。
那“带权路径长度”加了个“带权”，意思是每个节点不再一视同仁。假设一棵树的 n 个叶子节点分别带有权重 w₁、w₂、……、wₙ，其中第 i 个叶子节点深度是 lᵢ，那么整棵树的带权路径长度定义为：
WPL = w₁ × l₁ + w₂ × l₂ + …… + wₙ × lₙ
这里每个权重乘的是它所在叶子节点的深度。为什么要乘深度？因为在一个实际场景里，深度往往代表代价。比如用一棵树来做编码，深度就是编码长度；用一棵树来做决策，深度就是判定次数。权重越大的节点，越希望它待在离根近的地方，这样总代价才小。
哈夫曼树，又叫最优二叉树，就是给定一组叶子节点的权重，在所有这些叶子构成的二叉树里，构造出 WPL 最小的一棵。它不一定是唯一的，但它的带权路径长度一定是最小的。
1.2 为什么 WPL 越小越好
用一个非常具体的例子来说明。假设五个字符的出现次数分别是 2、3、5、7、11，如果随便摆一棵二叉树，比如把权重最小的 2 放在最靠近根的位置，权重最大的 11 反而沉在最底层，得到一棵极度倾斜的树，它的 WPL 是：
2×1 + 3×2 + 5×3 + 7×4 + 11×4 = 2 + 6 + 15 + 28 + 44 = 95
这个值非常大。原因很直观：11 这个最常用的字符被分到了 4 层深的位置，每次编码它都要多花好几个 bit，代价被成倍放大了。
那怎么安排才合理？核心直觉就一句话：权重越大的叶子，离根越近。哈夫曼的构造方法恰恰保证了这一点。同样五个权重，按哈夫曼算法建出来的树，WPL 只有 60。同样是编码这五个字符，一个用 95 个 bit，一个用 60 个 bit，差了将近 40。这就是最优树和普通树的差距。
如果把这些权重理解成字符在文本中的出现频率，那 WPL 就直接对应编码后的总比特数。压缩的本质，就是把频率高的东西用短码表示，频率低的东西用长码表示。哈夫曼把这件事做到了给定频率分布下的最优。
2. 哈夫曼树的构造方法：贪心思想的直观与证明
2.1 构造算法的四个步骤
哈夫曼树构造算法可能是整个数据结构课程里最“无脑”的贪心算法之一，本质就是反复做同一件事。完整流程如下：
- 把每个权重都看成森林里的一棵单节点树，所有根节点组成一个集合。
- 从集合里挑出根节点权重最小的两棵树。
- 把这两棵树作为左右子树，合并出一棵新树，新根的权重等于两者之和。
- 把新树放回集合，重复第 2 步，直到集合里只剩一棵树。
这个反复“挑最小、合并、放回去”的过程，一共要执行 n-1 次。初始有 n 棵树，每合并一次减少一棵，最后剩一棵就是哈夫曼树。整个过程不需要回溯，不需要调整前面的结构，贪心到底。
为什么用“每次都选最小”就能得到全局最优，而不是局部最优陷阱？这是整个算法最值得琢磨的地方，后面我会专门解释。先看一遍完整手算过程，对这个算法形成肌肉记忆。
2.2 一步步建树：2、3、5、7、11 的完整过程
以权重集合 {2, 3, 5, 7, 11} 为例，跟着走一遍。初始森林里有五棵单节点树。每一轮都取两个最小根权重合并，过程如下表：
| 轮次 | 当前森林（根权重） | 选中的两个权重 | 合并后的新权重 |
|---|---|---|---|
| 1 | 2, 3, 5, 7, 11 | 2, 3 | 5 |
| 2 | 5, 5, 7, 11 | 5, 5 | 10 |
| 3 | 7, 10, 11 | 7, 10 | 17 |
| 4 | 11, 17 | 11, 17 | 28 |
重点看一下第 2 轮：这时集合里有两个 5，一个是原始的叶子节点 5，一个是第 1 轮合并出来的内部节点 5。它们权重相同，选谁当左谁当右都行，没有任何区别，最终树的形状细节可能不同，但 WPL 完全一样。这里唯一的注意点是：内部节点和叶子节点权重相等的概率很高，处理时不要搞混它们背后的结构，只要权重数值参与比较即可。
最后一轮合并出的根节点权重 28，正好等于所有叶子权重之和。这也能用来检验整个过程有没有算错。
2.3 贪心为什么是对的
很多人学到这里会有一个疑问：每次只选两个最小的，万一这一步选了后面就亏了怎么办？这个问题值得认真回答，因为理解了它，才算真正理解哈夫曼算法的灵魂。
标准的证明思路是“交换论证”。考虑一棵真正最优的树，深度最深的两个叶子节点，它们的权重必然是所有叶子中最小的两个。为什么？假设最深的叶子中有一个节点的权重 x，它不是最小的，而另有一个权重更小的节点 y 待在更浅的位置，那把 x 和 y 交换，x 上移、y 下移。因为 x 的权重大但路径变短，y 的权重小但路径变长，整体 WPL 必然会下降。既然交换前已经是最优，说明这种局面不可能存在，所以最深的两个叶子必然是最小的两个权重。
既然两个最小权重的叶子在最深层，那把它们合并成一个父节点，用“父节点权重 = 两者之和”替代它们，问题的规模就从 n 个叶子缩小到 n-1 个，最小性不受影响。每合并一次，就等价于在原问题上做一次最优子结构的拆解。反复归纳下去，每一步“选两个最小”的操作都被证明是安全的。
这就是为什么哈夫曼树成为贪心算法的经典案例。它不是碰巧好用，而是有严格的交换论证做保证。面试或者考试里如果被问到“为什么哈夫曼一定最优”，把这个论证讲清楚，基本就稳了。
3. 从哈夫曼树到哈夫曼编码：压缩的本质
3.1 前缀编码：为什么解码不会产生歧义
树建好了，接下来就要给它一个用途。最经典的应用是哈夫曼编码：把每个叶子节点对应一个字符，从根出发往左走记 0，往右走记 1，走到某个叶子节点停下的路径，就是该字符的编码。
这种编码方式有一个极其重要的性质：它一定是前缀编码。所谓前缀编码，是指任何一个字符的编码，都不能是另一个字符编码的前缀。最简单的反例是：如果 a 的编码是 0，b 的编码是 1，c 的编码是 01，那么收到一段“01”，你根本不知道是 c 还是 a 后面跟着 b，这就是歧义。哈夫曼编码不会出现这种问题，因为每个字符都对应一个叶子节点，从根到叶子的路径是完整的，不可能出现“走到某个中间节点刚好停住”的情况。解码的时候，一路顺着 0 和 1 往下走，走到叶子就只能确定一个字符，然后回到根继续。这就是前缀编码天生无歧义的底层原因。
可以拿生活中的例子类比：你给同事安排值班表，为了减少记录量，给高频出现的同事用最简短的代号，低频的同事用长一点的代号，但前提是任何一个人的代号不能是另一个代号的开头，否则一登记就容易读串。哈夫曼编码就是在这种约束下把总记录长度压缩到最小。
3.2 编码表生成与实例
回到刚才建好的哈夫曼树，按“左 0 右 1”的约定，从上到下读出叶子编码。为了看清楚完整结构，我把树展开描述一遍：根节点 28，左孩子是叶子 11，右孩子是内部节点 17；17 的左孩子是叶子 7，右孩子是内部节点 10；10 的左孩子是内部节点 5，右孩子是叶子 5；最底下内部节点 5 的左右孩子分别是叶子 2 和叶子 3。
按照这个结构，从上到下给每个叶子编号，得到以下编码表：
| 字符（权重） | 哈夫曼编码 | 编码长度 |
|---|---|---|
| 11 | 0 | 1 |
| 7 | 10 | 2 |
| 5 | 111 | 3 |
| 2 | 1100 | 4 |
| 3 | 1101 | 4 |
验证一下总比特数：11×1 + 7×2 + 5×3 + 2×4 + 3×4 = 60，正好等于哈夫曼树的 WPL。这里能看到一个很有意思的对应关系：WPL 不只是树的带权路径长度，它同时就是在每个字符出现次数为权重的序列中，用哈夫曼编码压缩后的总比特数。树的深度就是编码长度，权重就是频率，这两个视角实际上是同一件事。
注意哈夫曼编码不是唯一的。如果某几轮合并时权重相等，左右子树对调，或者把“左 0 右 1”的约定换成“左 1 右 0”，都会产生不同形式的编码，但这些编码的总长度是一样的，都是最优的。平时做题或者看别人的代码，只要保证“建树规则一致、左右约定一致”，结果就是自洽的。
3.3 解码过程
解码是编码的逆过程，逻辑反而比编码更简单。拿到比特流之后，从根节点开始，遇到 0 走左，遇到 1 走右，每走到一个叶子节点就还原出一个字符，然后立刻回到根节点，继续消费后面的比特。
比如用刚才的编码表，比特流“010111001101”从左往右解：0 到叶子 11，解出第一个字符；接着走右 1 再走左 0，到叶子 7；然后 111 到叶子 5；接着 1100 到叶子 2；最后 1101 到叶子 3。整个过程一气呵成，中间不需要任何回溯，因为前缀编码保证了解码路径不会走进死胡同。
这里要特别强调一个工程项目里容易忽略的点：解码端必须拥有和编码端完全一致的树，或者完全一致的编码表。树如果对不上，解码结果就是一堆乱码。所以真实压缩格式里，要么把树结构写进文件头，要么用一个更聪明的办法——只存每个字符的编码长度，见后面第 5 章的规范哈夫曼编码。
4. 代码实现：手写一遍比看十遍更管用
4.1 用最小堆实现构造
哈夫曼算法的核心操作是“反复取集合里权值最小的两个元素”。这个需求天然适合用最小堆来实现。Python 里直接用heapq，每次取出两个最小根，合并后 push 回去，n-1 轮就得到整棵树的根。
我写了一段自认为比较干净的最小实现，包含了建树、编码表生成、编码和解码四个部分：
import heapq from collections import Counter class HuffNode: """哈夫曼树节点""" def __init__(self, weight, symbol=None, left=None, right=None): self.weight = weight # 权重，也就是出现次数 self.symbol = symbol # 叶子节点对应的字符，内部节点为 None self.left = left self.right = right def is_leaf(self): return self.symbol is not None def __lt__(self, other): # heap 比较节点时按权重，权重相同的情况保持一致性即可 return self.weight < other.weight def build_huffman_tree(freq): """freq 是 dict 或 Counter，例如 {'a': 5, 'b': 9, 'c': 12}""" heap = [HuffNode(w, ch) for ch, w in freq.items()] heapq.heapify(heap) while len(heap) > 1: left = heapq.heappop(heap) right = heapq.heappop(heap) parent = HuffNode(left.weight + right.weight, left=left, right=right) heapq.heappush(heap, parent) return heap[0] if heap else None def generate_code_table(node, code="", table=None): """深度优先遍历，生成 字符 -> 编码 的映射表""" if table is None: table = {} if node.is_leaf(): table[node.symbol] = code else: generate_code_table(node.left, code + "0", table) generate_code_table(node.right, code + "1", table) return table有一个极易写错的细节：__lt__这个方法。heapq在比较堆元素时，如果两个重量相等，就会尝试比较对象本身，而 Python 对象默认没有可比较的大小关系，不实现__lt__会在合并相等权重时直接给你抛TypeError。这是新手写哈夫曼实现最常见的崩溃点之一。
4.2 编码、解码与比特打包
建树之后，编码就是对原文本统计频率，然后逐个查表替换。解码则像前面说的，沿着树往下走。完整过程看这段：
def huffman_encode(text): freq = Counter(text) if not freq: return {} if len(freq) == 1: # 只有一种字符时没有真正的树，约定编码为 0 return {next(iter(freq)): "0"} root = build_huffman_tree(freq) return generate_code_table(root) def huffman_decode(bit_string, root): result = [] node = root for bit in bit_string: node = node.left if bit == "0" else node.right if node.is_leaf(): result.append(node.symbol) node = root return "".join(result)解码函数有个隐藏假设：传入的root和编码时使用的树完全一致。工程上，把整棵树序列化存进文件是可行的，但会占用不小的空间。实际压缩格式通常不直接存树，而是存每个字符的编码长度，然后用“规范哈夫曼编码”在解码端重建编码表。这个技巧能显著减少文件头体积，后面会展开讲。
另外，huffman_encode返回的是字符到二进制字符串的映射，真正写文件时不能把 “0” 和 “1” 当成字符写进去，那样反而把数据撑大了。正确做法是把每 8 个 bit 打包成一个字节。打包逻辑很简单，但很多初学压缩的人会栽在这里：
def bits_to_bytes(bits): """把 '0101...' 形式的字符串打包成字节序列，最后不足 8 位补 0""" buf = bytearray() for i in range(0, len(bits), 8): byte = 0 for j, bit in enumerate(bits[i:i + 8]): byte |= int(bit) << (7 - j) buf.append(byte) return bytes(buf)解码端拿到字节后，首先要做逆操作，把每个字节展开成 8 位比特，再送入哈夫曼树解码。头文件里的长度信息或者特殊的结束标记，就是用来应对最后那几位补零问题的。
4.3 复杂度分析
整个哈夫曼构造过程的复杂度非常好算：初始建堆是 O(n)，其中 n 是叶子节点数量；之后要合并 n-1 次，每次涉及两次弹出和一次压入，每次堆操作都是 O(log n)。所以总体复杂度是 O(n log n)。
编码阶段，如果做成查表，每编码一个字符的时间是 O(1)，遍历整段文本就是 O(m)，m 是文本长度。解码阶段稍有不同，每还原一个字符都要从根重新走到叶子，路径长度就是编码长度，平均意义上接近 O(1) 常数，最坏情况下接近 O(n)。整体来看，哈夫曼的编解码速度非常快，这也是它几十年后依然活跃在各类压缩算法底层的原因之一。
空间方面，额外需要 O(n) 存堆和树。对字符集 256 的字节流来说，n 最多 256，代价完全可以忽略。所以哈夫曼是那种“时间又快、空间又省、实现又简单”的算法，非常难得。
5. 常见问题排查与避坑记录
5.1 构造阶段的常见错误
我见过好几次有人把内部节点当成叶子节点，在合并完之后竟然继续用原来的两个叶子去参与下一轮比较，导致整个树的结构完全错误。记住：权重 5 的叶子一旦和权重 2、3 合并，这个 5 就“消失”了，取而代之的是一个新创建的内部节点 5。旧节点不再属于森林，否则会出现重复计数。
还有个考试高频陷阱：内部节点不能携带字符。哈夫曼编码的字符只允许出现在叶子节点上，如果为了让某个字符的编码更短而把它放到内部节点，就会立刻破坏前缀编码的性质。判断一棵树是不是合法的哈夫曼树，先看字符是不是都在叶子上，再看 WPL 是不是最小，顺序别搞反。
5.2 编码和解码阶段的坑
左右子树约定不一致是个隐蔽问题。有的人建树时习惯“左小右大”，生成编码时却按“左 1 右 0”，两套规则打架，最后解出来的文本首尾错乱。建议在代码里把约定固定成一个全局常量，比如LEFT_BIT = "0"、RIGHT_BIT = "1"，不要散落在多个函数里手写 0 和 1。
单字符输入是另一个边界问题。如果整个文本只有一种字符，比如全是“a”，那哈夫曼树退化成只有一个节点，按正常流程走下来，编码表里 a 的编码是空字符串。空编码没法写文件，必须在编码前单独处理，我习惯直接把唯一字符的编码约定为 “0”，并在文件头记录一个标志。
最后就是存储问题。一次压缩流程的完整数据包应该包含：哈夫曼树（或编码长度表）、编码后的比特流、必要的长度信息。很多人自己玩的时候只写了编码和解码函数，却忘了把树存下来，结果是压缩完自己都解不开。设计文件格式时，把头部信息、数据区和长度标记三件事一起规划清楚。
5.3 工程化的几个进阶技巧
如果只是应付考试，知道前面这些已经够了。但想在真实项目里用得顺手，再补两个实战技巧。
第一个是规范哈夫曼编码。它的思路是：解码端其实不需要知道树长什么样，只需要知道每个字符的编码长度。按“码长递增、同码长按字符顺序”的规则，就能推导出一套唯一的规范编码。像 DEFLATE 算法（ZIP、gzip、PNG 都用它）就采用这种方案，文件头只存码长序列，省掉了一大块树结构数据。
第二个是比特流边界处理。真实编码时，最后一组可能凑不满 8 个 bit，打包时会补 0。解码端如果不记录原始比特长度，就会把补的 0 当成有效数据。常见做法是在文件头保存“最后一个字节的有效位数”，或者保存原始比特流总长度，二选一，但绝不能两个都不写。
6. 哈夫曼编码在真实世界中的位置
6.1 哪些压缩算法在用哈夫曼
哈夫曼编码至今仍然是许多主流压缩格式的重要基石。DEFLATE 把 LZ77 窗口匹配和哈夫曼编码结合，广泛用于 ZIP、gzip、PNG 图像。JPEG 在量化后的 DCT 系数上使用哈夫曼编码，MP3 和许多视频编码标准同样包含哈夫曼风格的熵编码环节。传真机协议（比如 CCITT Group 3）也用了类似思想。可以说，凡是需要“把分布不均匀的符号变成尽量短的比特流”的场景，几乎都能看到哈夫曼的影子。
6.2 哈夫曼编码的局限与替代方案
但哈夫曼也有它的天花板：每个符号的编码长度必须是整数个 bit。如果某个字符的真实概率是 1/3，理论上最优编码长度是 log₂3 ≈ 1.585 bit，哈夫曼却只能分配 1 bit 或 2 bit，必然产生浪费。概率分布越“偏”，这种整数长度限制造成的损失越明显。算术编码、区间编码和近年流行的 rANS 熵编码，可以做到接近理论极限的分数比特编码，这就是为什么现代压缩算法（如 LZMA、Brotli、Zstandard）更倾向于使用这些更复杂的熵编码器，而非纯粹的哈夫曼。
6.3 动手做个小实验
写代码跑一个实验，比背十遍原理都管用。我建议你拿一本英文电子书的前几章做素材，统计一下字符频率，然后实现哈夫曼编码，对比压缩前后的大小。大概率你会得到一个 1.5 到 2 倍左右的压缩率，然后再试试把“the”这种高频单词当作一个整体符号参与统计，压缩率会进一步提升。把这个实验做完，你对“频率如何决定编码长度”的体会会深刻很多。
我自己当时做这个小实验时还有意外的收获：发现同样的频率表，左右子树对调之后编码完全变了，但总长度不变。这让我彻底理解了“最优”指的是总代价最优，而不是编码形式唯一。也正因为这一点，面试官特别喜欢在这里追加提问“哈夫曼编码唯一吗”。答案是不唯一，但最优长度是确定的，先想清楚这层，后面遇到再刁钻的变形题也不慌。
