哈夫曼树(Huffman Tree)
一.什么是哈夫曼树？
树的带权路径长度（WPL）：每个叶子结点带权路径长度之和
哈夫曼树（最优二叉树）：带权路径长度最小的二叉树
二.哈夫曼树的构造
每次把权值最小的两棵二叉树合并
三.哈夫曼树的特点
1.没有度为1的结点
2.n个叶子结点的哈夫曼树共有2n-1个结点（n2 = n0 -1），没有度为1的结点，所以n=n0+n2=2n-1
四.哈夫曼编码
利用哈夫曼树进行编码：
（1）左右分支：0，1
（2）字符只在叶节点上
eg：如下图
（1）构造哈夫曼树 （2）填充0 1 （ 3）得到字符的对应编码