对于给出的一组权W={9 13 16 20 30} 通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为()。A
求出,算法,路径
已帮助 人
对于给出的一组权W={9、13、16、20、30},通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为()。
A)88
B)188
C)98
D)198
-
参考答案:D霍夫曼给出了求具有最小带权外部路径长度的扩充二叉树的方法:首先找出两个最小的W值,设为W1和W2,然后对m-1个权W1+W2,W3,W4,…,Wn来求解这个问题,如此进行下去直到所有的W都成为外部结点的权。根据条件可以构造以下的霍夫曼树:因此该树的带权路径长度为L=30*2+(9+131*3+(16+20)*2=198
