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

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

哈夫曼树见图。用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 棵树。

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


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/yw/12600677.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-05-26
下一篇 2023-05-26

发表评论

登录后才能评论

评论列表(0条)

保存