每日学习一个数据结构-哈夫曼树Huffman Tree

哈夫曼树（Huffman Tree）是一种特殊的二叉树，用于最小化带权路径长度，通常应用于数据压缩。以下是关于哈夫曼树的详细介绍：

基本概念

• 带权路径长度（WPL）：对于一棵二叉树，带权路径长度是所有叶子结点的权重与其到根结点的路径长度的乘积之和。哈夫曼树的目标是构造一棵带权路径长度最小的二叉树。
• 叶子结点：二叉树中最底层的结点，没有子结点。
• 非叶子结点：除了叶子结点之外的所有结点，拥有至少一个子结点。

构造方法

哈夫曼树的构造遵循以下步骤：

1. 初始状态：给定一组带有权重的叶子结点，构造一个森林，其中每个结点都是一个孤立的树。
2. 合并：从森林中找出两个具有最小权重的树，并创建一个新的结点作为它们的父结点，新结点的权重等于两个子结点的权重之和。
3. 更新森林：用新创建的树替换原先的两棵树。
4. 重复：重复上述步骤，直到所有结点合并成单棵树。

特点

• 最优性：哈夫曼树构造的编码是前缀编码，即没有任何字符的编码是另一个字符编码的前缀，这样可以保证解码的唯一性。
• 非唯一性：尽管哈夫曼树构造的编码是最优的，但是哈夫曼树本身并不是唯一的。根据不同的构造顺序可能会得到不同的树形，但它们的带权路径长度相同。
• 编码规则：在哈夫曼树中，从根结点到叶子结点的路径可以定义为字符的编码，通常约定左分支编码为0，右分支编码为1。
• 叶子结点度：哈夫曼树中不存在度为1的结点，只有度为0（叶子结点）和度为2（内部结点）的结点。

应用

哈夫曼树的主要应用领域包括数据压缩和传输优化。例如，在文件压缩软件中，使用哈夫曼编码可以有效地减少文件大小，从而节省存储空间或加快文件在网络上的传输速度。

实例

假设有四个字符A、B、C、D，它们的频率分别为5、9、12、13。构造哈夫曼树的过程如下：

1. 初始森林：{A:5}, {B:9}, {C:12}, {D:13}
2. 合并A和B，形成新结点AB(5+9=14)
3. 当前森林：{AB:14}, {C:12}, {D:13}
4. 合并C和D，形成新结点CD(12+13=25)
5. 当前森林：{AB:14}, {CD:25}
6. 合并AB和CD，形成新结点ABCD(14+25=39)

最终得到的哈夫曼树可以用来为每个字符生成一个唯一的编码，例如：

• A: 00
• B: 01
• C: 10
• D: 11

通过这种方式，可以有效地压缩原始数据。