设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为7、19、2、6、32、3、21、10,根据这些频率作为权值构造哈夫曼树,则这棵哈夫曼树的高度为________________
时间: 2023-10-20 08:30:47 浏览: 104
哈夫曼树的建立(根据输入的权值,建立一棵哈夫曼树)
构造哈夫曼树的基本思路是:先将权值按照从小到大的顺序排列,然后每次选取权值最小的两个节点进行组合,得到新节点的权值为这两个节点的权值之和,直到最后只剩下一个节点为止。因此,哈夫曼树的高度取决于节点的组合方式,而节点的组合方式又取决于权值的大小关系。
在本题中,如果按照从小到大的顺序排列权值,则得到以下序列:
2,3,6,7,10,19,21,32
接下来按照哈夫曼树的构造方法,每次选取权值最小的两个节点进行组合,得到新节点的权值为这两个节点的权值之和。具体过程如下:
1. 选择2和3进行组合,得到新节点的权值为5。
2. 选择5和6进行组合,得到新节点的权值为11。
3. 选择7和10进行组合,得到新节点的权值为17。
4. 选择17和19进行组合,得到新节点的权值为36。
5. 选择21和32进行组合,得到新节点的权值为53。
6. 选择36和53进行组合,得到新节点的权值为89。
最终得到的哈夫曼树的高度为5。因此,答案为5。
阅读全文