哈夫曼树

1. 考点：最优二叉树基本概念

1.1 需要了解的基本概念

• 叶子结点的路径长度：从根结点到该叶子结点之间的分支线数量（即层数减 1，若根结点算第 0 层）。

• 树的路径长度：所有叶子结点路径长度之和。

• 权（Weight） ：叶子结点的数值（代表该结点的重要程度或出现频率）。

• 叶子结点的带权路径长度：该结点的 权重 $\times$ 路径长度。

• 树的带权路径长度（WPL，树的代价） ：所有叶子结点带权路径长度之和：

  $$\text{WPL} = \sum_{i=1}^{n} (w_i \times l_i)$$

(其中 $w_i$ 为叶子结点的权值， $l_i$ 为该叶子结点到根的路径长度)

1.2 图示实例拆解（WPL 计算演练）

观察右侧给出的哈夫曼树结构，其叶子结点为 2、4、8、1（注意：图中带圈的 15、14、12 是非叶子结点的权值，计算 WPL 时只计算叶子结点）：

1. 叶子结点 2 到根 15 的路径长度为 2，其带权路径长度 = $2 \times 2 = 4$
2. 叶子结点 4 到根 15 的路径长度为 3，其带权路径长度 = $4 \ = 12$
3. 叶子结点 8 到根 15 的路径长度为 3，其带权路径长度 = $8 \times 3 = 24$
4. 叶子结点 1 到根 15 的路径长度为 1，其带权路径长度 = $1 \times 1 = 1$

整棵树的带权路径长度 $\text{WPL} = 4 + 12 + 24 + 1 = 41$。

2. 考点：哈夫曼树的定义

2.1 哈夫曼树的核心规律与优化思想

观察图中给出的两棵叶子结点权值完全相同（均为 $1, 2, 4, 8$）的二叉树：

• 左侧树的 WPL 计算：

  $$\text{WPL} = (8 \times 3) + (4 \times 3) + (2 \times 2) + (1 \times 1) = 24 + 12 + 4 + 1 = 41$$

• 右侧树的 WPL 计算：

  $$\text{WPL} = (8 \times 1) + (4 \times 2) + (3 \times 3) + (1 \times 3) = 8 + 8 + 9 + 3 = 28$$

2.2 核心结论

• 基本规律：在叶子结点数量和权重完全一样的情况下，高权重叶子结点离根结点的距离越近（路径长度越短），整体的带权路径长度（WPL）就越小。
• 最优二叉树定义：把带权路径长度最小的树叫做最优二叉树，也称哈夫曼树（Huffman Tree） 。

3. 经典例题

3.1 题目一

3.1.1 初始状态（无编码）

(3)  (5)  (7)  (8)  (11)  (14)  (23)  (29)

---

3.1.2 解析：

3.1.2.1 第一步：合并 3 和 5，生成新节点 8

        [8]
       /   \
      0     1
     /       \
   (3)       (5)

当前集合： (7)  (8)  (11)  (14)  (23)  (29)  [8]

---

3.1.2.2 第二步：合并 7 和 8(新)，生成新节点 15

        [15]
       /    \
      0      1
     /        \
   (7)       [8]
            /   \
           0     1
          /       \
        (3)       (5)

当前集合： (8)  (11)  (14)  (23)  (29)  [15]

---

3.1.2.3 第三步：合并 8 和 11，生成新节点 19

        [19]
       /    \
      0      1
     /        \
   (8)       (11)

当前集合： (14)  (23)  (29)  [15]  [19]

---

3.1.2.4 第四步：合并 14 和 15，生成新节点 29(右)

        [29]
       /    \
      0      1
     /        \
  (14)       [15]
            /    \
           0      1
          /        \
        (7)       [8]
                 /   \
                0     1
               /       \
             (3)       (5)

当前集合： (23)  (29)  [19]  [29]

---

3.1.2.5 第五步：合并 19 和 23，生成新节点 42

         [42]
        /    \
       0      1
      /        \
    [19]      (23)
    /   \
   0     1
  /       \
(8)      (11)

当前集合： (29)  [29]  [42]

---

3.1.2.6 第六步：合并 29 和 29(右)，生成新节点 58

        [58]
       /    \
      0      1
     /        \
  (29)      [29]
            /    \
           0      1
          /        \
       (14)       [15]
                 /    \
                0      1
               /        \
             (7)       [8]
                      /   \
                     0     1
                    /       \
                  (3)       (5)

当前集合： [42]  [58]

---

3.1.2.7 第七步（最终）：合并 42 和 58，生成根节点 100

这是最终的完整哈夫曼树，我直接把每个叶子节点的完整编码标注在叶子上：

                       [100]
                      /     \
                     0       1
                    /         \
                [42]           [58]
               /    \         /    \
              0      1       0      1
             /        \     /        \
          [19]       (23) (29)      [29]
         /    \      ↑    ↑        /    \
        0      1    01    10      0      1
       /        \                /        \
     (8)      (11)            (14)       [15]
      ↑        ↑               ↑        /    \
     000      001             1100     0      1
                                       /        \
                                     (7)       [8]
                                      ↑        /   \
                                     11010    0     1
                                             /       \
                                           (3)       (5)
                                            ↑         ↑
                                          110110   110111

---

3.1.3 📋 叶子节点编码汇总表

把上图中所有原始叶子节点（圆形节点）的编码提取出来，按数值从小到大排列：

权值	完整路径	哈夫曼编码
3	右→右→右→左→左	110110
5	右→右→右→左→右	110111
7	右→右→左→右→左	11010
8	左→左→左	000
11	左→左→右	001
14	右→右→左→左	1100
23	左→右	01
29	右→左	10

3.2 题目二

正确答案：A。

---

3.3 题目三

题目： 给定一组叶子结点的权值序列为 $\{3, 4, 5, 6, 7\}$，用该序列构造一棵哈夫曼树（最优二叉树），则该哈夫曼树的带权路径长度（WPL）为（ ）。

• A、55
• B、57
• C、60
• D、63

【解析】

1. 构造哈夫曼树的过程

（每次选取权值最小的两个节点合并）：

• 初始序列：$\{3, 4, 5, 6, 7\}$
• 第一步：选 $3$ 和 $4$，合并生成新节点 $3 + 4 = 7$。序列变为 $\{5, 6, 7, 7\}$。
• 第二步：选 $5$ 和 $6$，合并生成新节点 $5 + 6 = 11$。序列变为 $\{7, 7, 11\}$。
• 第三步：选 $7$ 和 $7$，合并生成新节点 $7 + 7 = 14$。序列变为 $\{11, 14\}$。
• 第四步：选 $11$ 和 $14$，合并生成根节点 $11 + 14 = 25$。

2. 树形结构与路径长度

对应的树形结构如下：

                     [25]
                    /    \
                   /      \
               [11]        [14]
              /    \       /   \
             /      \     /     \
           (5)      (6) [7]     (7)
          深度2    深度2 /   \   深度2
                      (3)   (4)
                     深度3 深度3

3. WPL 计算过程

各叶子节点的权值与路径长度之积求和：

$$WPL = 5 \times 2 + 6 \times 2 + 3 \times 3 + 4 \times 3 + 7 \times 2$$

$$WPL = 10 + 12 + 9 + 12 + 14 = 57$$

4. 快捷计算法

（哈夫曼树的 WPL 等于所有非叶子节点权值之和）： 生成的中间非叶子节点有：$7, 11, 14, 25$。

$$WPL = 7 + 11 + 14 + 25 = 57$$

正确答案：B（57）。