二叉树（五）——哈夫曼树与哈夫曼编码
基本概念
WPL（树的带权路径长度）
若给具有m个叶结点的二叉树的每个叶结点赋予一个权值，则该二叉树的带权路径长度定义为:
其中，wi为第i个叶结点被赋予的权值，li为第i个叶结点的路径长度；
例子如下：
哈夫曼树的定义
给定一组权值，构造出的具有最小带权路径长度的二叉树称为哈夫曼树，如下：
哈夫曼树的特点
哈夫曼树具有如下特点：
1、权值越大的叶结点离根结点越近，权值越小的叶结点离根结点越远；（这样的二叉树WPL最小）
2、无度为1的结点；
3、哈夫曼树不是惟一的。
哈夫曼树的构造
哈夫曼树构造的核心思想如下：
1、对于给定的权值W={w1,w2,…, wm}，构造出树林F={T1,T2,…, Tm}，其中，Ti(1≤i≤m)为左、右子树为空，且根结点(叶结点)的权值为wi的二叉树；
2、将F中根结点权值最小的两棵二叉树合并成为一棵新的二叉树，即把这两棵二叉树分别作为新的二叉树的左、右子树，并令新的二叉树的根结点权值为这两棵二叉树的根结点的权值之和，将新的二叉树加入F的同时从F中删除这两棵二叉树；
3、重复步骤2，直到F中只有一棵二叉树。
例子如下：