权值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

肯定不唯一：

一个string 的哈夫曼树有多种画法

例如："a fast runner need never be afraid of the dark"

一共46个字符： 按字符出现频率从大到小排列：

可以画成这样：

取a 的代码就是：1101

第二种画法：

a= 10110

还有其它画法   a=010

我翻阅了所有的资料真的还没有发现一种哈夫曼树的唯一画法，画法既然多种，高度肯定不一样，代码肯定也不一样。

---