请画出叶子结点的权值集合为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。

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

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

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

第一步：将叶子结点按权值从小到大排序，得到：
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，W4和W6的父节点

第四步：取出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=14，并将其加入到叶子结点集合中，得到：
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的父节点的父节点的父节点

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

           41
        /      \
      16       25
     /  \     /   \
    6    10  13   12
   / \   / \
  3   2 5   8

带权路径长度为：3×3 + 9×2 + 8×2 + 5×2 + 2×3 + 学号后两位×4 = 72 + 学号后两位×4。