数据结构赫夫曼树带权路径长度详细求发

赫夫曼树是一种用于编码的数据结构，其带权路径长度（WPL）是指树中所有叶子节点的权值乘上其到根节点的路径长度之和。求赫夫曼树的带权路径长度需要以下步骤：

1. 给定n个权值，将它们看作n棵只有一个节点的树。
2. 在森林中选择两棵根节点权值最小的树合并成一棵新树，新树的根节点权值为这两棵树根节点权值之和。
3. 把新树加入到森林中。
4. 重复步骤2和3，直到森林中只剩下一棵树，即为赫夫曼树。
5. 计算赫夫曼树的带权路径长度，即为树中所有叶子节点的权值乘上其到根节点的路径长度之和。

下面以一个示例进行详细说明：

假设有以下5个权值：{5, 6, 7, 8, 9}

1. 将它们看作5棵只有一个节点的树，如下所示：

 | 5 |
 -----
  / \
 /   \
/     \

 | 6 |
 -----
  / \
 /   \
/     \

 | 7 |
 -----
  / \
 /   \
/     \

 | 8 |
 -----
  / \
 /   \
/     \

 | 9 |
 -----
  / \
 /   \
/     \

2. 选择两棵根节点权值最小的树合并成一棵新树，新树的根节点权值为这两棵树根节点权值之和。首先选择5和6合并，得到新树11，如下所示：

   11
 -----
  /   \
 /     \
5       6

再选择7和8合并，得到新树15，如下所示：

   11        15
 -----      -----
  /   \     /   \
 /     \   /     \
5       6 7       8

接着选择11和15合并，得到新树26，如下所示：

       26
     -------
    /     \
   /       \
  11        15
 -----      -----
  /   \     /   \
 /     \   /     \
5       6 7       8

3. 把新树加入到森林中。此时森林中只剩下一棵树，即为赫夫曼树，如下所示：

       26
     -------
    /     \
   /       \
  11        15
 -----      -----
  /   \        |
 /     \       |
5       6      |
             -----
              /   \
             /     \
            7       8

4. 计算赫夫曼树的带权路径长度，即为树中所有叶子节点的权值乘上其到根节点的路径长度之和。如下所示：

5 * 3 + 6 * 3 + 7 * 2 + 8 * 2 + 9 * 3 = 99

因此，赫夫曼树的带权路径长度为99。