哈夫曼树Huffman Tree是数据结构和算法里非常经典的一个模型也是一道出现率极高的编程题。很多人在考试和面试时能背出“每次选两个最小节点合并”这句话但真正要自己用 C 写一遍从频率统计、优先队列、编码表生成到解码才知道里面有大量细节。这篇教程就按完整流程走一遍覆盖哈夫曼树构建、哈夫曼编码生成以及最终解码适合把数据结构学完但没做过完整大作业的同学也适合想自己动手写个迷你压缩工具的人。我会尽量把代码写成“能直接编译”的版本同时把每一步设计背后的原因讲清楚。写成这样不是为了让代码最短而是让你在改 bug、加功能时不至于一头雾水。如果你完全没接触过哈夫曼树也不用慌后面第 1 节先把原理捋一遍接着就是可以直接抄的 C 实现。1. 哈夫曼树的核心原理为什么它能做到无损压缩1.1 定长编码与变长编码的差异计算机里文本最终都要变成二进制串。最朴素的做法是定长编码比如 ASCII 每个字符固定用 8 位二进制文件按字节读出来天然就是 8 位一组。定长编码的好处是解码非常简单读满固定长度就还原一个字符坏处是浪费——不管这个字符出现 100 次还是出现 1 次它占的位数完全一样。哈夫曼编码的思路改成变长编码出现频率高的字符用短码出现频率低的字符用长码。这样整段数据的总长度会明显下降。但变长编码有一个前提问题接收方怎么区分边界举个反例如果 A 的编码是 0B 的编码是 01收到 01 时到底应该解成 AB 还是 B这就是歧义。哈夫曼编码通过构造一颗二叉树来规避这个问题任何字符的编码都不是另一个字符编码的前缀解码时从头扫描永远不会卡在边界判断上。1.2 贪心策略与最小带权路径长度哈夫曼树的构建算法属于贪心算法把所有字符看成一片森林每棵树带一个权值也就是频率每一轮都取权值最小的两棵树合并成新树新树的权值是两个子树权值之和然后放回森林重复这个过程直到只剩一棵树。合并时频率低的节点处在树的深层频率高的节点处在树的浅层。这也对应了“最小带权路径长度”的概念。树里每个叶子的路径长度乘它的权值加起来就是整棵树的带权路径长度可以理解为“平均每个字符需要多少位”。贪心策略能保证这个值最小。证明通常用交换论证假设最优树里有两个最深的叶子如果它们不是当前频率最小的两个把更小的节点交换到更深的位置后总成本一定不会变大。这个证明你可以在任何《算法导论》版本里翻到我不多展开但记住“选最小合并”这个动作不是拍脑袋定的它有严格的数学基础。1.3 一个手算例子先看一个直观例子。假设文本里只有 A、B、C、D、E 五个字符统计频率如下字符频次定长编码(3位)哈夫曼编码A50000B400110C3010110D20111110E11001111定长编码总长度是 5*3 4*3 3*3 2*3 1*3 45 位。按哈夫曼编码总长度是 5*1 4*2 3*3 2*4 1*4 34 位节省了约 24%。如果频率分布更极端比如某些字符出现几十万次另一些只出现一次节省会更明显。你看编码表里没有一个编码是另一个的前缀比如 A 是 0没有任何其他编码以 0 开头B 是 10C 是 110也不会撞车。这是哈夫曼树能无损还原的根本原因。2. 动手前的准备节点设计与优先队列2.1 节点结构怎么设计才顺手我要处理的对象是字节流所以我直接把符号类型定义成 unsigned char。为什么不用 char因为 char 在有符号平台上取值可能是负数当你把 unsigned char 转成 int 做数组下标时负数会越界很隐蔽。用 unsigned char 就没这个问题。struct HuffNode { unsigned char ch; unsigned long long freq; HuffNode* left; HuffNode* right; HuffNode(unsigned char c, unsigned long long f) : ch(c), freq(f), left(nullptr), right(nullptr) {} };freq 用 unsigned long long 而不是 int是因为处理大文件时频率很容易超过 21 亿。很多新手在这里写 int然后压缩一个稍微大点的文件就溢出定位起来特别痛苦。在这里直接上 64 位无符号整数省心。left 和 right 指向两个子节点。当这个节点是内部节点时ch 字段其实用不到因为内部节点不代表具体字符所以可以随便填个 0。这正是后面代码里new HuffNode(0, ...)的原因。2.2 优先队列的坑自定义比较器要点构建哈夫曼树的时候每一轮都需要从节点集合里找“频率最小的两个”。C 里的 priority_queue 默认是大根堆也就是优先取出最大的元素所以必须自定义比较器让它变成小根堆。struct NodeCmp { bool operator()(HuffNode* a, HuffNode* b) const { if (a-freq ! b-freq) return a-freq b-freq; return a-ch b-ch; } }; std::priority_queueHuffNode*, std::vectorHuffNode*, NodeCmp pq;这里的逻辑要绕一下priority_queue 认为operator()返回 true 时a 的优先级低于 b所以会被放在堆的更下面。要让小 freq 的节点先被取出来比较器得返回a-freq b-freq。换句话说我们写的是一个“反着比较”的规则。很多第一次写的人会顺手写成a-freq b-freq结果构建出来的不是哈夫曼树而是按大根堆合并的树压缩率变的很差甚至完全不可用。这个问题你大概率会遇到后面第 6 节我再详细说。另外我还加了a-ch b-ch作为平局时的二次比较条件目的是让构建过程稳定同样频率时按字符顺序排避免堆内部顺序不确定导致调试时结果随机。2.3 为什么用优先队列而不是数组排序字符集固定为 256 个字节时你也可以用数组每轮 sort 一次或者用线性扫描找最小两个复杂度是 O(256*n)。因为 n 最多 256看着也能忍但思路到更大规模的符号集就不好使了。优先队列把每次取最小节点的成本压到 O(log n)整个构建复杂度是 O(n log n)n 是不同符号数量。这个复杂度在数据结构和算法题里属于标准答案。如果你以后想继续优化可以走双队列法把初始节点按频率排好放进一个队列每合并出的新节点放进另一个队列两个队列头部都是对应队列最小的每次比较两个队头就能取到全局最小构建能做到 O(n)。不过这不是 C 课程大作业的必需内容我顺带提一下你有个印象就行。3. 构建哈夫曼树的完整实现3.1 第一步统计每个字节的出现频率构建树之前必须知道每个符号的频率。这一步通常从文件读取也可以用一段内存字符串。我习惯先把整个文件读进一个 std::string因为后面编码也要用到原始数据。std::string readFile(const std::string path) { std::ifstream in(path, std::ios::binary); if (!in) throw std::runtime_error(cannot open file); std::string data((std::istreambuf_iteratorchar(in)), std::istreambuf_iteratorchar()); return data; }注意一定要用std::ios::binary打开文件。如果不加Windows 平台上会把 0x1A 这种字节当成文本结束符读出来的内容就不完整。Linux 上影响不大但写成二进制模式是跨平台的好习惯。频率统计直接用一个长度为 256 的数组std::vectorunsigned long long freq(256, 0); for (unsigned char c : data) { freq[c]; }这里for (unsigned char c : data)是我故意写的。如果写成for (char c : data)后面freq[c]会出现负数下标轻则崩溃重则悄悄把数据写坏。用 unsigned char 做遍历变量可以把这个隐患从源头掐掉。3.2 第二步初始化森林并循环合并有了频率数组之后构建函数长这样HuffNode* buildHuffmanTree(const std::vectorunsigned long long freq) { std::priority_queueHuffNode*, std::vectorHuffNode*, NodeCmp pq; for (int i 0; i 256; i) { if (freq[i] 0) { pq.push(new HuffNode(static_castunsigned char(i), freq[i])); } } if (pq.empty()) return nullptr; if (pq.size() 1) { HuffNode* only pq.top(); HuffNode* root new HuffNode(0, only-freq); root-left only; return root; } while (pq.size() 1) { HuffNode* left pq.top(); pq.pop(); HuffNode* right pq.top(); pq.pop(); HuffNode* parent new HuffNode(0, left-freq right-freq); parent-left left; parent-right right; pq.push(parent); } return pq.top(); }有两个边界情况被很多教程一笔带过但实际写代码时必须处理空文件时 pq 是空的直接返回 nullptr只有一个不同字符时 pq.size() 1循环不会执行直接返回那个单节点的话后面生成编码表会出问题。因为单个叶子节点的编码应该是 0 或 1不能是空串。我的处理是造一个虚拟根把唯一字符挂到左子树上这样它的编码自然就是 0。合并过程本身不难就是反复 pop 两个、push 一个。左子树和右子树的顺序其实是任意的只要整棵树保持一致编码和解码就不会出问题。我通常把先取出的节点放在 left后取出的放 right然后把这个新 parent 重新入堆。3.3 构建过程的可视化与复杂度推算如果左边例子中的五个字符走一遍构建过程是E(1) 和 D(2) 合并出 3C(3) 和这个 3 合并出 6B(4) 和 6 合并出 10A(5) 和 10 合并出 15。这里每次合并产生一个内部节点所以 5 个叶子会得到 4 个内部节点总节点数 9。一般规律叶子数 n内部节点数 n-1总节点数 2n-1。这个规律很有用可以提前开数组存节点而不是全部 new也能在调试时判断树的形状是否符合预期。构建复杂度上每个节点入堆出堆各一次每次 O(log n)所以整体 O(n log n)。由于字符集最大 256这个 n 很小构建时间几乎可以忽略真正的耗时点在编码时逐字节查表、写位流。4. 生成哈夫曼编码表把树变成“字典”4.1 从根出发的 DFS 遍历与编码生成树构建好之后下一步是给每个叶子生成二进制编码。约定向左走记 0向右走记 1走到叶子时把累计的路径串作为该字符的编码。void generateCodes(HuffNode* root, const std::string prefix, std::vectorstd::string codes) { if (!root) return; if (!root-left !root-right) { codes[static_castunsigned char(root-ch)] prefix; return; } generateCodes(root-left, prefix 0, codes); generateCodes(root-right, prefix 1, codes); }这个递归函数非常短但要注意它只在叶子字符非空时赋值。内部节点的 ch 是 0虽然它不会走进叶子判断条件因为有孩子会继续递归。这里不需要额外判断 codes 是否已经有值因为哈夫曼树的叶子节点彼此独立一个字符只会被访问到一次。4.2 编码表的组织方式与内存占用我建议用std::vectorstd::string codes(256)来存所有字符的编码。为什么不用 std::map因为字符集大小已知且固定数组直接按下标访问是 O(1)map 是 O(log n)而且 map 的节点开销大纯属浪费。256 个 string 对内存的影响也可以忽略。std::vectorstd::string codes(256); generateCodes(root, , codes);这里有个小坑统计频率时遍历用的是unsigned char放进 codes 下标时也要转成 unsigned char否则下标会越界。我见过有人统计时用 unsigned char到了查表这里又写codes[data[i]]data 是 std::string 的 char于是负数字符直接访问 codes[-99] 之类的位置程序当场崩溃。4.3 一个具体例子的压缩效果测算回到第 1 节的例子。字符串 AAAAABBBBCCCDDE 共 15 个字符定长用 3 位表示 5 种字符要 45 位哈夫曼编码后只要 34 位。但注意这 34 位“位”如果按字符串形式存每个字符 0 或 1 在内存里占 8 位最终是 272 位反而比原文本还大。所以哈夫曼编码要真正压缩必须把编码串按位压实成字节这也引出后面第 5 节的内容。很多初学者跑完字符串版就以为完成了其实只做到一半。真正的压缩率需要把 8 个 bit 塞进一个字节最后不足 8 位再补零并且要把“最后几位是有效位”记录下来。5. 编码与解码从字符串模拟到位流5.1 字符串版本的编码函数作为可读性最强的中间步骤先把编码输出成由 0 和 1 组成的字符串。它不方便直接写入文件但非常方便调试。std::string huffmanEncode(const std::string data, const std::vectorstd::string codes) { std::string encoded; encoded.reserve(data.size() * 2); for (unsigned char c : data) { encoded codes[c]; } return encoded; }如果某个字符在统计频率时没有出现它的 codes 会是空串这里 不会有任何输出也不会报错。这可能掩盖一些问题建议调试时加一个断言if (codes[c].empty()) { throw std::runtime_error(character not in code table); }5.2 字符串版本的解码函数解码是从根节点出发遇 0 走左、遇 1 走右走到叶子就输出字符然后回到根继续。std::string huffmanDecode(const std::string encoded, HuffNode* root) { if (!root) return ; std::string decoded; HuffNode* cur root; for (char bit : encoded) { if (bit 0) cur cur-left; else cur cur-right; if (!cur) { throw std::runtime_error(invalid encoded bit); } if (!cur-left !cur-right) { decoded.push_back(static_castchar(cur-ch)); cur root; } } return decoded; }注意 cur 走到叶子后必须立即重置为 root否则下一个 bit 会从上一次的叶子继续走出现空指针。这个 bug 很常见表现形式是解到一半崩溃或者输出一堆乱码。输出乱码比崩溃更隐蔽因为程序没报错但结果完全错误。5.3 位级写入压缩率真正生效的地方字符串版本的 encoded 每字符占 8 位。要写进文件就得按位打包。下面这个函数把 0/1 字符串转成一个字节序列并记录最后一个字节有效位数std::string bitsToBytes(const std::string bits, int lastBits) { std::string out; unsigned char byte 0; int count 0; for (char ch : bits) { byte static_castunsigned char((byte 1) | (ch - 0)); if (count 8) { out.push_back(static_castchar(byte)); byte 0; count 0; } } if (count 0) { byte static_castunsigned char(byte (8 - count)); out.push_back(static_castchar(byte)); lastBits count; } else { lastBits 8; } return out; }如果 bits 长度正好是 8 的倍数lastBits 置成 8表示最后一个字节全部有效。如果最后凑不够 8 位把剩余的 bit 移到字节高位低位补 0并记录有效位数。这个步骤不能省。否则解码时你会把补的 0 也当成真实编码解出一堆不存在的字符。与之配套的位流解码函数本质上就是一边读取每一个 bit一边沿树游走。如果你把整段 bitsToBytes 的结果和 lastBits 都保存下来解码时先按 lastBits 截断最后一段再交给 huffmanDecode就完成了完整还原。5.4 位级解码的具体做法给一个简单的位流解码参考std::string decodeBitStream(const std::string bytes, int bitCount, HuffNode* root) { std::string bits; bits.reserve(bitCount); int totalBits bytes.empty() ? 0 : (static_castint(bytes.size()) - 1) * 8 bitCount; // 这里 bitCount 表示最后一个字节的有效位数 for (int i 0; i totalBits; i) { unsigned char byte static_castunsigned char(bytes[i / 8]); int shift 7 - (i % 8); bits.push_back(((byte shift) 1) ? 1 : 0); } return huffmanDecode(bits, root); }这个函数先把位流还原成 0/1 字符串再走一遍树解码效率不是最高的但逻辑清楚适合做第二版。如果你想追求性能可以直接在循环里游走树遇到叶子输出字符后重置 cur根本不生成中间字符串。我在实际项目里就是这么做的代码会复杂一点但省内存、省时间。6. 实操中我踩过的坑问题速查表与排查方法6.1 优先队列比较器写反整棵树顺序全乱现象构建出来的树“看起来”也是从叶到根但频率最高的字符反而编码最长。原因就在于比较器把大根堆写成了小根堆的返回值反过来。排查时你可以在构建循环里打印每次合并的两个节点频率正常情况下第一次合并的应该是最小的两个如果打印出来是最大的两个说明比较器方向错了。修正方法就在第 2.2 节那段代码里。这个坑非常经典因为 priority_queue 的比较器语义和使用直觉相反我第一次写也在这里卡了整整一个下午。我的建议是永远不要裸记“大于号还是小于号”而是在写完比较器后push 三个频率分别为 1、2、3 的节点再连续 pop 出来看顺序。用 10 行测试代码验证方向比嘴上一遍遍背要可靠得多。6.2 指针内存泄漏new 出来的节点记得释放构建哈夫曼树时每个叶子节点 new 一次每次合并 new 一个父节点叶子数 n 的情况下总共有 2n-1 个 new。如果只分配不释放压缩大文件时会持续吃内存。解决办法是递归 deletevoid freeTree(HuffNode* root) { if (!root) return; freeTree(root-left); freeTree(root-right); delete root; }注意释放完 root 之后不要再二次访问 root 的 children否则就是 use-after-free。最好在 freeTree 后把外层指针置为 nullptr避免误用。还有一个容易忽略的点优先队列里的节点指针一旦 pop 后所有权就转移给了树结构不要在 pop 之后又去手动 delete否则后面构建父节点时访问的是悬垂指针。如果你实在不想手管内存可以把 left/right 改成 shared_ptr。但 priority_queue 存 shared_ptr 时要注意比较器需要解引用稍麻烦一点。对小工具来说裸指针加 freeTree 是最直白的。6.3 中文和 UTF-8 文本按字节还是按字符我前面设计的实现版本按字节处理也就是无论是什么文件读进来都是字节流。UTF-8 编码的“哈”字占 3 个字节会当作 3 个不同的符号参与统计。这样能完整无损地还原文件但压缩率一般因为同一个字的三个字节可能被拆开、各自占编码。如果你希望按真正语义上的“字符”来压缩必须先做解码把 UTF-8 转成 Unicode 码点再拿码点做频次统计。比如用 wstring 处理后按 wchar_t 统计。原理完全一样只是符号表从 256 变成几万个内存会大一些。这是我在做中文文本压缩时踩过的一个教训只测英文文件看不出问题一测中文才发现压缩率明显偏低。后来我把统计单位从“字节”改成“Unicode 码点”中文文本的压缩率立刻好看了很多。代价是文件头要记录更多符号复杂度也上来了。课程设计做中文压缩之前建议想清楚自己的目标格式。6.4 空文件和单字符文件最容易翻车的边界空文件频率数组全是 0buildHuffmanTree 返回 nullptr。编码表生成函数里第一步就要判断 root 为空。解码函数里也要判空。空文件可以直接选择不压缩写入一个特殊的文件头标记即可。单字符文件比如整个文件都是字母 a构建出来的树只有一个叶子。如果不特殊处理generateCodes 里这个叶子的 prefix 是空串编码结果是空串压缩完推不出任何 bit解压时也不知道代表什么。我的处理是强制造一个虚拟根节点把唯一叶子挂到左边这样字符 a 的编码就是 0一个 bit 就能表示一个原字节。虽然理论上有优化空间比如压根不需要编码但在代码上统一了流程后续解码不用写两套逻辑。6.5 位写入的补齐问题少记一位解码全错压缩文件时编码总长度大概率不是 8 的倍数。最后不足 8 位的部分要补 0 凑成一个字节否则文件没法按字节写。但补进去的 0 本身不是有效编码解压时必须知道“最后一个字节里后几位是有效数据”。很多时候我会把总 bit 数或有效位数写进文件头。最常见的方案是文件头写原始文件长度、哈夫曼树信息、编码总 bit 数。解压时先读文件头恢复树再根据 bit 数精确读取编码这样最后补的 0 完全不会进入解码过程。如果你用 lastBits 方案也要注意 lastBits 等于 0 还是等于 8 的区分。我习惯直接用 totalBits这样更直观也不会出现“刚好满一字节但忘记记有效位”的边界。6.6 其他零散问题的快速定位清单现象可能原因排查方向解出后半段乱码最后补 0 被当成真实编码检查 lastBits / totalBits 处理程序崩溃在 codes[c]用了有符号 char 做下标所有遍历改成 unsigned char压缩率几乎为 0比较器方向反了打印前两次合并频率验证输出文件比原文件还大直接把 0/1 字符串写文件了需要先按位打包成字节中文文件压缩率诡异低按字节统计 UTF-8 多字节字符考虑按 Unicode 码点统计这张表基本上是我做哈夫曼压缩时真踩过的坑排查时照着看能省不少时间。7. 性能优化与扩展从作业变成真正的压缩工具7.1 优化编码表的内存与序列化如果只是课程作业codes[256] 完全没问题。但如果你想做一个真正的压缩工具还要考虑把哈夫曼树或编码表写进压缩文件头供解压时使用。有两种常见做法一种是把整棵树序列化前序遍历树遇到叶子写 1 加字符遇到内部节点写 0解压时重建另一种是使用规范哈夫曼编码Canonical Huffman Coding不传树结构只传每个符号的编码长度然后由长度统一推导出编码能省大量空间。规范哈夫曼编码的思路就是先按码长分组再把同长度编码按符号顺序递增编号最后生成一张和原始哈夫曼编码等长的标准表。因为解码时只需要每个符号的码长不需要左右子树的完整形状文件头可以做得非常小。ZIP、PNG 等格式里都用了类似技巧有兴趣可以朝这个方向深入。7.2 流式处理不要一次性读入大文件我给的示例为了好懂使用 readFile 一次性把整个文件读进字符串。文件小无所谓几百 MB 的文件就会吃掉大量内存。更专业的做法是分块压缩文件头写总块数每一块独立统计频率、建树、编码解压时逐块处理。每个块通常几 KB 到几百 KB内存占用可以控制住还能对文件不同区域做自适应频率统计压缩率往往更好。代价是文件头更复杂每块都要附一个树或编码表。工业界很多格式就是这么做的分块大小经过精心调优。如果是课程设计你能做到分块读取 按块重建树已经比大多数同学强了。7.3 真实世界里的哈夫曼编码ZIP、JPEG 与 HTTP/2哈夫曼编码并不只是教材里的玩具。ZIP 实现了 DEFLATE 算法里面就大量使用动态哈夫曼编码JPEG 里对亮度、色度系数用的也是哈夫曼编码HTTP/2 的 HPACK 头部压缩也采用了哈夫曼表。你只要把本文这套构建和编码思路吃透再去看这些格式的源码就会顺畅很多。核心都是同一棵树只是工程上加了各种边界处理和压缩技巧。拿 DEFLATE 来说它除了哈夫曼编码还有 LZ77 字典压缩先找重复串再对剩余信息做哈夫曼编码。JPEG 则是量化后对 zig-zag 序列里的 DC 和 AC 系数分别建哈夫曼表。理解了哈夫曼树你再看这些文档不会觉得门槛很高。7.4 进一步优化的方向符号表变量化不固定 256而是根据实际文件动态确定符号范围减少无效节点。用数组代替递归生成编码避免递归深度过高虽然字符最多 256深度不会超过 255性能问题不大。编码位输出时合并多个文件句柄操作用更大的 buffer 一次 write减少系统调用。多线程并行编码大文件分块后每个块独立构建哈夫曼树可以并行但块数很多时每块的编码表开销也会变大。我觉得最值得做的扩展是分块 规范哈夫曼编码。前者解决大文件内存问题后者解决文件头臃肿问题两个组合起来已经接近一个轻量级压缩库的雏形。如果你也想把哈夫曼树彻底搞明白我推荐你按这个顺序写三版代码。第一版直接用字符串存 0/1把构建和编码解码流程跑通重点放在正确性。第二版改成位级写入并支持从文件恢复重点处理边界条件。第三版再加分块和规范哈夫曼编码做成一个真正可用的命令行工具。我最初做第二版时连续调了三天最后发现就是文件头少记录了 1 个字节的有效位。从那以后我再也不小看边界条件了。哈夫曼树看似简单真正写起来你能学到的东西绝对比课件上多得多。