设关键字的输入序列为：{53,40,45,20,14,78,95，54,51,98,52}，构造一棵平衡二叉树。

首先将输入序列排序，得到{14, 20, 40, 45, 51, 52, 53, 54, 78, 95, 98}。然后以中间的数51作为根节点，左侧的数作为左子树，右侧的数作为右子树。左子树的中间数40作为左子树的根节点，左侧的数作为左子树，右侧的数作为右子树。右子树的中间数95作为右子树的根节点，左侧的数作为左子树，右侧的数作为右子树。以此类推，最终得到的平衡二叉树如下所示：

          51
        /    \
      40      95  
     /  \    /   \
   20   45  78   98
  /  \        \
14   52       54
          	

相关问题

假定关键字输入序列为19，21，47，32，8，23，41，45，40，画出建立二叉平衡树的过程。

首先，我们需要选择一个根节点。由于输入序列中没有明显的中位数，我们可以选择第一个节点 19 作为根节点。

接下来，我们将输入序列分为两个部分，小于根节点的部分和大于根节点的部分。小于根节点的部分为 8，而大于根节点的部分为 21，47，32，23，41，45，40。

我们将小于根节点的部分作为左子树，大于根节点的部分作为右子树。左子树只有一个节点 8，因此它是平衡的。右子树的中位数为 41，因此我们选择它作为右子树的根节点。

现在，我们将右子树分为两个部分，小于右子树根节点的部分和大于右子树根节点的部分。小于右子树根节点的部分为 21，32，23，40，而大于右子树根节点的部分为 47，41，45。

我们将小于右子树根节点的部分作为右子树的左子树，大于右子树根节点的部分作为右子树的右子树。右子树的左子树的中位数为 23，因此我们选择它作为右子树的左子树的根节点。右子树的右子树的中位数为 45，因此我们选择它作为右子树的右子树的根节点。

最终的二叉平衡树如下所示：

        19
       /  \
      8    41
          /  \
         32   45
        /  \    \
       21  23   47
            \
            40

所给定的待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，采用堆排序的方法，每趟排序结束后关键字序列的状态：

所给定的待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，请分别写出使用以下排序方法，每趟排序结束后关键字序列的状态：

1. 冒泡排序法
第一趟排序后序列：2，12，16，28，10，16*，20，6，18，30
第二趟排序后序列：2，12，16，10，16*，20，6，18，28，30
第三趟排序后序列：2，12，10，16*，20，6，16，18，28，30
第四趟排序后序列：2，10，12，16*，6，16，18，20，28，30
第五趟排序后序列：2，10，12，6，16*，16，18，20，28，30
第六趟排序后序列：2，10，6，12，16，16*，18，20，28，30
第七趟排序后序列：2，6，10，12，16，18，16*，20，28，30
第八趟排序后序列：2，6，10，12，16，16*，18，20，28，30
第九趟排序后序列：2，6，10，12，16，16*，18，20，28，30

2. 插入排序法
第一趟排序后序列：2，12，16，30，28，10，16*，20，6，18
第二趟排序后序列：2，12，16，30，28，10，16*，20，6，18
第三趟排序后序列：2，12，16，28，30，10，16*，20，6，18
第四趟排序后序列：2，10，12，16，28，30，16*，20，6，18
第五趟排序后序列：2，10，12，16，16*，28，30，20，6，18
第六趟排序后序列：2，6，10，12，16，16*，20，28，30，18
第七趟排序后序列：2，6，10，12，16，16*，18，20，28，30

3. 选择排序法
第一趟排序后序列：2，12，16，30，28，10，16*，20，6，18
第二趟排序后序列：2，6，16，30，28，10，16*，20，12，18
第三趟排序后序列：2，6，10，30，28，16*，16，20，12，18
第四趟排序后序列：2，6，10，12，28，16*，16，20，30，18
第五趟排序后序列：2，6，10，12，16*，28，16，20，30，18
第六趟排序后序列：2，6，10，12，16*，16，28，20，30，18
第七趟排序后序列：2，6，10，12，16*，16，18，20，30，28

4. 希尔排序法
第一趟排序后序列：10，2，16*，6，12，16，18，30，28，20
第二趟排序后序列：2，10，6，12，16，16*，18，20，28，30
第三趟排序后序列：2，6，10，12，16，16*，18，20，28，30

5. 快速排序法
第一趟排序后序列：10，2，6，12，16，16*，18，30，28，20
第二趟排序后序列：2，6，10，12，16，16*，18，20，28，30

6. 归并排序法
第一趟排序后序列：2，10，16*，6，12，16，18，30，28，20
第二趟排序后序列：2，6，10，12，16，16*，18，20，28，30