哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度（WPL）最短的树。它广泛应用于数据压缩（如哈夫曼编码），通过为高频字符分配短编码、低频字符分配长编码，实现高效压缩。
一、基本概念权值：叶子节点的权重（如字符频率）。路径长度：节点到根经过的边数。带权路径长度（WPL）：所有叶子节点的权值 × 路径长度之和。目标：构造一棵WPL最小的二叉树。
二、构造步骤将权值作为叶子节点，按从小到大排序。选择权值最小的两个节点，合并为一个新节点，新节点权值为两者之和。将新节点加入原列表，重复步骤2，直到只剩一棵树。三、案例演示（权值：5, 9, 12, 13）假设字符A、B、C、D的频率分别为5、9、12、13。构造哈夫曼树：
步骤分解初始节点：5, 9, 12, 13。第一次合并：5和9 → 新节点14。 剩余节点：12, 13, 14。第二次合并：12和13 → 新节点25。 剩余节点：14, 25。第三次合并：14和25 → 根节点39。树结构代码语言：javascript复制 39
/ \
14 25
/ \ / \
5 9 12 13路径长度与编码A (5)：路径为左→左 → 编码 00（路径长度2）B (9)：路径为左→右 → 编码 01（路径长度2）C (12)：路径为右→左 → 编码 10（路径长度2）D (13)：路径为右→右 → 编码 11（路径长度2）计算WPLWPL = 5×2 + 9×2 + 12×2 + 13×2 = 78
（注：此处为简化案例，实际中合并顺序可能导致不同结构，但WPL相同）四、另一个案例（权值：3, 5, 7, 8, 11）构造过程初始节点：3, 5, 7, 8, 11。第一次合并：3和5 → 8。 剩余节点：7, 8, 8, 11。第二次合并：7和8 → 15。 剩余节点：8, 11, 15。第三次合并：8和11 → 19。 剩余节点：15, 19。第四次合并：15和19 → 根节点34。树结构代码语言：javascript复制 34
/ \
15 19
/ \ / \
7 8 8 11
/ \
3 5WPL计算3的路径长度：3 → WPL贡献：3×3=95的路径长度：3 → 5×3=157的路径长度：2 → 7×2=148的路径长度：2 → 8×2=1611的路径长度：2 → 11×2=22
总WPL = 9+15+14+16+22 = 76五、哈夫曼树的特点没有度为1的节点（严格二叉树）。n个叶子节点共有2n-1个节点。编码是前缀码，无歧义。六、应用场景数据压缩：如ZIP、JPEG文件。编码优化：高频字符用短码，低频用长码。通过构造哈夫曼树，可高效实现数据的无损压缩，平衡存储与传输效率。