二叉排序树的生成与删除节点演示

二叉排序树的生成与删除节点演示

问题描述: 已知一组关键字序列为：(10, 30, 5, 20, 40, 25)，按照依次插入结点的方法生成一棵二叉排序树。

(1) 画出该二叉排序树（不要求画出构造过程）；

(2) 画出从(1)所得树中删除关键字为'30'的结点之后的二叉排序树。

(1) 二叉排序树的构造过程如下:

首先将10插入根结点，得到如下树：

    10
   /  \
NULL  NULL

然后将30插入根结点的右子树，得到如下树：

    10
   /  \
NULL   30
       / \
     NULL NULL

接着将5插入根结点的左子树，得到如下树：

    10
   /  \
 5     30
 /     / \
NULL NULL NULL

然后将20插入根结点的左子树的右子树，得到如下树：

    10
   /  \
 5     30
      / \
     20 NULL
         / \
       NULL NULL

接着将40插入根结点的右子树的右子树，得到如下树：

    10
   /  \
 5     30
      / \
     20  40
         / \
       NULL NULL

最后将25插入根结点的右子树的右子树的左子树，得到如下树：

    10
   /  \
 5     30
      / \
     20  40
         / \
        25 NULL
            / \
          NULL NULL

因此，该二叉排序树为：

       10
      /  \
     5    30
         /  \
        20   40
            /
           25

(2) 从(1)所得树中删除关键字为'30'的结点之后的二叉排序树为:

首先找到要删除的结点30，由于该结点有两个子结点，因此需要找到其右子树中的最小结点，即25。然后将25的值替换到30中，再删除25即可。

删除25后，得到如下树：

       10
      /  \
     5    30
         /  \
        20   40

因此，删除关键字为'30'后的二叉排序树为：

       10
      /  \
     5    40
         /
        20