请以（1，3，4，7，9，11）为权值，构造一颗哈夫曼树。并计算带权路径长度WPL

哈夫曼树的构造是通过贪心算法，选择合适的两个权值较小的节点合并成一个新的节点（新节点的权值等于这两个节点权值的和），直到最后形成一棵树。下面我们一步一步构造给定权值（1，3，4，7，9，11）的哈夫曼树，并计算带权路径长度（WPL）。 **步骤 1：创建初始节点** - 创建节点1: `1` - 创建节点2: `3` - 创建节点3: `4` - 创建节点4: `7` - 创建节点5: `9` - 创建节点6: `11` **步骤 2：将节点按照权值从小到大排序并合并构建哈夫曼树** 1. 选择权值最小的两个节点 `1` 和 `3` 合并，新节点权值为 `4`。 节点列表：[4, 4, 7, 9, 11] 2. 再次选择权值最小的两个节点 `4`（上一步合成的）和 `4` 合并，新节点权值为 `8`。 节点列表：[8, 7, 9, 11] 3. 选择权值最小的两个节点 `7` 和 `8` 合并，新节点权值为 `15`。 节点列表：[15, 9, 11] 4. 继续选择权值最小的两个节点 `9` 和 `11` 合并，新节点权值为 `20`。 节点列表：[15, 20] 5. 最后选择剩余的两个节点 `15` 和 `20` 合并，得到最终的根节点，权值为 `35`。 完成树：根节点权值为 `35` **步骤 3：构建哈夫曼编码表并计算WPL** 根据上述合并顺序构建哈夫曼编码表： - `11` 和 `9`： - `9：0` - `11：1` - `7` 和 上面的结果： - `9` 的编码为 `00` - `11` 的编码为 `01` - `7` 的编码为 `10` - `4` 和 `4`（合并1和3的新节点8）： - `4`（含1）：编码为 `110` - `4`（含3）：编码为 `111` - `15` （7和上面的结果）和上面合成的 `8`（节点4）： - `7` 和 `9` 和 `11` 的总编码为 `0` - `4` 和 `1` 和 `3` 的总编码为 `1` - 最终的根节点合并 `15` 和 `20`： - `左子树（0）`：包含前面所有的 - `右子树（1）`：另一个分支 **计算WPL：** - `1`：路径长度`3`（编码`110`) - `3`：路径长度`3`（编码`111`) - `4`：路径长度`3`（编码`110`或`111`） - `7`：路径长度`2`（编码`10`） - `9`：路径长度`3`（编码`00`) - `11`：路径长度`3`（编码`01`） \[ WPL = 1\times3 + 3\times3 + 4\times3 + 7\times2 + 9\times3 + 11\times3 = 3 + 9 + 12 + 14 + 27 + 33 = 94 \] 因此，根据上述步骤和方法，哈夫曼树的带权路径长度WPL为94。