用c++构建哈夫曼树的核心是用priority_queue（配合greater）维护小根堆，每次取出两个最小权值节点合并；常见错误是未指定小根堆导致取最大节点或未重载比较操作符。
怎么用 C++ 构建哈夫曼树（不依赖第三方库）
核心是用 priority_queue 维护带权节点，每次取两个最小频率的节点合并。别手写堆——C++ 标准库的 priority_queue 默认是大根堆，得用 greater 反转成小根堆，否则合并顺序错，编码就全歪了。
常见错误现象：priority_queue<node></node> 直接用，结果总取到最大频率节点；或者没重载 operator，编译报错 <code>invalid operands to binary expression。
- 定义节点结构体时，必须让
operator 按频率升序比较（即 a priority_queue逻辑反了 - 合并新节点的频率 = 左子频率 + 右子频率，这个值必须参与下一轮比较，不能只存父指针
- 字符频次统计建议用
map<char int></char>，读文件时注意char有符号性问题：ASCII 扩展字符（如 0xFF）可能被当负数，导致 map 查不到
怎么从哈夫曼树生成编码表（避免递归爆栈或路径错乱）
递归遍历树生成编码最直观，但输入字符多、频率极不均衡时（比如一个字符占 99%），树可能退化成链表，递归深度超限。更稳的方式是后序遍历 + 显式栈，或直接在建树时给每个节点存编码字符串（用移动语义避免拷贝）。
使用场景：压缩前必须拿到每个字节对应的二进制码字符串，比如 'a' → "101"，后续才能拼接比特流。
立即学习“C++免费学习笔记（深入）”；
- 别在递归函数里用
string += "0"拼接路径——每次调用都拷贝整个字符串，O(n²) 时间；改用引用传入string& code，进入子树前code += '0'，返回前code.pop_back() - 叶子节点判断必须严格：只有
left == nullptr && right == nullptr才算，中间节点即使没子节点（异常情况）也不能当叶子处理 - 编码表最终存在
unordered_map<char string></char>里，查表快；但注意：如果原始数据含\0（比如二进制文件），char键能存，但用cin.get()读时会截断，得换istream::read
怎么把编码表和比特流一起写入文件（绕过字节对齐陷阱）
哈夫曼压缩输出不是纯文本，而是混合了变长比特 + 元信息，直接用 ofstream 写 <code>string 会丢数据——因为 string 的 "101" 是三个字节的 ASCII，不是真正的 3 个比特。
关键点：必须手撸比特写入器，把编码字符串转成连续 bit，每 8 个 bit 打包成一个 unsigned char 写入文件；同时得把编码表（或频次表）写在文件头，否则解压时根本不知道怎么还原。
- 文件头推荐写原始字符频次（
int[256]），共 1024 字节，比存编码字符串更紧凑、无歧义 - 主比特流写完后，最后一字节很可能不满 8 bit，必须在末尾补 0，并在文件头额外记下填充位数（1 字节足够），否则解压会多读几位
- 别用
fstream::binary就以为万事大吉——它只关掉换行转换，不解决比特打包问题；真正要的是自己维护一个unsigned char buffer和当前 bit 位置int pos
解码时为什么总读多一位或崩溃（指针/边界常见坑）
解码是拿比特流逐位匹配编码表，难点不在逻辑，而在指针管理和边界检查。最常出问题是：读完文件末尾还继续 f.read()，返回 0 字节却没检查，导致缓冲区残留旧数据，解码器误以为还有比特可读。
性能影响：用 unordered_map<string char></string> 做反向查表（比特串→字符）看似方便，但每次匹配都要构造 string 并哈希，比用哈夫曼树遍历慢 3–5 倍，尤其长编码出现频繁时。
- 解码必须用树遍历：从根出发，读 1 bit 走右，读 0 bit 走左，到叶子就输出字符并重置回根——这避免了所有字符串构造开销
- 读比特时，先检查是否已读完全部有效比特（由文件头记录的“总比特数”控制），而不是依赖
eof()；eof()只在尝试读失败后才置位 - 动态分配的树节点务必用智能指针（
unique_ptr）管理，或确保析构时递归释放；野指针在解码循环里可能表现为随机字符或段错误，很难复现
哈夫曼本身不难，难的是边界全凑齐：频次统计的字符类型、比特写入的 padding 记录、解码时的有效长度控制——漏一个，压缩后的文件就打不开。
