树和 Huffman Tree 哈夫曼树

基础概念补充

什么是树

这是一棵有12个节点的树（其中，我们定义这棵树每个节点上的数字只是它的编号，没有其他意义）。

1 2 3 4 5 6 7 8 9 10 11 12

其中，如果我们定义1号点为根，则其下方与它直接相连的节点都是它的子树（即：1号点的子节点为2, 3, 4号节点）。对于子节点们，它们上面那个就是自己的父节点（即：节点2, 3, 4的父节点都是1号节点）。

不难看出：

  • 8号节点的子节点为11号和12号节点
  • 7号节点的父节点为3号节点
  • 5号节点没有子节点
  • 1号节点（根）没有父节点

由其中某个点及以下节点组成的集合，称为一棵子树。例如，节点8, 11, 12组成的集合，是节点3的子树。
所有末端的节点，都是这棵树的叶节点。如，节点6就是这棵树的叶节点，节点11也是，节点4亦然。

什么是节点之间路径长度

看上面那棵树。我们定每条路的长度为1，则从点A到点B的路径长度为这两个点之间每条路的长度和。
如，从11号点走到6号点，路径长度为3，途径8号点和3号点。
如，从5号点走到10号点，路径长度为5，途径2号点，1号点，3号点和7号点。
同样，你可以自己算一算其他点之间的路径长度。

什么是树的路径长度

我们定义一棵树的路径长度为从根节点到所有叶节点的路径长度之和。
在上图中，我们定义1号点为根，则4、5、6、9、10、11、12号点为叶子节点。记叶节点编号为x，根节点到叶节点的距离为dist(x)，易得：

xdist(x)
41
52
62
92
103
113
123
∑ d i s t ( x ) \sum{dist(x)} ∑dist(x)16

(悄悄说：笔者希望上表横向排列，即，表头在左边，但不知道该怎么做……在此向诸位熟悉 Markdown 的大佬请教 qwq)
由上表可知，这棵树的路径长度为16.

什么是树的带权路径长度

上表中，我们计算那棵树的路径长度为 ∑ d i s t ( x ) \sum{dist(x)} ∑dist(x). 如果我们认为每个叶子节点都有一个权值（记编号为x的点的权值为value(x)），则树的带权路径长度为 ∑ ( v a l u e ( x ) ⋅ d i s t ( x ) ) \sum{(value(x)·dist(x))} ∑(value(x)⋅dist(x)). 我们假设上述那棵树的叶节点权值如下：

xvalue(x)
420
533
624
946
1058
114
1216

则可计算树的带权路径长度：

xdist(x)value(x)value(x) · dist(x)
412020
523366
622448
924692
10358174
113412
1231648
∑ ( v a l u e ( x ) ⋅ d i s t ( x ) ) \sum{(value(x)·dist(x))} ∑(value(x)⋅dist(x))460

这棵树的带权路径长度为460.

什么是森林

好多棵树放在一起，就是森林。比如这张图展示的就是一个森林：

1 2 3 4 5 6 7 8 9 10 11 12

图中，点 1, 2, 3, 4, 5 构成一棵树。
点 6 自己是一个只有一个节点的树。
点 7 自己是一个只有一个节点的树。
点 8, 10, 11, 12 构成一棵树。
点 9 自己是一个只有一个节点的树。

什么是二叉树

每个节点的子节点数最多为2的树，是二叉树。如图，这是一颗二叉树：

1 2 3 4 5 6 7 8 9 10 11 12

图中，每个节点的左右子节点，分别称为这个节点的左、右子节点。该节点及向下的所有节点组成的集合称为子树。于是，某节点的左、右子节点及以下的节点集合，分别称为左子树和右子树。
不难看出，不是每个节点都同时拥有左右子树。比如图中的6号点，它拥有一棵子树。由于笔者水平有限，画不出左右关系，我们暂时认为12号点是它的右子树，那么它没有左子树。
同样，节点4、节点7和节点10也都只有一个子树。

哈夫曼树

什么是哈夫曼树

假如我们有好多个带权的单节点树。如图（这里，我们定义圆圈内的数字是权值）：

20 33 24 46 58 4 16

现在，我们需要向图中添加一些不作为叶节点的节点，将它们和原来的带权节点连接起来，构成一棵二叉树。该二叉树中，所有新加入的节点都不是叶节点，而所有原有的带权节点都是叶节点。如图所示，我们可以构造出一棵二叉树：

20 33 24 46 58 58 16

从新加入的节点中选取一个根（为方便，我们认为画图时最上方的节点是根节点），这样可以得到树的权值。
不难计算，这棵树的带权路径长度是663.

同样，我们还可以构造出另外模样的二叉树：

20 33 24 46 58 4 16

不难算出，这棵树的带权路径长度是：752.

显然，第二棵树的带权路径长度比第一棵树大。
事实上，我们可以构造出非常多棵这样的二叉树。其中带权路径长度最短的那棵二叉树，即为哈夫曼树。
对于上述带权叶节点，构造出的哈夫曼树如图：

24 33 46 58 4 16 20

如图，这棵树的带权路径长度是519. 找不到带权路径长度比它小的构造方法（相等是可以的，但找不到更小的），不信你可以试试。

观察并思考，可以发现，想要构造哈夫曼树，就要让权值大的节点尽可能靠近根，权值小的节点相对远离根。于是，我们得到一种构造方法：

  1. 从所有根节点中（起初，所有节点都是根，因为所有节点都没有父节点），寻找到权值最小的两个。
  2. 使用一个节点，作为它们的根，将它们连接起来。该节点的权值设为两个子节点的权值之和。
  3. 回到步骤1，直到森林中只有一棵树。

我们跟着这个步骤尝试一下。

初始状态：

24 33 46 58 4 16 20

我们发现，权值最小的根节点，权值为4和16. 于是，我们将它们连起来，并将新的根节点权值设为它们的和：4+16=20

20 24 33 46 58 4 16 20

接下来，找到权值最小的两个根节点。他们的权值分别是20，20.
将它们连接，新的根节点权值为：20+20=40

20 40 24 33 46 58 4 16 20

继续寻找，找到权值分别为24和33的点。连接后，新的根节点权值为：24+33=57

20 40 57 24 33 46 58 4 16 20

继续寻找，找到权值分别为40和46的点。连接后，新的根节点权值为：40+46=86

20 40 57 86 24 33 46 58 4 16 20

继续寻找，找到权值分别为57和58的点。连接后，新的根节点权值为：57+58=115

20 40 57 86 115 24 33 46 58 4 16 20

继续寻找，找到权值分别为86和115的点（当然，也只剩这两个点了）。连接后，新的根节点权值为：86+115=201

20 40 57 86 115 201 24 33 46 58 4 16 20

至此，森林中只有一棵树。这棵树便是哈夫曼树。你可以算一下它的带权路径长度。
你可能觉得，这棵树跟上面那棵哈夫曼树不太一样。但是，它们其实是同构的，即，随意交换任意节点的左右孩子后，它们会变成同一棵树。

哈夫曼树的应用

借助哈夫曼树，我们可以实现很多神奇的操作，如对 ASCII 字符串文本的压缩。
[枫铃树] 使用 Huffman Tree 哈夫曼树实现对 ASCII 字符串文本的压缩与解压