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

Question

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

Answer 1

哈夫曼树见图.用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)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树