权值w={2.,3,5,7,9,12}，画出哈夫曼树，并求出其带权路径长度

哈夫曼树见图。用word随便画的，比较难看。

带权路径长度 （2+3）3+(5+7+9)2+121=15+42+12=69

其实你可以根据下面的直接求。

哈夫曼树的构造

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树

第一步：排序 2 4 5 9
第二步：挑出2个最小的 2 4 为叶子构造出
6
2 4
第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出：
11
6 5
2 4
第四步：继续生长
20
11 9
6 5
2 4
权值为 23+43+52+91=37
也可以20+11+6=37
例题：6、13、18、30、7、16
排序 6 7 13 16 18 30
13
6 7
26 26大于16或18 =》分支生长
13 13
6 7
26 34
13 13 16 18
6 7
此时最小的2个数为 26 30 得出
56 34
26 30 16 18
13 13
6 7
最后得出 90
56 34
26 30 16 18
13 13
6 7 权值 219
90+56+26+13+34 or 64+74+133+302+162+182

哈夫曼树           74

/ \

42                               32

/    \                            /    \

23         19                     12     20

/    \        /   \

15     8     9   10

/   \

8    7

/ \

3   5

编码：A（010）B（00000）C（00001）D（001）E（10）F（11）G（0001）H（011）

带权路径长度值为：（3+5）5+74+（8+9+10）3+（12+20）2=213

This is  it！！！  求采纳

①首先把 n 个叶子结点看做 n 棵树（仅有一个结点的二叉树），把它们看做一个森林。

②在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有 n-1 棵树。

③重复第②步直到森林中只有一棵为止。

---