问题
单项选择题
对于给出的一组权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