哈夫曼树的构造

构造步骤

简单来说就是不断选取当前最小的两个结点组成新结点，新结点权值为两个结点的权值和，将新结点替换原来的两个结点重新进行排序，不断重复直到最后只有一个结点（约定较小的一个在左侧）。

具体步骤如下：

根据给定的 n 个权值，构造 n 棵只有一个根结点的二叉树，n 个权值分别是这些二叉树根结点的权。
设 F 是由这 n 棵二叉树构成的集合，在 F 中选取两棵根结点权值最小的树作为左、右子树，构造一棵新的二叉树，置新二叉树根结点的权值 = 左、右子树根结点权值之和。
从 F 中删除这两棵树，并将新树加入 F。
重复第 2 和 3 步，直到 F 中只含一棵树为止（这棵树便是 Huffman 树）。

构造以 W = (5, 14, 40, 26, 10) 为权的哈夫曼树。

要使二叉树 WPL 小，就须在构造树时，将权值大的结点靠近根。

Huffman 树中没有度为 1 的结点，这类树又称严格的（strict）或正则的二叉树。
n 个结点构造的 Huffman 树最终有多少个结点？
- Huffman 树的构造过程说明：n 个结点需要进行 n - 1 次合并，每次合并都产生一个新的结点，所以最终的 Huffman 树共有 2n - 1 个结点。