5.2 哈夫曼树Huffman Tree

定义

如何构造一棵树，使得WPL总权重值最小
哈弗曼的思想：将两个最小权重的节点合并，生成一个新的节点

特点

1. 没有度为1的节点

2. n个叶子结点的哈弗曼树共有2n-1个结点
   n2 = n0 - 1
   哈夫曼树没有度为1的节点，所以总的节点个数：n+n-1 = 2n - 1

3. 哈夫曼树任意非叶子节点的左右子树交换后仍然是哈夫曼树

4. 同一组权值{},存在不同构的两棵哈夫曼树。但是最优化wpl的值相同