由权值为{3,17,2,7,11}的叶子结点构造的哈夫曼(Huffman)树,其带权路径长度为
时间: 2024-03-16 20:46:34 浏览: 56
霍夫曼树带权路径长度求值.cpp
构造哈夫曼树的步骤是:
1. 将给定的权值序列从小到大排序,得到{2,3,7,11,17}。
2. 取出权值最小的两个节点,构造一个新节点,权值为这两个节点的权值之和。
3. 将新节点加入权值序列中,删除原有的两个节点。
4. 重复2和3的步骤,直到只剩下一个节点,这个节点就是哈夫曼树的根节点。
根据上述步骤,可以按以下方式构造哈夫曼树:
1. 取出2和3,构造新节点,权值为5,得到{5,7,11,17}。
2. 取出5和7,构造新节点,权值为12,得到{11,12,17}。
3. 取出11和12,构造新节点,权值为23,得到{17,23}。
4. 取出17和23,构造新节点,权值为40,得到{40}。
最终得到的哈夫曼树如下所示:
```
40
/ \
17 23
/ \
11 12
/ \
2 5
```
其中,叶子节点的权值乘以其到根节点的距离,再将所有叶子节点的结果相加,就是这棵哈夫曼树的带权路径长度。计算得到:
3*3 + 17*2 + 2*4 + 7*3 + 11*3 = 3 + 34 + 8 + 21 + 33 = 99
因此,这棵哈夫曼树的带权路径长度为99。
阅读全文