5-7 哈夫曼树的构造算法
哈夫曼树特点：哈夫曼树中权越大的叶子离根越近
贪心算法：构造哈夫曼树时首选权值小的叶子结点
哈夫曼算法（构造哈夫曼树的方法）
- 根据n个给定的权值$\{w_1,w_2,...,w_n\}$构成n棵二叉树的森林$F=\{T_1,T_2,...,T_n\}$，其中$T_i$只有一个带权为$w_i$的根结点
- 在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根节点的权值之和
- 在F中删除这两棵树，同时将新得到的二叉树加入森林中
- 重复（2）和（3），直到森林中有一棵树为止，这棵树即哈夫曼树
哈夫曼算法口诀：
- 构造森林全是根
- 选用两小造新树
- 删除两小添新人
- 重复（2）、（3）剩单根
- 哈夫曼树的结点的度为0或2，没有度为1的结点
- 包含n个叶子结点的哈夫曼树中共有2n-1个结点
5-7 哈夫曼树构造算法的实现