带权路径长度(WPL)：设二叉树有N个叶子结点，每个叶子结点带有权值Wk，从根节点到每个叶子结点的长度为lk，则每个叶子结点的带权路径长度之和为：WPL = Wk*lk之和
哈夫曼树(Huffman Tree)(最优二叉树)：
WPL最小的二叉树
哈夫曼树的构造：
每次把权值最小的两棵二叉树合并
利用堆实现(O(NlogN))：
将H按权值调整为最小堆，做H->size - 1次合并，每次从堆中取出两个删除的结点，构成一个新的树，计算新的树的权值，并插入最小堆
哈夫曼树的特点：
1、没有度为1的结点
2、n个叶子结点的哈夫曼树共有2n-1个结点
3、哈夫曼树的任意非叶结点的左右子树交换后，仍是哈夫曼树
4、同一组权值，可能存在不同构的两棵哈夫曼树
哈夫曼编码：
将一段字符集合按出现频次组成哈夫曼树，叶结点即为该字符集合的编码
网友评论