软考-软件设计师：数据结构-特殊二叉树-最优二叉树（哈夫曼树、赫夫曼树）

作者：马育民 • • 阅读：10099

介绍

哈夫曼树（Huffman Tree）又称 赫夫曼树、最优二叉树，是带权路径长度（WPL）最短的二叉树，由David A. Huffman于1952年提出，核心是用贪心策略合并最小权值节点，让高频元素路径更短、低频元素路径更长，实现整体最优。它广泛用于哈夫曼编码、数据压缩等领域，也是无损压缩的经典基础技术。

关键概念

路径

树中一个节点 到 另一个节点间的路线

如：从根节点 15 到节点 8 之间的路径：15 → 14 → 12 → 8

路径长度

路径里 有多少条边（分支），就是路径长度

如：叶子结点 8 的到根节点 15 的路径，有 3 条边，所以路径长度是 3

树的路径长度

所有叶子结点路径长度之和

节点的权（权重）

节点的关联数值

如：叶子节点 8 的权是 8

叶子节点的 带权路径长度

节点权重*路径长度

如：叶子节点 8 的带权路径长度 8*3 = 24

带权路径长度（树的代价）

所有 叶子结点 带权路径长度之和

定义

带权路径长度最小的二叉树，即：所有 叶子节点 的 带权路径长度 之和 最小的二叉树

特点

  • 严格二叉树：所有非叶子节点都有左、右两个子节点，无单支节点。

  • 权值分布：权值越大的节点离根越近，权值越小的节点离根越远，保证 WPL 最小。

关键特点====================

  1. 所有非叶子节点，都是它两个子节点的和

  2. 由特点 1 可知，所有非叶子节点，一定有 2 个子节点（否则没法求和）

  3. 由特点 1 可知，叶子节点数量为 n，则哈夫曼树的 总节点数为 2n - 1（如：4个叶子节点，每两个节点有一个父结点，所以4个叶子节点有2个父结点，2个父结点有1个根节点，符合：2*4-1=7）。

应用场景

  • 数据压缩：ZIP、PNG、HTTP/2 头部压缩等，核心是哈夫曼编码。
  • 最优判定树：按事件概率分配判定步骤，降低平均判定次数。
  • 任务调度：给高优先级任务分配短路径，提升整体吞吐与响应速度。

解决一个问题需要分成几步并且这几步需要的代价很明确，我们要求最小的代价的时候，看起来像贪心的题目，我们都可以用哈夫曼树来解决，如：

  • 小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的重量之和

  • 如一块木板分割成N块，输入每块的长度，切割木板的长度即为花费的钱，求最小花费。

构建哈夫曼树

使用贪心算法，如：有一组权值：2, 3, 5, 7，画出哈夫曼树（数字代表权重）

分析

  1. 给出的权值，表示叶子节点，4个权值 2, 3, 5, 7，表示4个叶子节点，根据特点可知，总共节点数：2n-1 = 2*4-1 = 7

  2. 如果乱序，先排序

  3. 找到 权值最小的两个节点，相加的和，就是父节点，这3个节点组成树。并将新增的父节点，放到剩余的节点中

  4. 重复第3步

初始节点（都是叶子）

节点：2，3，5，7

[2]   [3]   [5]   [7]

第1步：选最小两个：2 和 3，合并成 5

新节点：5
剩余节点：5（新），5，7

        [5]
       /   \
     [2]   [3]

剩余节点：[5]   [7]

第2步：再选最小两个：5 和 5，合并成 10

新节点：10
剩余节点：10，7

           [10]
         /      \
       [5]      [5]
      /   \
    [2]   [3]

剩余节点：[7]

第3步：最后合并 7 和 10，得到根 17

最终哈夫曼树：

            [17]
          /      \
        [7]      [10]
                /      \
              [5]      [5]
                      /   \
                    [2]   [3]

做题技巧

  1. 给出的权值，就是叶子节点
  2. 根据权值数量，算出总共节点的数量，公式：2n-1
  3. 如果权值未排序，就先排序
  4. 找到 权值最小的两个节点，相加的和，就是父节点，这3个节点组成树。并将新增的父节点，放到剩余的节点中
  5. 同一层结点，从左到右依次增大
  6. 编号：左边线编号为 0，右边线编号为 1（看下面题2）
  7. 编码（叶子结点才需要编码）：从根到叶子节点，路径的编号（看下面题2）

例子

有一组权值 5,29,7,8,14,23,3,11，请尝试构造哈夫曼树

分析

  1. 8个权值，表示8个叶子节点，总共节点数：2n-1 = 2*8-1 = 15

  2. 排序，结果：3,5,7,8,11,14,23,29

  3. 找到 权值最小的两个节点，相加的和，就是父节点，这3个节点组成树。并将新增的父节点，放到剩余的节点中

  4. 重复第3步

提示

  • 编号，左边线编号为 0，右边线编号为 1
  • 只有叶子结点才需要对应的编码

步骤

第1步
  1. 选出最小的2个节点：3、5，和是 8，组成树
  2. 将 8 放到剩余节点中，剩余节点：7,8,8,11,14,23,29
    8
3       5
第2步
  1. 从剩余节点中，选出最小的2个节点：7、8，和是 15，组成树（注意：这里 有2个8,一个是 上一步的和，一个是 叶子结点 8，具体用哪个 8 ，不影响结果，这里用 上一步的和）
  2. 将 15 放到剩余节点中，剩余节点：8,11,14,15,23,29
    15
7         8
      3       5
第3步
  1. 从剩余节点中，选出最小的2个节点：8、11，和是 19，组成树
  2. 将 19 放到剩余节点中，剩余节点：14,15,19,23,29
   19
8     11
第4步
  1. 从剩余节点中，选出最小的2个节点：14、15（第2步的和），和是 29，组成树
  2. 将 29 放到剩余节点中，剩余节点：19,23,29,29
     29
14         15
       7        8
            3       5
第5步
  1. 从剩余节点中，选出最小的2个节点：19（第3步的和）、23，和是 42，组成树
  2. 将 42 放到剩余节点中，剩余节点：29,29,42
       42
   19     23
8     11
第6步
  1. 从剩余节点中，选出最小的2个节点：29（第4步的和）、29（叶子节点），和是 58，组成树
  2. 将 58 放到剩余节点中，剩余节点：42,58
     58
29        29
     14         15
            7        8
                 3       5
第7步

将节点 42、58 求和 100，即：根节点

答案

  • 同一层结点，从左到右依次增大
  • 左边线编号为 0，右边线编号为 1

题

已知某文档包含5个字符，每个字符出现的频率如下表所示。采用哈夫曼编码对该文档压缩存储，则单词“cade”的编码为（ ），文档的压缩比为（ ）

A、1110110101
B、1100111101
C、1110110100
D、1100111100

A、20%
B、25%
C、27%
D、30%

问题1 - 分析

问题1 - 答案

A

问题2 - 分析

提示： 压缩比=（压缩前-压缩后）/压缩前

压缩前，若要表示 5 个不同的字符，用二进制编码至少需要 3 位二进制，即每位字符占据空间 3bit，
平均字符长度为：

3×40%+3×10%+3×20%+3×16%+3×14%=3;

压缩后，这5个字符的编码长度（线数量）分别为 1、3、3、3、3，
平均编码长度为：

1×40%+3×10%+3× 20%+3×16%+3×14%=2.2;

压缩比为：

(3-2.2)/3=27%

问题2 - 答案

C

题

以下关于Huffman（哈夫曼）树的叙述中，错误的是（）

A、权值越大的叶子离根结点越近
B、Huffman（哈夫曼）树中不存在只有一个子树的结点
C、Huffman（哈夫曼）树中的结点总数一定为奇数
D、权值相同的结点到树根的路径长度一定相同

分析

选项A：正确
选项B：正确，因为每次都是两个最小值相加
选项C：正确，因为每次都是两个最小值相加
选项D：不一定，当有多个相同值时，权重不同

原文出处：/show_1GWvx1uCGIl.html

吉ICP备15003043号