对于给出的一组权w={10，12，16，21，30}，通过霍夫曼算法求出的扩充--X树的带权外部的路径长度为

admin2013-02-03 39

问题对于给出的一组权w={10，12，16，21，30}，通过霍夫曼算法求出的扩充--X树的带权外部的路径长度为

选项 A、89
B、189
C、200
D、300

答案4

解析霍夫曼算法给出了求扩充二叉树的具有最小带权外部路径的方法：首先找出两个最小的wi值，不妨设为w1、w2，然后对m-1个权(w1+w2，w3...．)来求解这个问题，并且将这个解中的结点(w1+w2)用图4所示来代替，如此下去，直到所有的w都成为外部结点。对本题中的w={10、12、16、21、30}，我们不妨写出其序列：