哈夫曼树，又称最优二叉树，是一种用于无损数据压缩的树形结构。它由美国计算机科学家大卫·哈夫曼在1952年提出。

1. 基础概念

在数据压缩中，哈夫曼树将每个符号分配一个长度可变的二进制代码。符号出现的频率越高，其代码就越短。

2. 创建频率表

作为第一步，需要创建输入符号的频率表。对于每个符号，频率表记录它在输入数据中出现的次数。

3. 构造初始列表

使用频率表创建一个初始列表，其中每个符号是一个单独的叶子节点。节点根据其频率从小到大排序。

4. 合并频率最小的两个节点

从初始列表中，合并频率最小的两个节点。创建一个新的内部节点作为它们的父节点，频率等于这两个节点频率之和。

5. 更新列表

将新创建的内部节点添加到列表中，按频率重新排序。重复步骤 4 和 5，直到只剩下一个内部节点。

6. 构建二叉树

从列表中的最后一个内部节点开始，建立一棵二叉树。每个内部节点都有两个子节点。子节点的频率要么等于它们的父节点频率，要么小于它们的父节点频率。

7. 编码符号

通过遍历二叉树，为每个符号分配一个二进制代码。从根节点开始，向左分支为 0，向右分支为 1。将沿途的二进制位连接起来，直到到达符号所在的叶子节点。

示例

以下是一个包含符号和频率的频率表：

| 符号 | 频率 |

|---|---|

| A | 5 |

| B | 9 |

| C | 12 |

| D | 13 |

构造哈夫曼树：

1. 创建初始列表：A (5), B (9), C (12), D (13)

2. 合并 A 和 B：创建一个内部节点 (14)，使其子节点为 A 和 B

3. 更新列表：A (5), (14) (14), C (12), D (13)

4. 合并 (14) 和 C：创建一个内部节点 (26)，使其子节点为 (14) 和 C

5. 更新列表：(26) (26), D (13)

6. 合并 (26) 和 D：创建一个内部节点 (39)，使其子节点为 (26) 和 D

7. 构建二叉树：

```

(39)

/ \

(26) D

/ \

(14) C

/ \

A B

```

编码：

A：0

B：10

C：110

D：111