问题 单项选择题

对于给出的一组权w={10,12,16,21,30},通过霍夫曼算法求出的扩充--X树的带权外部的路径长度为

A.89

B.189

C.200

D.300

答案

参考答案:C

解析:
霍夫曼算法给出了求扩充二叉树的具有最小带权外部路径的方法:首先找出两个最小的wi值,不妨设为w1、w2,然后对m-1个权(w1+w2,w3....)来求解这个问题,并且将这个解中的结点(w1+w2)用图4所示来代替,如此下去,直到所有的w都成为外部结点。

对本题中的w={10、12、16、21、30},我们不妨写出其序列:
10 12 16 21 30
16 21 30 22
30 22 37
37 52
89
因此其扩展二叉树参见图5。

我们奇以计算出扩充二叉树的具有最小带权外部路径长度为:
10*3+12*3+16*2+21*2+30*2=200

单项选择题
单项选择题