对于一组给定的叶子结点，它们的权值集合为W=｛3，5，9，11，12，13｝，给出此集合构造的霍夫曼树

首先，霍夫曼树是一种带权路径长度最短的树，构造霍夫曼树的基本步骤如下：

1. 将所有的叶子结点按照其权值大小从小到大排列。
2. 选取两个权值最小的叶子结点，构造一个新的二叉树，其根节点的权值为这两个叶子结点的权值之和。
3. 将上一步中选择的两个叶子结点从叶子结点集合中删除，并将新的二叉树加入到叶子结点集合中。
4. 重复步骤2-3，直到最后只剩下一个根节点为根的二叉树，这个二叉树就是霍夫曼树。

根据上述步骤，我们可以构造出如下的霍夫曼树：


其中，每个节点的数值表示该节点的权值。左边的数字表示叶子节点的权值，右边的数字表示非叶子节点的权值。

相关问题

请画出叶子结点的权值集合为w＝｛5，2，9，11，8，3，7｝的哈夫曼树构造过程

首先，将权值集合按从小到大的顺序进行排序，得到w'={2,3,5,7,8,9,11}。

然后，取出权值最小的两个节点2和3，构造一个新节点，权值为它们的和，即5。将原来的2和3节点作为新节点的左右子节点。

接着，取出权值最小的两个节点5和7，构造一个新节点，权值为它们的和，即12。将原来的5和7节点作为新节点的左右子节点。

继续，取出权值最小的两个节点8和9，构造一个新节点，权值为它们的和，即17。将原来的8和9节点作为新节点的左右子节点。

接下来，将之前构造的节点12和11进行合并，构造一个新节点，权值为它们的和，即23。将原来的12和11节点作为新节点的左右子节点。

最后，将之前构造的节点23和17进行合并，构造一个新节点，权值为它们的和，即40。将原来的23和17节点作为新节点的左右子节点。

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

       40
      /   \
     /     \
    23     17
   /  \
  12  11
 / \
5   7
 / \
2   3

1. 已知二叉树的叶子结点的权值集合为W={3，9，8，5，2，34}，请画出其哈夫曼树，并计算其带权路径长度。

好的，根据哈夫曼树的构建规则，我们先将叶子结点按权值从小到大排序，然后取出权值最小的两个叶子结点，构建出一个新的父节点，其权值为这两个叶子结点的权值之和。再将这个父节点加入到叶子结点集合中，重复以上步骤，直到所有叶子节点都被合并成为一个根节点，构成一棵哈夫曼树。

为了方便表示，我用W1，W2，W3，W4，W5，W6分别代表权值为3，9，8，5，2，34的叶子结点。

第一步：将叶子结点按权值从小到大排序，得到：
W5，W1，W6，W4，W3，W2

第二步：取出W2和W3，构建出一个新的父节点W2+3=5，并将其加入到叶子结点集合中，得到：
W5，W1，W6，W4，W2+3，W3

第三步：取出W5和W1，构建出一个新的父节点W5+1=6，并将其加入到叶子结点集合中，得到：
W6，W4，W2+3，W3，W6，W5+1

第四步：取出W6和W4，构建出一个新的父节点W6+4=10，并将其加入到叶子结点集合中，得到：
W2+3，W3，W5+1，W2+3和W3的父节点，W6+4，W5+1和W2+3和W3的父节点的父节点

第五步：取出W2+3和W3，构建出一个新的父节点W2+3+3=8，并将其加入到叶子结点集合中，得到：
W5+1，W6+4，W5+1和W2+3和W3的父节点，W6+4和W5+1和W2+3和W3的父节点的父节点，W2+3+3和W6+4的父节点

第六步：取出W5+1和W2+3和W3的父节点，构建出一个新的父节点W5+1+5+8=18，并将其加入到叶子结点集合中，得到：
W6+4，W6+4和W5+1和W2+3和W3的父节点的父节点，W2+3+3和W6+4的父节点，W5+1+5+8和W6+4和W5+1和W2+3和W3的父节点的父节点的父节点

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

               47
           /        \
         18         29
       /    \      /   \
     6      12   13    16
    / \    /   \
   3   2  5     8

带权路径长度为：3×3 + 9×2 + 8×2 + 5×2 + 2×3 + 34×2 = 120。