哈夫曼树
哈夫曼树（Huffman Tree），也称为最优二叉树，是一种特殊的带权路径长度最短的二叉树。它常用于数据压缩和编码，特别是哈夫曼编码。
以下是哈夫曼树的构建过程以及一个简单的例子：
构建过程：
- 将给定的n个权值作为n棵独立的二叉树。
- 在森林中选择两个根节点权值最小的树合并，作为一个新树的左、右子树，且新树的根节点权值为其左、右子树根节点权值之和。
- 从森林中删除选取的两棵树，并将新树加入森林。
- 重复步骤2和3，直到森林中只剩下一棵树为止，这棵树即为所求的哈夫曼树。
例子：
假设我们有以下字符及其出现的频率：
a: 5
b: 9
c: 12
d: 13
e: 16
f: 45
构建哈夫曼树的过程如下：
- 初始时，我们有6棵独立的树。
- 选择频率最小的两个字符'a'(5)和'b'(9)合并，得到一个新的节点，权值为14。
- 接下来，选择频率最小的字符'c'(12)和'd'(13)合并，得到一个新的节点，权值为25。
- 然后，选择上一步得到的权值为14的节点和'e'(16)合并，得到一个新的节点，权值为30。
- 最后，将权值为25和30的两个节点与'f'(45)合并，得到哈夫曼树的根节点，权值为100。
通过这种方式，我们得到了一个哈夫曼树，其中路径最短的字符是频率最高的字符，这有助于实现有效的编码。
在实际应用中，哈夫曼编码使用哈夫曼树为每个字符分配一个唯一的变长编码。频率高的字符有较短的编码，而频率低的字符有较长的编码，从而实现数据的有效压缩。