哈夫曼编码的核心是构建带权路径最短的二叉树，通过统计字符频次、用最小堆贪心合并建树，再递归生成前缀码映射表；需注意只处理出现字符、正确实现优先队列比较、高效路径记录、预分配编码空间、位流打包与解码匹配，以及单字节统计局限性和编码表序列化。
哈夫曼编码的核心是构建带权路径最短的二叉树
在 C++ 中实现字符串的哈夫曼编码，本质不是直接“压缩字符串”，而是为字符串中每个出现的字符构造最优前缀码。关键在于：先统计字符频次，再用优先队列（最小堆）反复合并两个权值最小的节点，直到只剩一棵树。整个过程不依赖任何第三方库，std::priority_queue 和 std::map 就够用了。
常见错误是把字符当作 ASCII 值硬编码进树节点，而忽略频次为 0 的字符不该参与建树；还有人误用 std::greater<int></int> 却没自定义比较逻辑，导致堆里节点顺序错乱——这会让生成的编码长度变长，甚至无法解码。
- 只对实际出现的字符建树，
std::map<char int></char>统计后遍历即可，别遍历 256 个 ASCII 值 - 优先队列必须按节点权重（频次）升序排列：
std::priority_queue<node std::vector>, Compare></node>，其中Compare是自定义仿函数或 lambda（C++11+） - 合并时新建父节点，左右子指针分别指向被弹出的两个节点，新节点权值 = 左权 + 右权
如何从哈夫曼树生成字符到编码的映射表
建完树后，得递归/迭代地从根走到每个叶子，记录路径上向左为 '0'、向右为 '1'，拼成该字符的编码字符串。最容易出问题的是路径记录方式：用 std::string 拷贝传递易引发大量临时对象；用引用 + 回溯（push_back / pop_back）更高效。
注意：同一个字符只对应一个编码，但不同字符可能有相同编码长度——这正常；如果某字符编码为空（即树退化为单节点），说明输入字符串只含一种字符，此时应特殊处理（如统一编码为 "0"）。
立即学习“C++免费学习笔记（深入）”；
void generateCodes(Node* root, std::string code, std::map<char, std::string>& codes) {
if (!root) return;
if (!root->left && !root->right) {
codes[root->ch] = code;
return;
}
generateCodes(root->left, code + "0", codes);
generateCodes(root->right, code + "1", codes);
}编码和解码时的边界与性能陷阱
编码阶段把原字符串逐字符查表拼接，看似简单，但若原串很长（比如几 MB），频繁字符串拼接（+=）会触发多次内存重分配。建议先估算总编码长度（每个字符编码长度 × 频次之和），用 std::string::reserve() 预分配空间。
解码必须用原始哈夫曼树，不能靠反向查表——因为编码无分隔符，必须从根出发逐位匹配：读入一个 bit，走左或右子树，直到抵达叶子。常见崩溃点是 bit 流末尾补零后多读、或未处理 EOF 导致无限循环。
- 编码输出通常是字节流，需把 bit 序列打包成
unsigned char；每 8 位合为 1 字节，末尾不足补 0，并单独记录补零个数（否则解码时无法截断） - 解码时用
std::bitset或位运算提取单个 bit，别用std::string存整个 bit 序列再索引——内存和速度都吃不消 -
std::priority_queue默认容器是std::vector，插入/弹出复杂度 log n，对万级字符频次完全够用；别自己手写堆
完整流程中真正影响压缩率的其实是频次统计粒度
基础实现只统计单字节（char）频次，这对英文文本有效，但对中文或 UTF-8 编码的文本会彻底失效——一个汉字占 3 字节，被拆成三个独立“字符”统计。这时候压缩率反而比原始还大。
想支持多字节字符，要么改用 std::u8string + UTF-8 解码（C++20），要么预处理把 UTF-8 序列转为 Unicode 码点再统计。但绝大多数教学级实现就停在单字节，因为重点是理解贪心构造和前缀码性质，不是工程压缩。
真正容易被忽略的是：哈夫曼编码本身不加密、不混淆，编码表必须随压缩数据一起保存（或约定重建规则），否则解码端根本不知道 'a' 对应的是 "101" 还是 "00"。这个元信息的序列化方式，才是落地时第一个要设计的接口。
