哈夫曼树带权长度wpl_哈夫曼树的构造_哈夫曼树带权路径长度

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

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

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

哈夫曼树的构造

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

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

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

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

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

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26962-1.html