哈夫曼树与哈夫曼编码
哈夫曼树
哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。在这个二叉树中，只有叶子节点才是有效的数据节点,其他只是作为路径而构造的。
带权路径长度
又称WPL，树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度，即树中所有叶节点的带权路径长度之和。
WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)， N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼编码
哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码主要是起到压缩的作用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。
构建哈夫曼树和获得哈夫曼编码以及WPL的计算
下面用一道题来说明构建哈夫曼树和获得哈夫曼编码的过程：
若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）
构造哈夫曼树
首先，从4，5，6，7，8 （为了方便，将这个数组称为a）中找到最小的两个数4和5，作为叶子结点（一般按照左小右大的方式）：
得到新结点权值 9（4+5=9）,从将9加入到剩余的数中，即此时a为6，7，8，9
从中再找到最小的2个数6，7，构造树为：
得到新结点权值 13（6+7=13）,从将13加入到剩余的数中，即此时a为13，8，9，
从剩余的数中找到最小的2个数8和9，构造数为：
得到新结点权值17（8+9=17）,从将17加入到剩余的数中，即此时a为13，17.
最后这两个节点构成根结点：
此时哈夫曼树构造完成了。
那么哈夫曼编码怎么算呢？按左小右大就是结点的左边连线为0，右边为1，即：
获取哈夫曼编码：
则相应数（可以看到叶子结点就是原先数组a中的数），所以只需遍历叶子结点，对每个结点，从根结点往下，直到该叶子结点的路径对应的数，即为该数的哈夫曼编码。如上图得到的哈夫曼编码分别为：
8：00
4：010
5：011
6：10
7：11
WPL的计算：叶节点的带权路径长度之和。对本题：权值4和权值5的路径长度为3，7，8，9的长度都为2，
所以WPL为：（4+5）*3+（6+7+8）*2 = 69