问题
填空题
对于给出的一组权W={2,3,4,7,8,9},通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为 【4】 。
答案
参考答案: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。