对给定的一组键值W= {4,2,5,1,8,13,10,12},试构造相应的哈夫曼树，并计算它的带权路径长度WPL

好的，我知道了。根据哈夫曼树的构造方法，我们需要先将这些权值从小到大排序，得到{1,2,4,5,8,10,12,13}。然后，我们每次取出权值最小的两个节点，合并成一个新节点，其权值为这两个节点的权值之和。重复这个过程，直到最后只剩下一个节点，即为哈夫曼树的根节点。

具体的构造过程如下：

1. 将权值排序得到{1,2,4,5,8,10,12,13}
2. 取出1和2，合并成一个新节点，权值为3
3. 取出3和4，合并成一个新节点，权值为7
4. 取出5和7，合并成一个新节点，权值为12
5. 取出8和10，合并成一个新节点，权值为18
6. 取出12和13，合并成一个新节点，权值为25
7. 取出18和25，合并成一个新节点，权值为43

最后得到的哈夫曼树如下：

        43
      /    \
     25    18
    / \    / \
  12  13  8   10
  / \
1   2

计算带权路径长度WPL的公式为：WPL = Σ（每个叶子节点的权值 × 到根节点的路径长度）。

对于这个哈夫曼树，我们可以计算出每个叶子节点的权值和到根节点的路径长度如下：

| 节点 | 权值 | 到根节点的路径长度 | 权值 × 到根节点的路径长度 |
| ---- | ---- | ------------------ | --------------------------- |
| 1 | 1 | 3 | 3 |
| 2 | 2 | 3 | 6 |
| 4 | 4 | 2 | 8 |
| 5 | 5 | 2 | 10 |
| 8 | 8 | 1 | 8 |
| 10 | 10 | 1 | 10 |
| 12 | 12 | 2 | 24 |
| 13 | 13 | 2 | 26 |

将所有叶子节点的权值 × 到根节点的路径长度相加，得到带权路径长度WPL = 85。