哈夫曼树
一、 基本术语
1. 路径与路径长度
若在一棵树中存在一个结点序列 k1, k2, …., kj ，使得kj是kj+1的双亲（1<=i<j），则称结点序列是从k1到kj 的路径（如树中的某个结点到它的某个祖先，或者到它的某个后代的的包括它本身的一系列按顺序的结点序列称为路径），因树中的每个结点只有一个双亲结点，所以这是两个结点间的唯一路径，从k1到kj 所经过的分支数称为这两点之间的路径长度。它等于结点数-1。
如： 从结点A到结点J的结点序
列为A，B，E，J。
路径长度为3。
8 10
4 5 3
2. 结点的权和带权路径长度
如果根据需要给树中的结点赋予一个有某中意义的实数，则称此实数为该结点的权，结点带权路径长度规定为从树根结点到该结点之间的路径长度乘上该结点的权值所得到的乘积。
3. 树的带权路径长度
树的带权路径长度定义为树中所有叶结点的带权路径长度之和，通常记为：
n
WPL=∑ wili wi和li 分别代表叶结点ki的权值和ki到
i=1 根结点的路径长度
例如：上图的WPL=（4+5+3）*3+（8+10）*2=72
4. 哈夫曼树
哈夫曼树又称为最优二叉树，它是由n个带权叶结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
例如：有四个叶结点a，b，c，d，分别带权为9，4，5，2，可以构成三棵不同的二叉树（当然可以构成更多的二叉树）见下图：
9 4 5 2 WPL=（9+4+5+2）*2=40
4
2
5 9
WPL=（9+5）*3+2*2+4*1=50
4
2
5 9
WPL=（9+5）*3+2*2+4*1=50
9
5
4 2
WPL=9*1+5*2+（2+4）*3=37
可以证明最后一棵二叉树是哈夫曼树。
二、 构造哈夫曼树
1. 将n个叶结点构成独立的n棵二叉树，每棵二叉树只有一个根结点。
2. 选择两棵权值最小的二叉树合并成一棵二叉树，并以这两棵二叉树的权值之和作为这棵二叉树的权值，取消原来的两棵二叉树。
3. 重复2，知道只剩一棵二叉树为止。
例如：有6个带权叶结点的权值分别为：3，6，8，5，2，2，构造一棵哈夫曼树，并计算WPL的结果。
1.构造6棵二叉树
3 6 8 5 2 2
2选出两个权值最小的二叉树的组成一棵二叉树
2 2 合并权值为4
3 6 8 5
3 6 8 5 4
2 2
选出两个权值最小的二叉树的组成一棵二叉树
7 6 8 5
3
2 2
选出两个权值最小的二叉树的组成一棵二叉树
7 11 8
3
5 6
2 2
选出两个权值最小的二叉树的组成一棵二叉树
15 11
8
5 6
3
2 2
选出两个权值最小的二叉树的组成一棵二叉树（最终的哈夫曼树）
8
5 6
3
2 2
WPL=（2+2）*4+3*3+（5+6+8）*2=16+9+38=63
作业：P221/9