哈夫曼树与哈夫曼编码详解：从手算建树到编码解码全流程

提到数据结构里的哈夫曼树与哈夫曼编码，很多人第一反应是“贪心”“最优二叉树”“无损压缩”，但真让自己手动构造一棵树，或者分析某个编码为什么是最优，又容易卡住。这篇文章就用一个具体到不能再具体的例子，带着你把哈夫曼树与哈夫曼编码从构造到编码、解码完整走一遍，同时把“为什么每次要选两个最小”“编码表为什么不唯一”这些容易混的问题一次说清楚。适合正在复习数据结构的同学、准备算法面试的开发者，以及想做文本压缩却不知道从哪下手的入门选手。

我不打算堆公式，只讲你手动能复现的步骤。你只需要一张纸、一支笔，跟着下面的字符频率表走一遍，五步就能建出一棵哈夫曼树。建完之后，我会继续用一个二进制串完成编码和解码，再给出能直接运行的代码。这套流程一旦跑通，后面再看任何关于哈夫曼的变种算法，基本不会发怵。

1. 先搞清楚：哈夫曼树与哈夫曼编码到底解决什么问题

1.1 从一份“能再小一点吗”的文本说起

假设我有一份文本，里面只有6种不同字符，统计下来出现次数分别是：A出现5次，B出现9次，C出现12次，D出现13次，E出现16次，F出现45次，总共100个字符。

如果不做任何压缩，用固定长度编码，6种字符至少需要3位二进制，100个字符占300位。注意这里的“位”就是0和1，一个字符对应3个bit。看上去不贵，但F几乎占了一半，却和只出现5次的A用同样的3位，显然浪费。这就是哈夫曼树登场的基础场景：给高频字符短的编码，给低频字符长的编码，让总长度尽量小。

你可以把这件事类比成办公室打印材料：热门的员工手册印100份，冷门的项目存档只印3份，如果两者都印成一样的厚度，仓库很快就满了。所以“按热度分配资源”是哈夫曼树最底层的直觉。

1.2 最优前缀编码的三个关键词

要理解哈夫曼编码，先抓住三个关键词：变长编码、前缀编码、最优二叉树。

变长编码的意思是每个字符的编码长度可以不同。比如字符X用1位，字符Y用5位，都合法。但变长编码最怕歧义：某个二进制串到底该切成几段，每段对应哪个字符，必须能唯一确定。

前缀编码就是为了解决歧义。它的定义很严格：任何一个字符的编码，都不能是另一个字符编码的前缀。举个例子，“0”“10”“110”“111”这组编码就满足前缀性质；但“0”“01”“1”就不满足，因为“0”是“01”的前缀。如果编码满足前缀性质，解码时就不需要额外分隔符，从左往右读一定能唯一还原。

最优二叉树，也叫带权路径长度最小的二叉树。每个叶子节点放一个字符，叶子到根节点的深度就是这个字符的编码长度，叶子的权就是字符出现次数。带权路径长度WPL，就是所有字符的“次数乘以编码长度”加总。哈夫曼算法干的事，就是构造一棵让WPL最小的二叉树。

为什么树恰好能对应编码？因为每走一位二进制，只有0和1两个方向，所以每个内部节点最多两个分支。把所有叶子挂在二叉树上，每个叶子都有一条从根到叶子的唯一路径，路径上的0/1序列就是编码。树结构天然保证前缀性质，因为一条路径不可能同时是另一条路径的前缀，除非一个叶子挂在另一个叶子的路径中间，而这是不可能的。

2. 用一个真实字符表手动构造一棵哈夫曼树

2.1 示例数据与手算准备

先固定一份数据，后面所有推导都围绕它。字符和出现次数如下：

手算准备很简单：把每个字符看成一棵只有一个节点的树，节点上记录“字符”和“权重”。权重可以不是出现次数，你用概率、文件大小、金额权重都可以，只要有大小可比性就行。我这里直接用次数，因为最直观。

初始化之后，你是拥有“一堆树”的人，专业说法叫森林。接下来的核心动作只有两个：挑两棵最小树，合并；重复一百次直到只剩一棵树。为什么是“最小”而不是“最大”，我在后面用反例说明。

2.2 五步合并：从森林变成一棵树

合并规则非常机械：从森林中选两个权重最小的节点，把它们作为新节点的左右子树，新节点权重等于两者之和，然后把新节点放回森林。重复直到森林里只剩一个节点，这个节点就是哈夫曼树的根。

第一步，当前权重是5、9、12、13、16、45，最小的是5和9。把A和B合并，得到权重14的节点。森林变成：12、13、14、16、45。

第二步，最小的是12和13。把C和D合并，得到权重25的节点。森林变成：14、16、25、45。

第三步，最小的是14和16。把第一步的AB节点和E合并，得到权重30的节点。森林变成：25、30、45。

第四步，最小的是25和30。把CD节点和ABE节点合并，得到权重55的节点。森林变成：45、55。

第五步，只剩45和55，合并成权重100的根节点。森林里只剩一棵树，构造结束。

这棵树画成文字大概是：

(100) / \ f(45) (55) / \ (25) (30) / \ / \ c(12) d(13)(14) e(16) / \ a(5) b(9)

如果你习惯把高频字符放在左边，完全可以把左右互换，不影响正确性。但一旦定下“左边0右边1”，整棵树就必须按这个规则统一解释。

2.3 为什么“每次取两个最小”是最优的

有人会问，每次合并不就是“贪心”吗？凭什么保证全局最优？这是哈夫曼编码最值得深挖的点。

直观解释是这样的：权重越大的字符，越希望它离根近，编码越短。如果第一次不合并5和9，而是把5和45合并，高频字符F就会被拖到很深的位置。F出现45次，路径每深一层，总代价就多45位，这是很大的损失。反过来，把出现5次和9次的低频字符放在最深处，即使路径长一点，对总代价的拖累也有限。

如果要稍微严谨一点，可以用交换论证。在一棵最优树里，权重最小的两个叶子一定位于最深层，而且一定是兄弟。如果它们不在最深层或者不是兄弟，那么把权重更小的叶子换到更深的位置、把权重更大的叶子换到更浅的位置，WPL只会更小。换句话说，任何违背“最小两个先合并”的树，都能通过若干次交换变得更优，所以哈夫曼算法构造出来的树确实是最优的。

这个证明思路在面试里很容易被追问，能说清楚“交换后WPL不增”就基本过关。

2.4 WPL与压缩率怎么算

现在我们按“左0右1”的约定，从根往下走，得到每个字符的编码：

看看规律：F只出现一次? 不对，F出现45次，但编码只有1位；A只出现5次，编码却是4位。符合“高频短码、低频长码”的设计目标。

WPL按下式计算：

5×4 + 9×4 + 12×3 + 13×3 + 16×3 + 45×1 = 20 + 36 + 36 + 39 + 48 + 45 = 224

如果还用等长3位编码，总长度是100×3=300。等于每100个字符省下76位，压缩率约74.7%。注意这里的压缩率对比的是纯编码部分，没有算额外信息开销。

这里分享一个手算小技巧：把所有内部节点（就是每次合并产生的新节点）的权重加起来，也会得到WPL。上面每次合并后的内部节点权重依次是14、25、30、55、100，加总正好是224。 这个性质可以用来验证手动计算结果，非常实用。

3. 编码和解码的完整流程演示

3.1 从树到编码表：左0右1

树建好后，要把它变成一张字符到二进制串的映射表。做法是深度优先遍历：从根开始，向左走拼一个“0”，向右走拼一个“1”，每到达一个叶子，就把当前路径字符串记为该字符的编码。

用伪代码写就是：

procedure dfs(node, path): if node 是叶子节点: 编码表[node.ch] = path return dfs(node.left, path + "0") dfs(node.right, path + "1")

为什么用“左0右1”而不是“左1右0”？没有强制要求，完全看约定。只要编码和解码用同一棵树、同一个方向约定，就不会出错。工程上为了统一，通常固定写左0右1。

3.2 一次完整的编码和解码

假设原始文本只有几个字符拼接而成：A、B、F、C、D、E、F。我不加分隔符，直接连起来写就是“A B F C D E F”。

逐字符替换成编码：

A → 1100
B → 1101
F → 0
C → 100
D → 101
E → 111
F → 0

拼接后得到二进制串：

1100110101001011110

解码时从根出发，每读一位二进制，就向左或向右走一步。规则是：读到0去左子节点，读到1去右子节点；当走到一个持有字符的叶子节点时，输出该字符，然后立刻回到根，继续读下一位。

拿开头的4位“1100”演示：从根出发，1走到右边节点，1再走到右边节点，0走到左边节点，0走到左边叶子，这个叶子是A，输出A。回到根，接着处理下一个4位“1101”，输出B。接下来的一位是0，直接从根左走到F，输出F。后面“100”输出C，“101”输出D，“111”输出E，最后0输出F。整个二进制串完美还原成原文本。

这个“到达叶子立刻回到根”的细节非常关键。很多人写解码时忘记复位，结果后面所有字符都错位。树本身不会告诉你“该停了”，必须靠叶子节点信息判断。

3.3 前缀性质怎么保证解码无歧义

为什么解码不需要逗号、空格这类分隔符？靠的就是前缀性质。

想一个反例：如果编码表是 a=0、b=01、c=1，那么二进制串“01”可以解释成“a c”吗？0是a，剩下1是c，看起来可以；但它也可以整体解释成b。两条解码路径都说得通，这就失败了。问题根源就是a的编码0是b编码01的前缀。

哈夫曼编码不存在这个问题，因为每个字符对应树上的一个叶子。如果一个编码是另一个编码的前缀，意味着某个叶子出现在另一片叶子的根路径上，这在二叉树里不会发生。所以只要按树解码，任何合法二进制串都只能有一种切分方式。

这个性质也是为什么哈夫曼编码能“不加分隔符”省位数的原因。如果每个编码后面都补一个分隔符，那省下的位数又会被吃回去，压缩效果大打折扣。

4. 最小可用代码：建树、编码、解码一起搞定

4.1 数据结构与建树主流程

光说不练假把式，直接上一份能跑的Python代码。核心数据结构就一个Node，包含权重、字符、左右子节点。叶子节点记录字符，内部节点不记录字符。

from heapq import heapify, heappop, heappush class Node: def __init__(self, weight, ch=None, left=None, right=None): self.weight = weight self.ch = ch self.left = left self.right = right def build_huffman_tree(freq): counter = 0 heap = [] for ch, w in freq.items(): heap.append((w, counter, Node(w, ch))) counter += 1 if not heap: return None heapify(heap) while len(heap) > 1: w1, _, n1 = heappop(heap) w2, _, n2 = heappop(heap) merged = Node(w1 + w2, left=n1, right=n2) heappush(heap, (merged.weight, counter, merged)) counter += 1 return heappop(heap)[2]

建树流程和手算步骤完全一致。先用一个最小堆维护森林，每次弹出两个权重最小的节点，合并后再放回去。使用堆而不是普通列表，是因为每次取最小值的复杂度只有O(log n)，整个建树过程是O(n log n)。n是字符种类数。

counter在这里不是业务数据，而是为了破坏“权重相等时比较Node对象”的尴尬局面。这个细节很多人第一次写都会踩，后面专门讲。

4.2 生成编码表与解码函数

建完树，下一步生成编码表、编码串、解码串。这里给出完整的几个函数。

def build_codes(root, prefix="", code_map=None): if code_map is None: code_map = {} if root is None: return code_map if root.ch is not None: code_map[root.ch] = prefix return code_map build_codes(root.left, prefix + "0", code_map) build_codes(root.right, prefix + "1", code_map) return code_map def huffman_encode(text, code_map): return "".join(code_map[ch] for ch in text) def huffman_decode(bits, root): if root is None: return "" result = [] node = root for bit in bits: node = node.left if bit == "0" else node.right if node is None: raise ValueError("非法编码串，走到空节点") if node.ch is not None: result.append(node.ch) node = root return "".join(result)

build_codes递归遍历整棵树，路径字符串就是编码。huffman_encode很直白，查表拼接。huffman_decode从根开始逐位移动，遇到叶子输出并回到根。

用第2节的数据测试，freq填成字典形式，应该得到和手算完全一致的编码表。如果结果不一致，说明左右子树顺序或者合并平局策略和文章不同，但WPL依然相同，这属于正常现象。

4.3 一个很多人都踩过的坑：堆比较器

在Python里，heapq比较元组时会先比较第一个元素，如果第一个元素相等，就继续比较第二个元素。如果你把堆元素写成(weight, node)，当两个节点权重相同时，Python就会去比较Node对象，而Node类没有定义“小于”运算符，直接抛出TypeError: '<' not supported between instances of 'Node' and 'Node'。

解决办法有三种：

第一种，在元组里加一个单调递增的序号(weight, counter, node)，让第二个元素永远不相等。文章代码就是这么写的。

第二种，给Node实现__lt__方法，按权重比较，权重相等时再按某个稳定字段比较。这样堆可以直接比较Node对象。

第三种，用对象包装，在外部显式比较权重。但代码会啰嗦很多。

这个问题不只是Python有，Java的PriorityQueue、C++的优先队列同样需要自定义比较器。凡是“多个元素权重相同”的场景，都要想好平局怎么打破。平局策略不同，得到的树可能不同，但WPL仍然一样。

4.4 工程边界：单字符、相同权重、空串

代码能跑通标准案例之后，一定要考虑几个边界情况。

第一，只有一个字符的情况。如果freq里只有一个字符，while循环不会执行，根节点直接就是一个叶子。此时build_codes返回的编码表里，该字符的编码是空字符串。空字符串参与拼接会被“吞掉”，解码逻辑也会出问题。常见处理方案是特殊约定：单字符时编码为“0”，解码时只要二进制串非空，就全部还原成那个字符。

第二，所有字符权重相同。比如5个字符都是10，哈夫曼树会退化成接近完全二叉树，编码长度都非常接近，压缩率不如权重悬殊时明显。算法仍然正确，只是收益变小。

第三，空输入。没有任何字符时，不能建树，也不能编码解码，业务层需要单独拦截。

内部节点不能存字符，这是另一个容易犯错的地方。如果把字符错误地放到内部节点上，解码走到中间就会输出内容，后面全部崩坏。写代码时建议加断言，非叶子节点的ch保持None。

5. 常见问题与排查技巧实录

5.1 哈夫曼树是不是只有一棵

不是。 很多资料给出的哈夫曼树不一样，但都是对的。因为当存在多个相同权重的节点时，选择不同的两个节点合并，会产生不同的树结构；左右子树交换也会产生不同树。这些不同的树共享同一个最优WPL，只是编码表不同。

那为什么网上示例的编码表往往一致？因为很多教材人为定了平局规则，比如“权重相同取字符编码更小的”“总是先合并左子树”，并不是算法本身强制要求。

工程上如果希望一次压缩的结果稳定可复现，一定要给节点加一个二级排序键，比如字符本身、插入序号。否则同一段文本每次运行可能得到不同压缩串，给调试和比对造成麻烦。

5.2 WPL算错？试试内部节点求和

手动计算WPL，最容易错的是漏掉某个叶子，或者把内部节点的权重重复算了一遍。

我通常用两个方法交叉验证。方法一，叶子计算法：直接做“次数乘以编码长度”的累加，例如5×4+9×4+12×3+13×3+16×3+45×1=224。方法二，内部节点求和法：把所有合并产生的新节点权重加起来，14+25+30+55+100=224。两个结果一致，基本可以放心。

内部节点求和的原理其实不复杂：每次合并新节点，相当于把两个子树的叶子深度加深了一层，新节点权重就是这些叶子新增的代价。所有新节点权重累加，正好等于所有叶子深度乘以权重的总和。

5.3 解码异常多半出在这三个地方

如果解码结果和原文对不上，优先检查三个位置。

第一，编码表和解码树是不是同一棵。 经常有人用一个临时树生成编码表，再用另一棵手工画的树去解码，路径当然错位。解决方案是编码和解码必须共享同一个根节点，或者至少共享同一份编码表。

第二，有没有“叶子输出后回到根”。 编码串是连续的，解码器必须在每个叶子输出后把当前节点重置为根。漏掉这行，后面的字符会全部偏移。

第三，编码串是否被截断。 如果二进制串最后停在内部节点，说明数据不完整。解码函数应该检查最终节点是否为叶子，不是就报错，而不是静默返回。

5.4 压缩效果不理想的原因

用了哈夫曼编码，压缩率却很差，常见原因有四种。

一是数据量太小。哈夫曼编码需要额外存储编码表或树结构，如果原始数据只有几十字节，编码表可能比正文还大。二是字符频率分布均匀，比如每个字符出现次数都差不多，哈夫曼树很难给出短码优势，编码总长度接近等长编码。三是输入本身已经是压缩格式，比如图片、视频、zip文件，在这些数据上再做哈夫曼，几乎没有收益。四是没有把编码表算进存储成本，只比较了编码后数据的位数，实际落地时编码表也是要传的。

6. 一些实操心得和扩展思路

6.1 什么时候真的适合用哈夫曼编码

根据我实际使用的经验，哈夫曼编码最适合“字符频率差异明显”的无损压缩场景。典型例子是英文文本、日志文件、自然语言数据。比如日志里某个错误码出现次数特别多，哈夫曼能明显减少体积。

如果数据已经做过压缩，或者字符分布非常均匀，哈夫曼的意义就不大。很多流式压缩算法只是把哈夫曼作为最后一环，前面还有游程编码、LZ77等更复杂的处理。单独的教科书式哈夫曼，更适合做理解和教学，而不是直接挑战高压缩率。

小文件千万别直接用哈夫曼单枪匹马压。你不仅要传编码表，还要考虑文件头、校验位，这些开销在小文件里占比很高。我见过有人把几十字节的配置用哈夫曼压，结果压缩后比原文件还大，得不偿失。

6.2 长得像哈夫曼的算法们

哈夫曼树的思想，本质是“两个最小合并”的贪心模式，它在算法题里长着很多张脸。

比如合并石子问题：若干堆石子，每次合并任意两堆，付出两堆重量之和的代价，问总代价最小是多少。解法就是哈夫曼树，用优先队列不断取两堆最小的合并。又比如最优归并模式：把若干长度不等的有序表归并成一个有序表，希望比较次数最少，模式同样相同。

更深一层，哈夫曼编码还可以和算术编码放在一起对比。哈夫曼为每个字符设计离散码字，算术编码则把整段消息映射到一个0到1之间的实数区间，后者更逼近熵极限，但实现复杂度也更高。面试时不必展开太深，能点出“哈夫曼是离散码字方案、算术编码是区间编码方案”就足够了。

6.3 最后想说的几个细节

手动在纸上推一遍，比背十遍公式有用。我强烈建议你用6个字符、频率悬殊一点的数据开始，像我上面那样列合并表、画树、写编码表、算WPL。这个过程做完，哈夫曼树就再也不会是“背过的算法”了。

第二件小事：写代码时先把解码函数调通，再回来看压缩率。很多初学者只盯着编码长度，却忘了压缩的前提是能无损还原。我会在测试里放一个循环，随机生成文本，编码再解码，断言两者完全一致。这个测试比手写用例更能暴露问题。

第三件小事：编码表的序列化也要当一等公民。很多实际项目里，编码表没有妥善保存，压缩后的数据根本解不开。一个简单做法是随压缩数据一起保存每个字符的出现次数，解压时重新建树，这样比保存整张表更稳，也避免了对树结构做复杂序列化。

哈夫曼树与哈夫曼编码的价值不在于“能写出不报错的代码”，而在于你能从一行0和1里，看出概率、信息量和工程取舍。把这篇例子吃透，再去看DEFLATE、ZLIB这类现代压缩方案里的哈夫曼用法，你会发现那些复杂系统里最核心的骨架，其实就是今天手算的这五步合并。