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

Question

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

Answer 1

正确答案：
37
按照霍夫曼树构造的方法构造一棵带权的扩充二叉树，此扩充二叉树的带权外部路径长度为9×1+5×2+(2+4)×3=37。