感谢某位在后台留言的同学，让我想起来我还有这个没写完的系列。
在最开始，先了解几个基础概念：
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。上面这个二叉树中，根节点A到叶子结点I的路径，就是A，B，D，I。
路径长度：在一条路径中，每经过一个结点，路径长度都要加1。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第i层结点的路径长度为i-1。在这个二叉树中，根节点A到叶子结点H的路径长度就是3。
结点的权：给每一个结点赋予一个数值，被称为这个结点的权。结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。我们假设节点H的权是5，从根结点到结点H的路径长度是3，那么结点H的带权路径长度是3X5=15。
树的带权路径长度：在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为「WPL」。还是这颗树，它的带权路径长度是1X2+2X1+2X3+2X4+3X5+3X6=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：
此时，我们得到的这棵树就是哈弗曼树。
哈夫曼树就介绍到这里，下一节，将会介绍哈夫曼树的用途：哈夫曼编码。
参考