赫夫曼树是贪心算法的经典应用，通过为高频字符分配短编码、低频字符分配长编码实现最短总编码长度，保证无损压缩与唯一可解码；构建时以字符频次为权值自底向上合并节点，生成前缀码；编码需同步存储频次或树结构以支持解压。
赫夫曼树（Huffman Tree）是贪心算法的经典应用，核心在于为出现频率高的字符分配短编码、频率低的分配长编码，从而实现整体编码长度最短——这正是无损压缩的关键。它不改变原始数据内容，只优化表示方式，解码时能唯一还原，因此完全无损。
构建赫夫曼树：按权值自底向上合并
给定字符集及其在文件中的出现频次（即权值），构建步骤如下：
- 将每个字符作为叶子节点，权值为其频次，放入优先队列（最小堆）
- 重复执行：取出权值最小的两个节点，新建一个内部节点，其权值为二者之和，左子为较小者（或任选），右子为较大者；将新节点重新入队
- 直到队列只剩一个节点——即赫夫曼树的根节点
注意：左右子节点的分配顺序影响编码中0/1的方向（如左0右1），但只要编码规则统一，不影响唯一可解码性。
生成赫夫曼编码：从根到叶走路径
对每个叶子节点，从根出发回溯至该叶，每向左走记0，向右走记1（或反之），路径上0/1序列即为该字符的赫夫曼编码。
deep-java-review
下载
Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...
- 可用递归或栈记录路径，避免重复遍历
- 实际实现中常在建树后用DFS/BFS一次性生成所有编码，并存入哈希表（char → string）供后续编码使用
- 编码一定是前缀码：任意字符编码都不是另一字符编码的前缀，保证解码无歧义
文件压缩与解压：编码+存储树结构
压缩过程不只是替换字符为编码，还需让解压方知道如何解码——即重建同一棵赫夫曼树：
- 方案一（常用）：将字符频次统计信息（如ASCII码+频次对）写入压缩文件头部，解压时重新建树
- 方案二：只保存树的拓扑结构（如用0表示内部节点、1表示叶子+后跟字节），更节省空间但实现稍复杂
- 正文部分将原文件逐字节查表转为比特流，按字节对齐写入（末尾补位需记录补了多少位）
解压时先读头部重建树，再逐比特匹配：从根出发，遇0走左、遇1走右，到达叶子即输出对应字符，重置回根继续下一段。
实际编码注意事项
直接操作比特而非字节容易出错，建议：
- 用整型变量（如uint32_t）缓存待写入的比特，满8位再写入文件；记录当前已写入的比特数
- 压缩前必须完整扫描一遍源文件统计频次；若文件极大，可采样或分块统计（但会降低压缩率）
- 对空文件、单字符文件等边界情况单独处理，避免建树失败
- 赫夫曼编码本身不加密、不纠错，常与其它技术组合（如ZIP中先LZ77后Huffman）
它不复杂但容易忽略细节，关键是把频次、建树、编码、比特流、树同步这五个环节串成闭环。
