前言哈夫曼树Huffman tree是一棵带权二叉树目标只有一个让带权路径长度weighted path length, WPL最小。WPL 是每个叶子的权重乘上它到根的路径长度之和。把权重大的叶子放得浅、权重小的放得深WPL 就小。这个性质直接对应压缩高频字符用短码低频字符用长码。常见的误解有三个。第一以为哈夫曼树唯一——当有权值相同的结点时不同的合并顺序会得到不同的树但 WPL 相同。第二以为它是平衡树其实它刻意不平衡越常用的字符越靠近根。第三把编码过程与建树过程混在一起建树只依赖频率编码只是对树做一次遍历。本文按概念 → 构造 → 编码解码 → 完整实现讲重点说清为什么每次合并最小的两个权重能得到最优解以及实现时堆的比较器方向、单字符树、比特流校验这些边界。代码以 C17 为基准。一、带权路径长度给定n个叶子每个带权重w_i深度为d_i根为 0或按边数计为 1只要全树统一即可则WPL Σ w_i × d_i在所有以这些叶子为叶子的二叉树中WPL 最小的那棵就是哈夫曼树也叫最优二叉树。举例权重为 1、2、3、4 的四个叶子。若做成一条链深度分别是 0、1、2、3假设WPL 会很大若尽量让大权重靠近根WPL 会明显下降。哈夫曼算法给出的结构是先合并 1 与 2 得到 3再合并 3 与 3 得到 6最后合并 6 与 4 得到 10。四个叶子的深度分别是 3、3、2、1WPL 1×3 2×3 3×2 4×1 19。二、构造贪心合并最小的两个算法非常短把每个叶子作为一个单结点树放入一个按权重排序的集合取出权重最小的两棵合并成一棵新树新树的权重是两者之和把新树放回集合重复直到只剩一棵树。n 个叶子 → 需要 n-1 次合并 → 总共 2n-1 个结点为什么这样能得到最优解核心是一个交换论证在任意一棵最优树中权重最小的两个叶子一定可以放在最深的一层并且互为兄弟。如果它们不在最深处把最深处的叶子与它们交换WPL 不会增大因为小权重下沉、大权重上浮只会让总和更小如果它们不是兄弟把它们调整为兄弟也不会增大 WPL。于是合并最小的两个这一步是安全的剩下的问题规模减一归纳即得最优。这个论证也解释了贪心成立的条件每一步都必须合并当前最小的两个而不是原始权重最小的两个。合并产生的新权重会参与后续比较。三、编码与解码前缀码把树的左分支记为 0、右分支记为 1从根到叶子的路径就是一个二进制串。由于每个字符都在叶子上任何一个编码都不是另一个编码的前缀——这就是前缀码prefix code解码时不需要分隔符从左到右走树即可。字符频率编码深度a4501b131103c121013d161113e91003构造过程是合并 9 与 12 得 21合并 13 与 16 得 29合并 21 与 29 得 50最后合并 45 与 50 得 95。左右分支可以互换所以具体编码不是唯一的但每个编码都满足前缀性质没有任何一个编码是另一个编码的前缀解码时不需要分隔符。四、完整实现用std::priority_queue维护最小堆。默认的priority_queue是最大堆所以要自定义比较器让权重小的排在堆顶。// 适用于 C17#include map#include memory#include queue#include string#include utility#include vectorstruct Node {int weight 0;char ch \0; // 内部结点没有字符Node* left nullptr;Node* right nullptr;Node(int w, char c) : weight(w), ch(c) {}};struct MinCompare {bool operator()(const Node* a, const Node* b) const {return a-weight b-weight; // 注意方向大于号构成最小堆}};class Huffman {public:explicit Huffman(const std::vectorstd::pairchar, int freqs) {std::priority_queueNode*, std::vectorNode*, MinCompare pq;for (const auto item : freqs) {if (item.second 0) continue; // 忽略非正频率nodes_.push_back(std::make_uniqueNode(item.second, item.first));pq.push(nodes_.back().get());}if (pq.empty()) return;while (pq.size() 1) {Node* a pq.top(); pq.pop();Node* b pq.top(); pq.pop();nodes_.push_back(std::make_uniqueNode(a-weight b-weight, \0));Node* parent nodes_.back().get();parent-left a;parent-right b;pq.push(parent);}root_ pq.top();}void build_codes() {codes_.clear();build_codes(root_, std::string());if (root_ ! nullptr root_-left nullptr root_-right nullptr) {codes_[root_-ch] 0; // 单字符树给一个占位编码}}const std::mapchar, std::string codes() const { return codes_; }std::string encode(const std::string text) const {std::string bits;for (char c : text) {auto it codes_.find(c);if (it codes_.end()) return std::string(); // 未知字符bits it-second;}return bits;}std::string decode(const std::string bits) const {if (root_ nullptr) return std::string();if (root_-left nullptr root_-right nullptr) {return std::string(bits.size(), root_-ch); // 单字符树}std::string text;const Node* cur root_;for (char b : bits) {if (b 0) cur cur-left;else if (b 1) cur cur-right;else return std::string();if (cur nullptr) return std::string();if (cur-left nullptr cur-right nullptr) {text.push_back(cur-ch);cur root_; // 回到根解下一个字符}}if (cur ! root_) return std::string(); // 比特流不完整return text;}int wpl() const { return wpl(root_, 0); }private:static void build_codes(const Node* n, const std::string prefix,std::mapchar, std::string out);static int wpl(const Node* n, int depth);std::vectorstd::unique_ptrNode nodes_; // 统一持有所有结点Node* root_ nullptr;std::mapchar, std::string codes_;};两个静态辅助函数的实现// 适用于 C17void Huffman::build_codes(const Node* n, const std::string prefix,std::mapchar, std::string out) {if (n nullptr) return;if (n-left nullptr n-right nullptr) {out[n-ch] prefix;return;}build_codes(n-left, prefix 0, out);build_codes(n-right, prefix 1, out);}int Huffman::wpl(const Node* n, int depth) {if (n nullptr) return 0;if (n-left nullptr n-right nullptr) {return n-weight * depth;}return wpl(n-left, depth 1) wpl(n-right, depth 1);}用std::vectorstd::unique_ptrNode统一持有所有结点结点之间的left/right用裸指针表示非拥有关系。这样既不会泄漏也不需要在树结构里处理所有权转移。五、复杂度与边界建树时每个叶子入堆一次、每次合并产生一个新结点入堆共2n-1个结点每次堆操作 O(log n)总时间 O(n log n)。编码遍历 O(n)解码 O(比特数)。边界情况只有一个不同字符树只有一个结点没有左/右分支常规遍历会给它一个空编码。上面用0占位解码时按位数还原。这是压缩实现里必须特判的情况。频率为 0 或负数没有意义应当过滤或拒绝。全部被过滤时root_为空编码解码返回空串。比特流不完整最后一个字符的编码被截断cur不会回到根解码应当报错而不是返回半截结果。树的形状不唯一权重相同的结点谁左谁右都可以只要双方约定一致即可编码表必须与树一起传递不能只传比特流。常见坑点1. 比较器方向写反得到最大堆// ❌ 每次取出最大的两个WPL 不是最优return a-weight b-weight;// ✅ 最小堆堆顶是最小值return a-weight b-weight;2. 合并后忘记把新结点入堆// ❌ 集合元素越来越少结果错误Node* parent make(a, b);// ✅ 新结点也要参与后续比较pq.push(parent);3. 单字符树没有编码// ❌ 编码为空串无法还原if (leaf) out[ch] prefix; // prefix 为空// ✅ 特判并给一个占位码codes_[root_-ch] 0;4. 解码不校验比特流完整性// ❌ 截断的输入被当成合法数据for (char b : bits) { ... }return text;// ✅ 结束后确认已回到根if (cur ! root_) return std::string();5. 用裸new建结点却没有统一释放// ❌ 异常路径上泄漏Node* n new Node(w, c);// ✅ 用 unique_ptr 容器统一持有nodes_.push_back(std::make_uniqueNode(w, c));6. 把原始频率当成合并后的权重// ❌ 新结点权重算错贪心失效parent-weight a-weight; // 漏了 b// ✅ 权重是两者之和parent-weight a-weight b-weight;7. 假设哈夫曼树唯一// ❌ 用树的形状做校验// ✅ 只校验 WPL 与编解码的可逆性8. 编码表与比特流分开传输却未同步// ❌ 解码方用旧表解新流// ✅ 编码表随数据一起传输或固定版本总结步骤操作复杂度统计频率遍历输入O(n)建树最小堆反复合并O(n log n)生成编码一次 DFSO(n)编码查表拼接O(输出长度)解码沿树走比特O(输入长度)概念含义WPL叶子权重 × 深度之和贪心选择每次合并当前最小的两个前缀码任一编码都不是另一编码的前缀树的唯一性不唯一WPL 唯一最小哈夫曼树的核心只有一句让权重大的叶子离根近。构造算法用最小堆把这个直觉变成可执行步骤编码只是对结果做一次遍历。实现时真正要小心的是堆的比较方向、单字符树、比特流完整性这三处边界把这三个处理掉剩下的就是标准的二叉树遍历。