1. 从"变长编码"说起：赫夫曼树到底在解决什么问题
很多人第一次接触赫夫曼树，是在数据结构课的树章节末尾，教材往往用一段"带权路径长度最小"的定义带过，然后直接跳到代码。结果就是：考试能画树，真让你写一个文件压缩工具，完全不知道从哪下手。我当年也是这样，直到自己动手写了一个完整的压缩解压程序，才真正理解赫夫曼这套东西的精妙之处。
先说清楚它解决的核心问题：如何用最少的比特数表示一组出现频率不同的数据。举个最直观的例子，假设有一段文本，里面字符 A 出现了 80 次，B 出现 10 次，C 出现 5 次，D 出现 5 次。如果每个字符都用固定 2 位二进制表示（00、01、10、11），总长度是 (80+10+5+5)×2 = 200 位。但如果我们让 A 用 1 位（比如 0），B 用 2 位（10），C 用 3 位（110），D 用 3 位（111），总长度就变成 80×1 + 10×2 + 5×3 + 5×3 = 120 位，直接省了 40%。
这就是变长编码的威力：出现频率高的字符用短码，频率低的用长码。但变长编码有个致命问题——如果随便分配，解码时会产生歧义。比如 A=0，B=00，那么"00"到底是两个 A 还是一个 B？所以必须满足前缀编码约束：任何一个字符的编码都不能是另一个字符编码的前缀。赫夫曼树就是构造最优前缀编码的经典算法，它保证在满足前缀约束的前提下，加权路径长度（也就是总编码长度）最小。
这套东西的实际应用场景非常广：文件压缩（ZIP、GZIP 的底层就有它的影子）、图像格式（JPEG 的熵编码阶段）、通信协议里的数据编码，甚至一些数据库的索引压缩。理解赫夫曼树，不只是为了应付考试，而是掌握一种"用频率换空间"的通用思维。
这篇文章我会从原理推导讲到完整代码实现，覆盖数据压缩、创建编码表、解码、压缩文件、解压文件这五个环节，每一步都给出可运行的 Java 代码和实测说明。适合已经了解二叉树基本操作、想真正把赫夫曼树用起来的读者。如果你连二叉树的遍历都还不熟，建议先补一下基础再回来。
2. 赫夫曼树的构造原理：为什么贪心策略能得到最优解
2.1 带权路径长度的数学定义
在动手写代码之前，必须把几个核心概念理清楚，否则后面代码里的每一步操作你都会觉得"凭什么是这样"。
先定义几个术语：
- 路径长度：从根节点到某个节点的边数。根节点到自己是 0。
- 节点的权：这个节点代表的字符出现的频率（次数）。
- 带权路径长度（WPL）：节点的权 × 从根到该节点的路径长度。
- 树的带权路径长度：所有叶子节点的 WPL 之和。
赫夫曼树的目标就是：给定 n 个带权的叶子节点，构造一棵二叉树，使得整棵树的带权路径长度最小。这样的树也叫最优二叉树。
用前面的例子验证一下。字符 A(80)、B(10)、C(5)、D(5)，如果构造出的树让 A 的路径长度是 1，B 是 2，C 和 D 是 3，那么 WPL = 80×1 + 10×2 + 5×3 + 5×3 = 120。这个 120 就是总编码位数，和前面算的一致。
2.2 贪心构造：每次合并最小的两个
赫夫曼当年提出的算法非常优雅，核心就一句话：每次从节点集合中取出权值最小的两个节点，合并成一个新节点，新节点的权是两者之和，然后把新节点放回集合，重复直到只剩一个节点。
这个策略为什么能得到全局最优？直觉上的解释是：权值小的节点应该离根远一点（路径长），权值大的节点应该离根近一点（路径短）。每次合并最小的两个，相当于把最"不重要"的两个先放到树的深处，它们的路径长度自然就长。而合并产生的新节点权值是两者之和，会参与后续的比较，保证整体平衡。
严格的数学证明用的是贪心选择性质和最优子结构，这里不展开，但你可以这样理解：假设最优树里权值最小的两个节点不是兄弟，那么把它们交换成兄弟，WPL 不会增大。所以一定存在一棵最优树，让最小的两个节点互为兄弟。既然它们一定是兄弟，那把它们合并成一个节点，问题规模就缩小了，递归下去就是赫夫曼算法。
我用一个具体例子走一遍构造过程，字符和频率如下：
| 字符 | 频率 |
|---|---|
| A | 5 |
| B | 7 |
| C | 10 |
| D | 15 |
| E | 20 |
| F | 43 |
第一步：取最小的 5(A) 和 7(B)，合并成 12。集合变成 {10, 12, 15, 20, 43}。 第二步：取 10(C) 和 12，合并成 22。集合变成 {15, 20, 22, 43}。 第三步：取 15(D) 和 20(E)，合并成 35。集合变成 {22, 35, 43}。 第四步：取 22 和 35，合并成 57。集合变成 {43, 57}。 第五步：取 43(F) 和 57，合并成 100。结束。
最终树的根权值是 100，正好等于所有频率之和，这是个很好的自检点——根节点的权值一定等于所有叶子权值之和。
2.3 编码表的生成：左 0 右 1
树构造好之后，从根节点出发，向左走记 0，向右走记 1，走到叶子节点时路径上的 0/1 序列就是这个字符的赫夫曼编码。
按上面的例子，F(43) 离根最近，编码最短；A(5) 和 B(7) 在最深处，编码最长。具体编码取决于合并时谁放左边谁放右边，但无论怎么放，WPL 都是最小的。这一点很重要：赫夫曼编码不唯一，但最优性是确定的。所以你在不同实现里看到同一组数据生成不同的编码，是正常现象，只要 WPL 一致就没问题。
这里有个容易踩的坑：合并两个节点时，新节点的权值是两者之和，但新节点本身不对应任何字符，它只是内部节点。只有原始字符对应的节点才是叶子。生成编码表时，必须只对叶子节点记录编码，内部节点的路径不能作为编码。
3. 手写赫夫曼树：节点设计、优先队列与建树代码
3.1 节点类的设计取舍
先看节点类怎么设计。最直接的想法是搞一个Node类，包含权值、字符数据、左右子节点引用。但这里有个细节：内部节点没有字符，只有叶子节点才有。所以字符字段对于内部节点是空的。
public class HuffmanNode implements Comparable<HuffmanNode> { Byte data; // 存放字符对应的字节，内部节点为 null int weight; // 权值，即出现频率 HuffmanNode left; HuffmanNode right; public HuffmanNode(Byte data, int weight) { this.data = data; this.weight = weight; } @Override public int compareTo(HuffmanNode o) { // 按权值升序，优先队列会用到 return this.weight - o.weight; } @Override public String toString() { return "Node[data=" + data + ", weight=" + weight + "]"; } }为什么用Byte而不是char？因为后面要做文件压缩，文件里是字节流，不是字符流。用Byte可以统一处理文本和二进制文件。如果你只处理纯文本，用char也行，但通用性差一些。这是我踩过的坑：一开始用char写，处理中文文本时因为编码问题各种乱码，换成Byte之后清爽多了。
实现Comparable接口是为了配合PriorityQueue。赫夫曼算法每次要取最小的两个节点，用优先队列是最自然的选择，取最小值的时间复杂度是 O(log n)，比每次排序 O(n log n) 高效得多。
3.2 用优先队列建树
建树的核心逻辑就是把所有叶子节点丢进优先队列，然后循环取出两个最小的合并。
public static HuffmanNode buildHuffmanTree(byte[] bytes) { // 1. 统计每个字节出现的次数 Map<Byte, Integer> freqMap = new HashMap<>(); for (byte b : bytes) { freqMap.merge(b, 1, Integer::sum); } // 2. 为每个字节创建叶子节点，放入优先队列 PriorityQueue<HuffmanNode> queue = new PriorityQueue<>(); for (Map.Entry<Byte, Integer> entry : freqMap.entrySet()) { queue.offer(new HuffmanNode(entry.getKey(), entry.getValue())); } // 3. 循环合并，直到只剩一个节点 while (queue.size() > 1) { HuffmanNode left = queue.poll(); HuffmanNode right = queue.poll(); // 新节点的权值是两者之和，没有字符数据 HuffmanNode parent = new HuffmanNode(null, left.weight + right.weight); parent.left = left; parent.right = right; queue.offer(parent); } // 队列里剩下的就是根节点 return queue.poll(); }这段代码有几个值得说的点。
第一，freqMap.merge(b, 1, Integer::sum)是 Java 8 的写法，等价于"如果 key 存在就加 1，不存在就设为 1"，比手写 if-else 简洁。
第二，合并时left和right谁在左谁在右其实无所谓，因为最终编码不唯一。但为了结果可复现，建议固定一个顺序，比如权值小的放左边。不过优先队列 poll 出来的顺序本身就不保证稳定，所以严格可复现需要额外处理，一般场景不用纠结。
第三，边界情况必须处理：如果输入只有一个字节（比如整个文件都是同一个字符），那么队列里只有一个节点，while 循环不执行，直接返回这个叶子节点。这时候它既是根也是叶子，编码就是空字符串或者单个 0。后面生成编码表和解码时都要考虑这种情况，否则会出 bug。我实测时用全 'a' 的文件测试，一开始就卡在这里，解码出来是空的。
3.3 生成赫夫曼编码表
有了树，接下来遍历它生成编码表。用递归最自然，用一个StringBuilder记录路径。
// 用于存放编码表：字节 -> 编码字符串 static Map<Byte, String> huffmanCodes = new HashMap<>(); public static Map<Byte, String> getCodes(HuffmanNode root) { if (root == null) { return null; } huffmanCodes.clear(); // 根节点的路径为空 getCodes(root, "", new StringBuilder()); return huffmanCodes; } private static void getCodes(HuffmanNode node, String code, StringBuilder sb) { StringBuilder sb2 = new StringBuilder(sb); sb2.append(code); if (node.data == null) { // 内部节点，继续递归 if (node.left != null) { getCodes(node.left, "0", sb2); } if (node.right != null) { getCodes(node.right, "1", sb2); } } else { // 叶子节点，记录编码 huffmanCodes.put(node.data, sb2.toString()); } }这里有个细节：每次递归都 new 一个StringBuilder，是为了避免回溯时状态污染。如果你直接共用一个 StringBuilder，左子树走完回来，右子树的路径会带上左子树的残留。这是递归里非常经典的坑，我见过不少人在这里翻车。
还有一个边界：如果整棵树只有一个节点（前面说的单字符情况），那么getCodes(root, "", sb)会直接进入 else 分支，把这个字符的编码设为空字符串。空字符串在后续拼接时会出问题，所以需要特殊处理，比如强制设为 "0"。这个细节后面压缩环节会再提。
4. 数据压缩与编码表：从字节数组到 0/1 串再到字节
4.1 压缩的整体流程
压缩分两步走：先把原始字节数组按编码表转成 0/1 字符串，再把这个字符串按 8 位一组转回字节数组。听起来简单，但中间有几个坑。
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) { // 1. 把原始字节按编码表拼成 0/1 串 StringBuilder sb = new StringBuilder(); for (byte b : bytes) { sb.append(huffmanCodes.get(b)); } // 2. 计算需要多少个字节：长度除以 8 向上取整 int len = (sb.length() + 7) / 8; byte[] huffmanBytes = new byte[len]; // 3. 每 8 位转成一个字节 int index = 0; for (int i = 0; i < sb.length(); i += 8) { String strByte; if (i + 8 > sb.length()) { // 最后不足 8 位，直接取剩下的 strByte = sb.substring(i); } else { strByte = sb.substring(i, i + 8); } huffmanBytes[index++] = (byte) Integer.parseInt(strByte, 2); } return huffmanBytes; }(sb.length() + 7) / 8这个写法是向上取整的经典技巧。比如长度是 10，(10+7)/8 = 2，需要 2 个字节；长度是 16，(16+7)/8 = 2，正好 2 个字节。如果用sb.length() / 8就会少算一个字节。
Integer.parseInt(strByte, 2)把二进制字符串转成整数，再强转成 byte。这里要注意：如果 strByte 是 "11111111"，parseInt 得到 255，强转 byte 会变成 -1，这是正常的，因为 byte 是有符号的。解码时用| 0x100或者Integer.toBinaryString配合补零就能还原。
4.2 最后一位的补零问题
这是整个压缩环节最容易出错的地方。假设最后一段 0/1 串只有 3 位，比如 "101"，我们把它当成一个字节存进去，parseInt("101", 2) = 5，存成字节 5。但解码时，Integer.toBinaryString(5)得到的是 "101"，只有 3 位，我们怎么知道它原本就是 3 位，还是原本 8 位但前面是 0？
答案是：必须额外记录最后一个字节的有效位数。否则解码时无法区分补零和真实数据。
常见的做法是在压缩结果里额外存一个 int 表示最后一段的有效位数。比如：
// 记录最后一个字节的有效位数 int lastBitCount = sb.length() % 8; if (lastBitCount == 0) { lastBitCount = 8; }然后在解压时，对最后一个字节特殊处理，只取前 lastBitCount 位。这个信息必须和压缩数据一起保存，否则解压必然出错。我在第一次实现时忽略了这一点，压缩一个文本文件再解压，末尾总是多出几个乱码字符，排查了半天才发现是补零没处理。
4.3 编码表本身也要存
还有一个更隐蔽的问题：解压时需要编码表，但编码表怎么来？你不能假设解压方知道原始数据的频率分布。所以压缩文件里必须包含足够的信息让解压方重建赫夫曼树。
有两种主流方案：
- 方案一：把编码表直接序列化存进压缩文件。简单直接，但编码表本身占空间，对于小文件可能得不偿失。
- 方案二：把每个字节的频率表存进去。解压方根据频率表重建赫夫曼树，再生成编码表。频率表通常比完整编码表小。
我选的是方案二，因为频率表结构更紧凑，而且重建树的逻辑复用压缩时的代码，不容易出错。频率表可以用一个Map<Byte, Integer>序列化，或者更紧凑地用一个定长数组（256 个 int，因为字节范围是 -128 到 127，共 256 种可能）。
// 把频率表转成字节数组存起来 // 每个字节对应一个 int（4 字节），共 256 * 4 = 1024 字节 public static byte[] freqMapToBytes(Map<Byte, Integer> freqMap) { byte[] result = new byte[256 * 4]; int index = 0; for (int i = 0; i < 256; i++) { byte key = (byte) (i - 128); // 映射回 byte 范围 int freq = freqMap.getOrDefault(key, 0); // 把 int 拆成 4 个字节 result[index++] = (byte) (freq >>> 24); result[index++] = (byte) (freq >>> 16); result[index++] = (byte) (freq >>> 8); result[index++] = (byte) freq; } return result; }1024 字节的头部开销对于大文件可以忽略，对于小文件确实有点浪费。如果追求极致压缩率，可以用变长编码存频率表，但那是另一个话题了。实际工程里，GZIP 这类格式用的是更复杂的方案，我们这里以理解原理为主。
5. 解码与文件解压：把 0/1 串还原成原始数据
5.1 字节转回 0/1 串
解码的第一步是把压缩后的字节数组还原成 0/1 字符串。这里的关键是最后一个字节要按有效位数截取。
public static String bytesToBitString(byte[] huffmanBytes, int lastBitCount) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < huffmanBytes.length; i++) { byte b = huffmanBytes[i]; boolean isLast = (i == huffmanBytes.length - 1); // 最后一个字节特殊处理 if (isLast) { sb.append(byteToBitString(b, lastBitCount)); } else { sb.append(byteToBitString(b, 8)); } } return sb.toString(); } private static String byteToBitString(byte b, int bitCount) { // 把 byte 转成 int，保留低 8 位 int value = b; if (value < 0) { value += 256; // 处理负数，比如 -1 变成 255 } String binary = Integer.toBinaryString(value); // 补零到 8 位 while (binary.length() < 8) { binary = "0" + binary; } // 按有效位数截取 return binary.substring(8 - bitCount); }value += 256这一步是处理负数的关键。Java 的 byte 是有符号的，-1 的二进制补码是 11111111，但Integer.toBinaryString(-1)会返回 "11111111111111111111111111111111"（32 个 1），不是我们想要的。加上 256 变成 255，toBinaryString(255)就是 "11111111"，正确。
5.2 用树遍历解码
有了 0/1 串，解码就是沿着赫夫曼树走：遇到 0 往左，遇到 1 往右，走到叶子节点就输出对应字节，然后回到根节点继续。
public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes, int lastBitCount) { // 1. 先还原 0/1 串 String bitString = bytesToBitString(huffmanBytes, lastBitCount); // 2. 把编码表反转：编码 -> 字节，方便查表 Map<String, Byte> reverseMap = new HashMap<>(); for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { reverseMap.put(entry.getValue(), entry.getKey()); } // 3. 逐个匹配 List<Byte> list = new ArrayList<>(); for (int i = 0; i < bitString.length(); ) { int count = 1; boolean flag = true; Byte b = null; while (flag) { // 从 i 开始取 count 位 String key = bitString.substring(i, i + count); b = reverseMap.get(key); if (b == null) { count++; } else { flag = false; } // 防止越界 if (i + count > bitString.length()) { break; } } list.add(b); i += count; } // 4. 转成 byte 数组 byte[] result = new byte[list.size()]; for (int i = 0; i < list.size(); i++) { result[i] = list.get(i); } return result; }这段代码用的是查表法，把编码表反转成"编码字符串 -> 字节"的映射，然后从当前位置尝试 1 位、2 位、3 位……直到匹配上。因为赫夫曼编码满足前缀约束，所以第一次匹配成功的一定是正确的字符，不会出现歧义。
另一种更优雅的做法是直接遍历树：从根节点开始，读一位走一步，走到叶子就输出并回到根。这种方法不需要反转编码表，但需要把树也传进来。两种方法各有优劣，查表法代码简单，遍历树法更省内存（不用存反转表）。我两种都写过，实测下来对于大文件，遍历树法稍微快一点，因为省去了字符串 substring 的开销。
5.3 文件压缩解压的完整封装
把前面的环节串起来，就是一个完整的文件压缩解压工具。核心流程：
压缩：
- 读取文件所有字节
- 统计频率，建赫夫曼树
- 生成编码表
- 压缩数据
- 把频率表 + 最后有效位数 + 压缩数据写入输出文件
解压：
- 读取压缩文件
- 解析出频率表、最后有效位数、压缩数据
- 用频率表重建赫夫曼树，生成编码表
- 解码得到原始字节
- 写入输出文件
这里有个工程上的细节：文件头的设计。我用的格式是：
| 部分 | 长度 | 说明 |
|---|---|---|
| 频率表 | 1024 字节 | 256 个 int，每个 4 字节 |
| 最后有效位数 | 4 字节 | int 类型 |
| 压缩数据 | 剩余 | 实际的压缩字节 |
读取时先读 1024 字节解析频率表，再读 4 字节得到有效位数，剩下的就是压缩数据。这个格式简单可靠，不需要额外的解析库。
实测一个 1MB 左右的文本文件，压缩后大约 600KB 左右，压缩率 60% 上下。压缩率取决于数据的频率分布，如果文本里字符分布均匀，压缩效果就一般；如果某几个字符占绝大多数，压缩率会很高。这是赫夫曼编码的固有特性——它吃的是频率不均匀的红利。
6. 实测踩坑记录：那些文档里不会写的细节
6.1 单字符文件的死循环
前面提过，如果文件里只有一个字符，赫夫曼树只有一个节点。这时候生成编码表会得到空字符串，压缩时sb.append("")什么都不加，压缩结果长度为 0，解压时直接崩溃。
解决方案是在生成编码表时判断：如果树只有一个节点，强制给这个字符分配编码 "0"。这样压缩后每个字符占 1 位，虽然没压缩效果，但至少不会出错。
if (huffmanCodes.size() == 1) { // 单字符特殊情况 for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { entry.setValue("0"); } }6.2 空文件的处理
如果输入文件是空的（0 字节），统计频率得到空 map，建树时优先队列为空，queue.poll()返回 null，后面全部空指针。所以必须在入口处判断：空文件直接返回空结果，或者原样复制。
6.3 中文和二进制文件的编码问题
用char处理中文时，一个中文字符可能占多个字节，频率统计会乱。用Byte就没这个问题，因为不管什么字符，最终都是字节流。这也是我推荐用Byte的原因。
但要注意：读取文件时必须用字节流，不能用字符流。用FileReader会把字节按平台默认编码转成字符，再转回字节时可能不一致。必须用FileInputStream直接读字节。
6.4 大文件的内存问题
我的实现是把整个文件读进内存处理的，对于几百 MB 的文件没问题，但上 GB 的文件会 OOM。如果要处理超大文件，需要分块处理，但分块会破坏赫夫曼编码的全局最优性（每块的频率分布不同）。工程上的做法是分块压缩，每块独立建树，牺牲一点压缩率换内存安全。这是另一个话题，这里不展开。
6.5 编码表反转时的 key 冲突
理论上赫夫曼编码满足前缀约束，不会有两个字符编码相同。但如果实现有 bug（比如单字符情况没处理好），可能出现重复编码，反转 map 时会覆盖。建议在反转时加个检查，发现重复就抛异常，方便定位问题。
7. 赫夫曼编码的边界与延伸思考
赫夫曼编码不是万能的，它有明确的适用边界。它假设字符之间相互独立，不考虑上下文关系。比如英文里 "th" 出现频率很高，但赫夫曼编码会把 t 和 h 分开编码，浪费了这部分信息。更高级的压缩算法（如算术编码、LZ 系列）会利用上下文，压缩率更高。
另外，赫夫曼编码需要两遍扫描：第一遍统计频率，第二遍编码。对于流式数据（比如网络流），这个特性不太友好。实际工程里常用自适应赫夫曼编码，边读边更新树，但实现复杂度高不少。
如果你想继续深入，可以研究这几个方向：范式赫夫曼编码（Canonical Huffman Code），它让编码表可以用更紧凑的方式存储；长度受限赫夫曼编码，限制最大编码长度，适合硬件实现；算术编码，突破整数位编码的限制，逼近信息熵。
我自己写完这套代码最大的收获，不是学会了赫夫曼树本身，而是理解了"用统计规律换空间"这个通用思路。这个思路在缓存淘汰、索引优化、数据分片里都能看到影子。数据结构课上的东西，只有真正动手实现一遍，才能变成自己的东西。
最后分享一个调试技巧：写压缩解压程序时，先用很小的数据测试，比如 "aaaaabbbcc" 这种，手动算出编码和压缩结果，再和程序输出对比。小数据能跑通，再上大文件。我一开始直接拿几 MB 的文件测，出了问题根本不知道是哪一步错的，后来改成小数据逐步验证，效率高多了。
