哈夫曼树和哈夫曼编码

定义：当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”，哈夫曼树不唯一。

树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。
下面树的WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

构造哈夫曼树：以2，6，8，9，3为例。

  1. 选最小的两个数，构建树，排序

  2. 重复上述操作，如果有相同的值，谁前谁后无所谓，最后WPL值一样。

哈夫曼编码：二叉树往左边为0，往右边为1，即可得到每个树的编码。