哈夫曼树的定义、构造及其遍历

定义

Huffman Tree， 给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的WPL(带权路径)长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

构造

在我们已有的权值（例子里的频次）中，每次都找到2个最小的，将它们构造成一颗二叉树，再插入我们已经构造好的二叉树中，将每个值都插完后，我们的哈夫曼树就构造完成了。
image.png
image.png
image.png
image.png
image.png
那我们的代码如何实现呢？如果我们要按如上的方法实现哈夫曼树，首先我们要找到的就是最小值，如何找到最小值一定是我们需要面对的最关键的问题。这里有2种方法：
1、先将所有的权值排序，如何再建立哈夫曼树。
2、先建立最小堆，每次从堆顶选元素来建立哈夫曼树。

遍历

  1. //