需自定义node结构体并重载operator
怎么用C++构建哈夫曼树并生成编码表
核心是先统计字符频次，再用优先队列（最小堆）合并节点。C++标准库没有现成的哈夫曼树类，得自己定义Node结构体，并重载operator让<code>priority_queue按频次升序排列。
常见错误是把priority_queue默认当成小顶堆——其实它是大顶堆，必须显式传入greater<node></node>或自定义比较器；另一个坑是合并时没把新节点的频次设为左右子节点频次之和，导致树结构错乱。
关键步骤：
- 用
unordered_map<char int></char>遍历字符串统计频次 - 每个字符建一个叶子
Node，频次为计数值，左右子指针为nullptr - 所有
Node*入堆，每次取两个频次最小的节点，新建父节点，左/右子分别指向它们 - 重复直到堆中只剩一个节点——即根节点
- 从根DFS递归生成编码：左走记
'0'，右走记'1'，到达叶子时存入map<char string></char>
如何避免编码表生成时的递归栈溢出和重复路径
当输入字符串含大量唯一字符（比如随机二进制数据转成字符串），哈夫曼树可能退化成链状，深度接近字符种类数。此时DFS递归容易爆栈，尤其在Windows默认栈大小下。
更稳妥的做法是改用迭代DFS或BFS：用stack<pair string>></pair>保存当前节点和已生成的编码前缀，避免函数调用开销。同时注意string在循环中频繁拼接会触发多次内存分配，应改用string_view临时拼接，或在进入子节点前用prefix += '0'再回溯pop_back()。
另一个易错点：多个字符频次相同时，合并顺序不唯一，会导致不同但等长的编码表。这不影响压缩率，但会使相同输入产生不同输出，不利于校验。若需确定性，可在比较器中加入字符值或地址作为第二排序键。
压缩后怎么存编码结果而不丢失边界信息
哈夫曼编码是变长的，直接拼接string得到的"0101100"无法知道第一个字符占几位。所以不能只存编码比特流，还得存元数据。
实际做法分两部分：
- 头部写入字符频次表（如先写字符个数
n，再写n组char + int，注意int要转为固定长度如uint32_t并考虑字节序） - 主体写编码比特流：把
string形式的"0101"转为vector<uint8_t></uint8_t>，每8位塞进一个字节，末尾不足8位时补0并在头部记录有效位数（如最后字节用了5位，就存5） - 解压时先读频次表重建树，再按位读取比特流，逐位在树上查找叶子——找不到就继续读下一位，直到命中
别忘了处理空字符串或单字符等边界情况：if (freq_map.size() == 1)时树退化为单节点，编码全为空，必须特殊处理，否则解压会卡死。
为什么不用std::map而用unordered_map统计频次
因为频次统计只需要O(1)平均插入和查找，unordered_map比map快得多，尤其当字符串很长、字符集较小时（比如纯ASCII文本）。实测在1MB文本上，前者耗时约0.8ms，后者约2.3ms。
但要注意：如果字符是宽字符（wchar_t）或需要支持UTF-8多字节序列，unordered_map的哈希函数需自定义，否则char数组会被当作指针哈希。此时更简单的方式是先用std::string切分UTF-8字符，再对每个std::string（代表一个Unicode码点）做映射。
另外，若输入含控制字符（如\0），用std::string构造时别用C风格字符串构造函数，防止截断；应显式传入长度：string(s.c_str(), s.length())。
真正麻烦的是压缩率本身——哈夫曼只是无损压缩的第一步，它不消除冗余模式，对已经加密或随机数据几乎无效。别指望它把一段base64密文压掉一半。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
