由权值为{3, 17, 2, 7, 11}的叶子结点构造的哈夫曼(Huffman)树,其带权路径长度为
时间: 2024-03-16 15:45:55 浏览: 112
根据结点值和权重建立哈夫曼树哈夫曼代码
4星 · 用户满意度95%
构造哈夫曼树的过程是:首先将叶子结点按照权值从小到大排序,然后每次选取权值最小的两个结点合并成一个新的结点,其权值为这两个结点的权值之和,重复此过程直至所有结点都合并成一个根节点。在这个过程中,每个结点的深度为其到根节点的路径长度,而带权路径长度就是每个叶子结点的权值乘以其深度的和。对于权值为{3, 17, 2, 7, 11}的叶子结点构造的哈夫曼树,其构造过程如下:
1. 将叶子结点按照权值从小到大排序,得到{2, 3, 7, 11, 17};
2. 选取权值最小的两个结点2和3,合并成一个新的结点5,其深度为1,权值为5;
3. 将新的结点5插入排序后的序列中,得到{5, 7, 11, 17};
4. 选取权值最小的两个结点5和7,合并成一个新的结点12,其深度为2,权值为12;
5. 将新的结点12插入排序后的序列中,得到{11, 12, 17};
6. 选取权值最小的两个结点11和12,合并成一个新的结点23,其深度为3,权值为23;
7. 将新的结点23插入排序后的序列中,得到{17, 23};
8. 选取权值最小的两个结点17和23,合并成一个新的根节点40,其深度为4,权值为40。
最终得到的哈夫曼树如下所示:
```
40
/ \
17 23
/ \
5 12
/ \
2 7
```
叶子结点的带权路径长度分别为:2×3 + 3×2 + 7×2 + 11×3 + 17×2 = 94,因此,权值为{3, 17, 2, 7, 11}的叶子结点构造的哈夫曼树的带权路径长度为94。
阅读全文