以(3，7，11，8，9，12)为叶子结点的权重，构造一棵哈夫曼二叉树，构造树的高度是多少

首先将叶子结点按照权重从小到大排序，得到：

(3，7，8，9，11，12)

接下来，每次取权重最小的两个叶子结点，合并成一个新的节点，其权重为两个叶子结点权重之和，直到最后合并成一棵树。具体过程如下：

1. 取3和7，合并成新节点，权重为10，得到(10，8，9，11，12)
2. 取8和9，合并成新节点，权重为17，得到(10，17，11，12)
3. 取10和11，合并成新节点，权重为21，得到(21，17，12)
4. 取12和17，合并成新节点，权重为29，得到(21，29)
5. 最后合并成一棵树，如下所示：

50
/ \
21 29
/ \
3 7

构造出的树的高度为2，即根节点到叶子结点的最长路径为2。

相关问题

以(3，7，11，8，9，12)为叶子结点的权重，构造一棵哈夫曼二叉树，构造树的高

度为3。

构造过程如下：

1. 将叶子结点按权重从小到大排序：(3，7，8，9，11，12)

2. 取出权重最小的两个结点3和7，合并成一个新的结点，权重为3+7=10，成为新的根节点，左子节点为权重为3的结点，右子节点为权重为7的结点。

3. 将新的结点10插入到原来的序列中，得到(8，9，10，11，12)。

4. 重复2、3步骤，取出权重最小的两个结点8和9，合并成一个新的结点，权重为8+9=17，成为新的根节点，左子节点为权重为8的结点，右子节点为权重为9的结点。

5. 将新的结点17插入到原来的序列中，得到(10，11，12，17)。

6. 重复2、3步骤，取出权重最小的两个结点10和11，合并成一个新的结点，权重为10+11=21，成为新的根节点，左子节点为权重为10的结点，右子节点为权重为11的结点。

7. 将新的结点21插入到原来的序列中，得到(12，17，21)。

8. 重复2、3步骤，取出权重最小的两个结点12和17，合并成一个新的结点，权重为12+17=29，成为新的根节点，左子节点为权重为12的结点，右子节点为权重为17的结点。

9. 最后得到一棵哈夫曼二叉树，根节点的权重为29，树的高度为3。

构造出的哈夫曼二叉树如下图所示：

    29
   /  \
  12  17
 /    / \
3   8   9 11
         \
         12

以(3，7，11，8，9，12)为叶子结点的权重，构造一棵哈夫曼二叉树，构造树的高的是？

首先，将叶子节点按照权重从小到大排序，得到：(3，7，8，9，11，12)

然后，每次选择权重最小的两个节点进行合并，直到只剩下一个节点，即为根节点。具体步骤如下：

1. 将3和7合并，得到一个新节点，权重为10。
10
/ \
3 7

2. 将8和9合并，得到一个新节点，权重为17。
10 17
/ \ / \
3 7 8 9

3. 将10和11合并，得到一个新节点，权重为21。
17 21
/ \ / \
8 9 10 11
/ \
3 7

4. 将17和21合并，得到一个新节点，权重为38。
21
/ \
17 21
/ \ / \
8 9 10 11
/ \
3 7

因此，构造出的哈夫曼二叉树的高度为3。