关于哈夫曼树的一题，望给出详细解释，感激不尽！

A-B合并（权5）
A-B再和C合并（权10）
D-E合并（权16）
（A-B）-C再和F合并（权21）
最后((A-B)-C)-F再和D-E合并（权37）
总之是找两个最小的结点合并，然后生成的新节点权为两个结点权之和。
平均路径长度为（2×3+3×3+5×2+7×1+9×1+12×1）/6=53/6约等于88
各字符Huffman编码可以为:A-0000 B-0001 C- 001 D-10 E-11 F-01
还有什么不懂，看看参考资料的网址吧～

哈夫曼树
一、 基本术语
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+22+41=50
4
2

5 9
WPL=（9+5）3+22+41=50
9
5

4 2
WPL=91+52+（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+33+（5+6+8）2=16+9+38=63
作业：P221/9

设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树
夫曼树的构造：
（1）根据给定的n个权值{w1,w2,,wn}构造n棵二叉树的集合F={T1,T2,,Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；
（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。
哈夫曼bmp (13499 KB)
2008-8-5 17:55
以上是过程
最后的树是这样：
35
20 15
9 11 7 8
3 5
wpl=33 53 72 92 112=78
本文来自: 冠威计算机网(

39
15 24
7 (8) (9) (15)
(2) (5)
带权长度：32+35+28+29+215
平均长度：带权长度/（2+5+8+9+15）

---