给定8片树叶,其权值分别是2,3,5,7,9,11,13,17,请用Huffman算法构造最优二叉树并计算其权值。
时间: 2024-03-25 20:37:10 浏览: 13
好的,根据Huffman算法,我们可以先将这8片树叶按照权值从小到大进行排序,得到:
2,3,5,7,9,11,13,17
然后我们将权值最小的两个树叶取出来,合并成一棵树,其权值为2+3=5。得到新的序列:
5,5,7,9,11,13,17
继续取权值最小的两个树叶,合并成一棵树,其权值为5+5=10。得到新的序列:
7,9,10,11,13,17
继续取权值最小的两个树叶,合并成一棵树,其权值为7+9=16。得到新的序列:
10,11,13,16,17
继续取权值最小的两个树叶,合并成一棵树,其权值为10+11=21。得到新的序列:
13,16,17,21
继续取权值最小的两个树叶,合并成一棵树,其权值为13+16=29。得到新的序列:
17,21,29
最后取权值最小的两个树叶,合并成一棵树,其权值为17+21=38。这棵树就是最优二叉树,其权值为38。
构造的最优二叉树如下图所示:
```
38
/ \
17 21
/ \
9 12
/ \
5 7
/ \ / \
2 3 5 2
```
其中左子树的叶子节点代表的原始权值为2、3、5、7,右子树的叶子节点代表的原始权值为9、11、13、17。