请以（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。