权值为123456789构造哈夫曼树

根据提供的引用内容，构造哈夫曼树的步骤如下：

1. 根据给定的权值，构造n棵只有根结点的二叉树，这n棵二叉树构成一个森林F。
2. 在森林中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且新置的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
3. 在森林F中删除这两棵树，同时将新得到的二叉树加入F中。
4. 重复步骤2和3，直到F中只含一棵树为止。这棵树就是哈夫曼树。

根据给定的权值123456789，我们可以按照上述步骤构造哈夫曼树。首先，我们将每个权值作为一个独立的树，构成森林F。然后，我们选择权值最小的两棵树（1和2）作为左右子树构造一棵新的二叉树，根结点的权值为左右子树根结点的权值之和（1+2=3）。接下来，我们删除这两棵树，并将新得到的二叉树加入F中。重复这个过程，直到F中只含一棵树为止。

构造哈夫曼树的过程如下：
1. 构造森林F：根据给定的权值，构造9棵只有根结点的二叉树，分别为1, 2, 3, 4, 5, 6, 7, 8, 9。
2. 选择权值最小的两棵树：选择1和2作为左右子树构造一棵新的二叉树，根结点的权值为1+2=3。
3. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有8棵树：3, 3, 4, 5, 6, 7, 8, 9。
4. 选择权值最小的两棵树：选择3和3作为左右子树构造一棵新的二叉树，根结点的权值为3+3=6。
5. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有7棵树：4, 5, 6, 6, 7, 8, 9。
6. 选择权值最小的两棵树：选择4和5作为左右子树构造一棵新的二叉树，根结点的权值为4+5=9。
7. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有6棵树：6, 6, 7, 8, 9,9。
8. 选择权值最小的两棵树：选择6和6作为左右子树构造一棵新的二叉树，根结点的权值为6+6=12。
9. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有5棵树：7, 8, 9, 9, 12。
10. 选择权值最小的两棵树：选择7和8作为左右子树构造一棵新的二叉树，根结点的权值为7+8=15。
11. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有4棵树：9, 9, 12, 15。
12. 选择权值最小的两棵树：选择9和9作为左右子树构造一棵新的二叉树，根结点的权值为9+9=18。
13. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有3棵树：12, 15, 18。
14. 选择权值最小的两棵树：选择12和15作为左右子树构造一棵新的二叉树，根结点的权值为12+15=27。
15. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有2棵树：18, 27。
16. 选择权值最小的两棵树：选择18和27作为左右子树构造一棵新的二叉树，根结点的权值为18+27=45。
17. 删除选择的两棵树，并将新得到的二叉树加入F中，此时F中含有1棵树：45。

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

   45
  /  \
18    27
    /    \
   12    15
       /    \
      9     9