求这个题的答案.对于给出的一组权w={10,12,16,21,30},通过哈夫曼算法求出的扩充二叉树的带权外部路径长度是多少?\x14\x08\x14\x08\x14\x08谢谢求解啊

Question

求这个题的答案.
对于给出的一组权w={10,12,16,21,30},通过哈夫曼算法求出的扩充二叉树的带权外部路径长度是多少?\x14\x08\x14\x08\x14\x08谢谢求解啊

Answer 1

数据结构的概念有些不一致,先说一下我这里的扩充二叉树：设一个权值集合为{w0,.,wn},若T是一个有n个叶节点的二叉树,且n个叶节点的权值分别为w0,.wn,则称T是权值为w0,.wn的扩充二叉树.
霍夫曼算法使用贪心法,先对数据按权值排序：
10 12 16 21 30 选取最小的两个得 10+12=22
16 21 22 30 同上,得 16+21=37
22 30 37 同上,得 22+30=52
37 52 同上,得 37+52=89
画出该二叉树知,其带权路径长为：10×3 + 12×3 + 16×2 + 21×2 +30×2 = 200
故结果为200