对于给出的一组权W={9、13、16、20、30},通过霍夫曼算法求出的扩充二叉树的带权外部路径长

参考答案:

D霍夫曼给出了求具有最小带权外部路径长度的扩充二叉树的方法：首先找出两个最小的W值，设为W1和W2，然后对m-1个权Wl+W2，W3，W4，…，Wn来求解这个问题， 如此进行下去直到所有的W都成为外部结点的权。 根据条件可以构造以下的霍夫曼树： 因此该树的带权路径长度为L=30﹡2+(9+13)+ ﹡3+(16+20) ﹡2=198