构造一棵带权1，3，3，4，6，9，10的最优二元树

最优二元树也称为哈夫曼树，它的构造过程如下：

1. 将所有节点按权值从小到大排序，得到序列：1，3，3，4，6，9，10。

2. 选取权值最小的两个节点1和3，构造一棵二元树，令1为左子树，3为右子树，该二元树的根节点权值为4。

3. 将序列中的1和3删除，将4插入序列中。

4. 选取权值最小的两个节点3和4，构造一棵二元树，令3为左子树，4为右子树，该二元树的根节点权值为7。

5. 将序列中的3和4删除，将7插入序列中。

6. 重复上述步骤，直到序列中只剩下一个节点，即得到最优二元树。

最终得到的最优二元树如下图所示：

       36
      /  \
     /    \
    14     22
   / \     / \
  6   8   9  13
     / \
    3   5

其中，每个节点的权值为上述序列中对应数字的和。

相关问题

构造一棵带权1，3，3，4，6，9，10的最优二元树，并指出该二元树的树高h（T）和树权W（T）

构造最优二元树的步骤如下：

1. 将结点按照权值从小到大排序，得到：1，3，3，4，6，9，10。
2. 从中选取权值最小的两个结点作为一对兄弟结点，并将它们合并成一个新的结点，权值为两个结点的权值之和。在本例中，选取1和3作为一对兄弟结点，合并成一个新的结点，权值为4。
3. 将新的结点插入原来的结点中，保持权值从小到大的顺序。得到：3，4，3，6，9，10，4。
4. 重复步骤2和3，直到只剩下一个结点为止。在本例中，得到的最优二元树如下图所示：

      40
     /  \
    16  24
   / \   / \
  6  10  9  15
     / \
    3   3

该二元树的树高为h(T)=3，树权为W(T)=40。

构造一棵带权1，3，3，4，6，9，10的最优二元树(图中必需有正确标注)，并指出该二元树的树高h（T）和树权W（T）。

我们可以使用Huffman算法构造最优二元树。

首先将所有节点按照权值从小到大排序，得到节点序列：1, 3, 3, 4, 6, 9, 10。

然后取出权值最小的两个节点1和3，构造一棵二元树，其中1作为左子树，3作为右子树，其根节点的权值为4。得到节点序列：4, 3, 4, 6, 9, 10。

接着取出权值最小的两个节点3和4，构造一棵二元树，其中3作为左子树，4作为右子树，其根节点的权值为7。得到节点序列：7, 4, 6, 9, 10。

再取出权值最小的两个节点4和6，构造一棵二元树，其中4作为左子树，6作为右子树，其根节点的权值为10。得到节点序列：10, 7, 9, 10。

继续取出权值最小的两个节点7和9，构造一棵二元树，其中7作为左子树，9作为右子树，其根节点的权值为16。得到节点序列：16, 10, 10。

最后取出剩下的两个节点10和16，构造一棵二元树，其中10作为左子树，16作为右子树，其根节点的权值为26。

得到最终的最优二元树如下图所示：

       26
      /  \
     /    \
    10    16
   /  \
  4    6
 / \
1   3
   / \
  3   4

树高 $h(T)$ 为 4，树权 $W(T)$ 为 49。