以权值集合{2，5，7，9，13}构造一棵哈夫曼树，给出相应的哈夫曼编码，并计算其带权路径长度。

以下是以权值集合{2，5，7，9，13}构造哈夫曼树的过程：
1.将权值从小到大排序，得到{2，5，7，9，13}。
2.取出权值最小的两个节点2和5，构造一棵二叉树，根节点的权值为2+5=7，左子节点为权值为2的节点，右子节点为权值为5的节点。
3.将构造出的二叉树插入到原来的权值集合中，得到{7，7，9，13}。
4.重复步骤2和3，直到只剩下一个节点，即为哈夫曼树的根节点。
5.得到的哈夫曼树如下所示，其中数字表示节点的权值。

        43
       /  \
      /    \
     20    23
    /  \     
   /    \    
  9     11   
 / \   / \  
2   7 5   6  

6.根据哈夫曼树的定义，从根节点到每个叶子节点的路径上的分支组成的0和1的序列即为该节点对应字符的哈夫曼编码。因此，节点2的哈夫曼编码为1000，节点5的哈夫曼编码为1001，节点7的哈夫曼编码为101，节点9的哈夫曼编码为00，节点11的哈夫曼编码为01，节点13的哈夫曼编码为11。
7.计算带权路径长度，即每个叶子节点的权值乘以其到根节点的路径长度之和。节点2的带权路径长度为2*4=8，节点5的带权路径长度为5*4=20，节点7的带权路径长度为7*3=21，节点9的带权路径长度为9*2=18，节点11的带权路径长度为11*2=22，节点13的带权路径长度为13*2=26。因此，哈夫曼树的带权路径长度为8+20+21+18+22+26=115。

相关问题

题目要求构造一个哈夫曼树，以权值集合{2,5,7,9,13}为基础，给出相应的哈夫曼编码

首先，我们需要根据权值集合构造哈夫曼树。哈夫曼树的构造过程如下：

1. 将权值集合中的每个权值看作一个节点，并按照权值大小从小到大排序。

2. 选取权值最小的两个节点，将它们合并为一个新的节点，新节点的权值为这两个节点的权值之和。将新节点插入到排序后的节点集合中，同时从节点集合中删除被合并的两个节点。

3. 重复步骤2，直到集合中只剩下一个节点，即为哈夫曼树的根节点。

按照上述步骤，我们可以得到如下哈夫曼树：

        36
      /    \
     /      \
    16      20
   /  \    /  \
  7    9  13   7
 / \       
2   5      

哈夫曼编码的计算方法如下：

1. 对于哈夫曼树中的每个叶子节点，从它的父节点开始向上遍历，如果经过的边是从左子树出发的，则编码为0，如果是从右子树出发的，则编码为1。将每个叶子节点的编码记录在一个表格中。

2. 对于给定的字符或符号，查表格得到其对应的哈夫曼编码。

按照上述方法，我们可以得到如下哈夫曼编码：

权值    编码
 2     1111
 5     1110
 7     110
 9     10
13     0

其中，每个叶子节点的编码表示为从根节点到该节点路径上的边的方向（0为左，1为右）拼接而成的二进制字符串。

设给定一个权值集合 W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的 带权路径长度 WPL。

哈夫曼树的构造过程如下：

1. 将所有权值按照从小到大的顺序排列，得到：(3，5，7，9，11)。
2. 取出权值最小的两个节点3和5，将它们合并成一个新节点，权值为8。此时得到的节点集合为(7，8，9，11)。
3. 取出权值最小的两个节点7和8，将它们合并成一个新节点，权值为15。此时得到的节点集合为(9，11，15)。
4. 取出权值最小的两个节点9和11，将它们合并成一个新节点，权值为20。此时得到的节点集合为(15，20)。
5. 最后将权值为15和20的节点合并成一个根节点，得到哈夫曼树。

哈夫曼树如下图所示：

      35
     /  \
    15  20
   /  \     
  7    8
 / \
3   5

根据哈夫曼树的定义，每个叶子节点都对应一个权值，而每个非叶子节点都对应一个权值之和。因此，我们可以通过遍历哈夫曼树来计算带权路径长度WPL。

在上面的哈夫曼树中，有5个叶子节点，分别对应权值3，5，7，9，11。它们的深度分别为2，2，1，1，1。因此，带权路径长度WPL为：

WPL = 2*3 + 2*5 + 1*7 + 1*9 + 1*11 = 6 + 10 + 7 + 9 + 11 = 43

因此，构造出的哈夫曼树的带权路径长度WPL为43。