从大学毕业后，读研专业很少涉及到数据结构。因找工作秋招需求，因此再捡回以前遗忘的数据结构知识
哈夫曼树
1. 怎么造一棵哈夫曼树？（核心口诀：每次挑最小的两个）
我们现在有 5 个叶子节点，权值分别是：11、8、6、2、5。 把它们看作是一个池子里的 5 个数字。
- 第一步：挑池子里最小的两个数（2 和 5） 把它们俩绑在一起，生成一个“父节点”，权值相加 2+5=7。 现在池子里剩下的数字是：11、8、6，以及新合成的 7。
- 第二步：再从池子里挑最小的两个数（6 和 7） 把它们绑在一起，生成新的父节点 6+7=13。 现在池子里剩下的数字是：11、8，以及新合成的 13。
- 第三步：继续挑最小的两个数（8 和 11） 绑在一起，生成新父节点 8+11=19。 现在池子里剩下的数字是：13 和 19。
- 第四步：最后把剩下的 13 和 19 绑在一起 生成最终的根节点 13+19=32。 到这里，只剩一个数字，树就建完了！
2. 什么是带权路径长度（WPL）？怎么算？
- 路径长度：从最顶上的根节点，走到某个叶子节点，需要经过几条线（向下走几层）。
- 带权路径长度（WPL）：把每个叶子节点的权值 × 它走的层数，然后全部加起来。
我们来看看刚才那棵树里，每个原始叶子节点在第几层：
- 11 和 8：它们是在第三步直接和 19 绑定的，19 往上直接就是根节点 32，所以它们只往下走了 2 层。
- 6：它是在第二步和 7 绑成 13，13 往上是根节点 32，它也往下走了 2 层。
- 2 和 5：它们在第一步绑成 7，7 往上是 13，13 往上是 32，它们在最底下，走了 3 层。
老老实实的标准算法：
WPL=11×2+8×2+6×2+2×3+5×3
WPL=22+16+12+6+15=71
算层数很容易数错眼花，其实数学家早帮我们总结了一个极其简单的“作弊”公式： 一棵哈夫曼树的 WPL，就等于你刚才造树的过程中，所有“新合成的父节点”的权值之和！
我们回头看看刚才造树时，产生过哪些新的父节点？ 第一步造了 7，第二步造了 13，第三步造了 19，第四步造了根节点 32。 直接把它们加起来：
WPL=7+13+19+32=71