用权值{3, 2, 4, 5, 1}构造的哈夫曼树带权路径长度计算

本文将详细介绍如何用权值{3, 2, 4, 5, 1}构造哈夫曼树，并计算其带权路径长度。

首先，我们需要找到两个权值最小的节点，将它们合并为一个新的节点，权值为它们的和。重复这个步骤，直到只剩下一个节点为根节点的哈夫曼树。

以下是构造哈夫曼树的过程：

1. 合并权值为1和2的节点，得到新节点（权值为1+2=3）。 新节点的左子节点是权值为1的节点，右子节点是权值为2的节点。

2. 合并权值为3的节点和权值为3的节点，得到新节点（权值为3+3=6）。 新节点的左子节点是权值为3的节点，右子节点是权值为3的节点。

3. 合并权值为4的节点和权值为5的节点，得到新节点（权值为4+5=9）。 新节点的左子节点是权值为4的节点，右子节点是权值为5的节点。

4. 合并权值为6的节点和权值为9的节点，得到根节点（权值为6+9=15）。 根节点的左子节点是权值为6的节点，右子节点是权值为9的节点。

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

    15
  /    \
6       9

/ \ /
3 3 4 5 /
1 2

接下来，我们计算带权路径长度（WPL，Weighted Path Length），即每个叶子节点的权值乘以从根节点到该叶子节点的路径长度的总和。

根据上述哈夫曼树，计算带权路径长度的公式如下：

WPL = (32) + (32) + (42) + (52) + (6*2) = 6 + 6 + 8 + 10 + 12 = 42

所以，使用权值{3, 2, 4, 5, 1} 构造的哈夫曼树的带权路径长度是 42。