一本正经的聊数据结构（6）：最优二叉树 —— 哈夫曼树
lickylin 2020-05-31
前文传送门：
基础知识
感谢某位在后台留言的同学，让我想起来我还有这个没写完的系列。
在最开始，先了解几个基础概念：
- 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。
上面这个二叉树中，根节点 A 到叶子结点 I 的路径，就是A，B，D，I。
- 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。
在这个二叉树中，根节点 A 到叶子结点 H 的路径长度就是 3 。
- 结点的权：给每一个结点赋予一个数值，被称为这个结点的权。
- 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。
我们假设节点 H 的权是 5 ，从根结点到结点 H 的路径长度是 3 ，那么结点 H 的带权路径长度是 3 X 5 = 15。
- 树的带权路径长度：在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为 「WPL」 。
还是这颗树，它的带权路径长度是 1 X 2 + 2 X 1 + 2 X 3 + 2 X 4 + 3 X 5 + 3 X 6 = 51 。
哈夫曼树
哈弗曼树就是在用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为「最优二叉树」，有时也叫「哈夫曼树」或者「赫夫曼树」。
在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。
需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗，在同一层，左右叶子节点交换位置，树的带权路径长度是一样的，就比如下面这两个哈夫曼树：
哈弗曼树的构建过程
那么如何构建一个哈夫曼树呢？我们这里举个例子，比如我们有这么几个叶子节点：3，4，7，9，13，15，17：
第一步：选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和：
第二步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列，也就是从队列中删除 3 和 4 ，插入 7 ，并且仍然保持队列的升序：
第三步：选择当前权值最小的两个结点，生成新的父结点。
这一步其实是在重复上一步操作，当前队列中最小的节点是 7 和 7 ，生成新的父结点权值是 7 + 7 = 14 ：
第四步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这一步依然是在重复，从队列中删除 7 和 7 ，加入 14 ，并且仍然保持队列的升序：
第五步：选择当前权值最小的两个结点，生成新的父结点。
这一步还是重复操作。当前队列中权值最小的结点是 9 和 14 ，生成新的父结点权值是 9 + 14 = 23 ：
第六步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这一步依然是在重复，从队列中删除 9 和 14 ，加入 23 ，并且仍然保持队列的升序：
第七步：选择当前权值最小的两个结点，生成新的父结点。
这一步从队列中选择权值最小的结点是 13 和 15 ，生成新的父结点权值是 13 + 15 = 28 ：
第八步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
从队列中删除 13 和 15 ，加入 28 ，并且仍然保持队列的升序：
第九步：选择当前权值最小的两个结点，生成新的父结点。
这一步从队列中选择权值最小的结点是 17 和 23 ，生成新的父结点权值是 17 + 23 = 40 ：
第十步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
从队列中删除 17 和 23 ，加入 40 ，并且仍然保持队列的升序：
第十一步：选择当前权值最小的两个结点，生成新的父结点，移除队列中的最后两个节点（懒得画了，最后两步并一步）。
这一步从队列中选择权值最小的结点是 28 和 40 ，生成新的父结点权值是 28 + 40 = 68 ：
此时，我们得到的这棵树就是哈弗曼树。
哈夫曼树就介绍到这里，下一节，将会介绍哈夫曼树的用途：哈夫曼编码。
参考
http://c.biancheng.net/view/3398.html
https://baijiahao.baidu.com/s?id=1663514710675419737&wfr=spider&for=pc
