对于给出的一组权W={2,3,4,7,8,9},通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为【】。

Question

对于给出的一组权W={2，3，4，7，8，9}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为【 】。

Answer 1

正确答案：80
80 解析：用霍夫曼算法求具有最小带权外部路径长度的扩充二叉树的办法是：首先找出两个最小的wi值，不妨设为w1和w2，然后对m-1个权w1+w2，w3，…，wm来求解这个问题，并且将这个解中的结点用权值代替，如此进行下去，直到所有的w都成为外部结点的权。根据条件构造哈夫曼树如下：树的带权路径长度为WPL=7×2+8×2+4×3+2×4+3×4+9×2=80。