【数据结构 哈夫曼树】构建步骤、案例

哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度（WPL）最短的树。它广泛应用于数据压缩（如哈夫曼编码），通过为高频字符分配短编码、低频字符分配长编码，实现高效压缩。

一、基本概念

• 权值：叶子节点的权重（如字符频率）。
• 路径长度：节点到根经过的边数。
• 带权路径长度（WPL）：所有叶子节点的权值 × 路径长度之和。

目标：构造一棵WPL最小的二叉树。

二、构造步骤

1. 将权值作为叶子节点，按从小到大排序。
2. 选择权值最小的两个节点，合并为一个新节点，新节点权值为两者之和。
3. 将新节点加入原列表，重复步骤2，直到只剩一棵树。

三、案例演示（权值：5, 9, 12, 13）

假设字符A、B、C、D的频率分别为5、9、12、13。构造哈夫曼树：

步骤分解

1. 初始节点：5, 9, 12, 13。
2. 第一次合并：5和9 → 新节点14。
   • 剩余节点：12, 13, 14。
3. 第二次合并：12和13 → 新节点25。
   • 剩余节点：14, 25。
4. 第三次合并：14和25 → 根节点39。

树结构

      39
    /    \
  14      25
 /  \    /  \
5   9  12   13

路径长度与编码

• A (5)：路径为左→左 → 编码 00（路径长度2）
• B (9)：路径为左→右 → 编码 01（路径长度2）
• C (12)：路径为右→左 → 编码 10（路径长度2）
• D (13)：路径为右→右 → 编码 11（路径长度2）

计算WPL

• WPL = 5×2 + 9×2 + 12×2 + 13×2 = 78 （注：此处为简化案例，实际中合并顺序可能导致不同结构，但WPL相同）

四、另一个案例（权值：3, 5, 7, 8, 11）

构造过程

1. 初始节点：3, 5, 7, 8, 11。
2. 第一次合并：3和5 → 8。
   • 剩余节点：7, 8, 8, 11。
3. 第二次合并：7和8 → 15。
   • 剩余节点：8, 11, 15。
4. 第三次合并：8和11 → 19。
   • 剩余节点：15, 19。
5. 第四次合并：15和19 → 根节点34。

树结构

        34
      /    \
    15      19
   /  \    /  \
  7    8  8   11
         / \
        3   5

WPL计算

• 3的路径长度：3 → WPL贡献：3×3=9
• 5的路径长度：3 → 5×3=15
• 7的路径长度：2 → 7×2=14
• 8的路径长度：2 → 8×2=16
• 11的路径长度：2 → 11×2=22 总WPL = 9+15+14+16+22 = 76

五、哈夫曼树的特点

1. 没有度为1的节点（严格二叉树）。
2. n个叶子节点共有2n-1个节点。
3. 编码是前缀码，无歧义。

六、应用场景

• 数据压缩：如ZIP、JPEG文件。
• 编码优化：高频字符用短码，低频用长码。

通过构造哈夫曼树，可高效实现数据的无损压缩，平衡存储与传输效率。