【函数题】6-12 二叉搜索树的操作集

1 题目原文

题目链接：6-12 二叉搜索树的操作集

本题要求实现给定二叉搜索树的5种常用操作。

函数接口定义：

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

其中 BinTree 结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

函数 Insert 将 X 插入二叉搜索树 BST 并返回结果树的根结点指针；
函数 Delete 将 X 从二叉搜索树 BST 中删除，并返回结果树的根结点指针；如果 X 不在树中，则打印一行Not Found 并返回原树的根结点指针；
函数 Find 在二叉搜索树 BST 中找到 X，返回该结点的指针；如果找不到则返回空指针；
函数 FindMin 返回二叉搜索树 BST 中最小元结点的指针；
函数 FindMax 返回二叉搜索树 BST 中最大元结点的指针。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT ); /* 先序遍历，由裁判实现，细节不表 */
void InorderTraversal( BinTree BT );  /* 中序遍历，由裁判实现，细节不表 */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("\n");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found\n", X);
        else {
            printf("%d is found\n", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key\n", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key\n", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例：

10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3

输出样例：

Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9

代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB

2 思路解析

    题目要求实现二叉搜索树的 5 种常用操作，其中 插入，查找，最大值，最小值 这 4 种操作没有什么难以理解的，都是直接根据二叉搜索树的性质来的。但是 删除 这个操作比较繁琐，需要注意。
    下面是 删除 操作的算法步骤，其余操作的算法步骤见代码注释。
        1. 寻找待删除的结点，可以直接调用 查找 操作；
        2. 如果没有，则做相应操作，结束；
        3. 如果有，用指针 p 指向该结点，q 指向其父结点：
            3.1 p 是一个叶结点：将 q 的相应儿子指针置为空，并删除 p，结束；
            3.2 p 只有左子树：删除 p，将 p 的位置替换为 p.left；
            3.3 p 只有右子树：删除 p，将 p 的位置替换为 p.right；
            3.4 p 有左右子树：找到 p 的第一个后继结点 r，删除 p，将 p 的位置替换为 r，将原来的 r 删掉。

3 代码实现

    下面给出递归法和迭代法两种代码实现。

3.1 插入操作

3.1.1 递归法

BinTree Insert(BinTree BST, ElementType X) {
    if (!BST) {
        // 空树
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    } else if (X > BST->Data) {
        // 要插入的值大于根结点的值，往右子树里面插
        BST->Right = Insert(BST->Right, X);
    } else if (X < BST->Data) {
        // 要插入的值小于根结点的值，往左子树里面插
        BST->Left = Insert(BST->Left, X);
    }
    // 当 X == BST->Data 时，是没有执行任何操作的
    return BST;
}

3.1.2 迭代法

BinTree Insert(BinTree BST, ElementType X) {
    Position node = (BinTree)malloc(sizeof(struct TNode));
    node->Data = X;
    node->Left = node->Right = NULL;
    if (!BST) {
        return node;
    }
    Position p = BST, q = NULL;
    while (p && p->Data != X) {
        q = p;
        p = p->Data < X ? p->Right : p->Left;
    }
    if (q->Data < X) {
        q->Right = node;
    } else if (q->Data > X) {
        q->Left = node;
    }
    return BST;
}

3.2 删除操作

    注意删除操作调用了查找最小值操作

3.2.1 递归法

BinTree Delete(BinTree BST, ElementType X) {
    if (!BST) {
        // 空树
        printf("Not Found\n");
        return NULL;
    }
    if (X < BST->Data) {
        // 如果目标值小于当前结点的值，递归到左子树中删除
        BST->Left = Delete(BST->Left, X);
    } else if (X > BST->Data) {
        // 如果目标值大于当前结点的值，递归到右子树中删除
        BST->Right = Delete(BST->Right, X);
    } else {
        // 找到目标结点
        if (BST->Left && BST->Right) {
            // 如果目标结点有两个子结点
            // 找到右子树中的最小值结点（后继结点）
            Position tt = FindMin(BST->Right);
            // 将目标结点的值替换为后继结点的值
            BST->Data = tt->Data;
            // 递归删除后继结点
            BST->Right = Delete(BST->Right, tt->Data);
        } else {
            // 如果目标结点只有一个子结点或没有子结点
            Position temp = BST;
            if (!BST->Left) {
                // 只有右子树或没有子结点
                BST = BST->Right;
            } else if (!BST->Right) {
                // 只有左子树
                BST = BST->Left;
            }
            // 释放目标结点的空间
            free(temp);
        }
    }
    return BST;
}

3.2.1 迭代法

BinTree Delete(BinTree BST, ElementType X) {
    if (!BST) {
        // 空树
        printf("Not Found\n");
        return NULL;
    }
    BinTree p = NULL, t = BST;
    // 否则，找出目标结点以及其父结点
    while (t && t->Data != X) {
        p = t;
        t = X < t->Data ? t->Left : t->Right;
    }
    if (!t) {
        // 如果没找到，直接返回BST
        printf("Not Found\n");
        return BST;
    }
    // 否则，p指向的就是目标值父结点，t指向目标值
    // 进一步判断目标值结点的子树情况
    if (t->Left && t->Right) {
        // 两棵子树都存在，找目标结点的后继（其右子树的最小值）
        Position tt = FindMin(t->Right);
        // 可知tt所指的结点就是目标值的后继结点，显然tt没有左子树
        // 然后将目标结点的左子树接到后继结点的左子树上
        tt->Left = t->Left;
        // 删除目标结点
        if (!p) {
            // 如果目标结点就是根结点
            BST = t->Right;
        } else {
            if (p->Left == t) {
                p->Left = t->Right;
            } else {
                p->Right = t->Right;
            }
        }
    } else if (t->Left) {
        // 只有左子树，直接删掉，其左子树直接接上去
        if (!p) {
            // 如果目标结点就是根结点
            BST = t->Left;
        } else {
            if (p->Left == t) {
                p->Left = t->Left;
            } else {
                p->Right = t->Left;
            }
        }
    } else if (t->Right) {
        // 只有右子树，直接删掉，与左子树同理
        if (!p) {
            // 如果目标结点就是根结点
            BST = t->Right;
        } else {
            if (p->Left == t) {
                p->Left = t->Right;
            } else {
                p->Right = t->Right;
            }
        }
    } else {
        // 叶结点，直接释放空间，同时别忘了置空
        if (!p) {
            // 如果目标结点就是根结点
            BST = NULL;
        } else {
            if (p->Left == t) {
                p->Left = NULL;
            } else {
                p->Right = NULL;
            }
        }
    }
    // 释放空间
    free(t);
    return BST;
}

3.3 查找操作

3.3.1 递归法

Position Find(BinTree BST, ElementType X) {
    if (!BST) {
        return NULL;
    }
    return X == BST->Data  ? BST
           : X < BST->Data ? Find(BST->Left, X)
                           : Find(BST->Right, X);
}

3.3.2 迭代法

Position Find(BinTree BST, ElementType X) {
    Position p = BST;
    while (p && p->Data != X) {
        p = X < p->Data ? p->Left : p->Right;
    }
    return p;
}

3.4 查找最大值操作

3.4.1 递归法

Position FindMax(BinTree BST) {
    if (!BST || !BST->Right) {
        return BST;
    }
    return FindMax(BST->Right);
}

3.4.2 迭代法

Position FindMax(BinTree BST) {
    Position p = BST;
    while (p && p->Right) {
        p = p->Right;
    }
    return p;
}

3.5 查找最小值操作

    和查找最大值操作类似

3.5.1 递归法

Position FindMin(BinTree BST) {
    if (!BST || !BST->Left) {
        return BST;
    }
    return FindMin(BST->Left);
}

3.5.2 迭代法

Position FindMin(BinTree BST) {
    Position p = BST;
    while (p && p->Left) {
        p = p->Left;
    }
    return p;
}

4 总结

    实际上在删除二叉搜索树结点的时候可以有很多种操作的方法，比如可以取第一个前驱结点替代当前结点而不一定是第一个后继结点等，还可以在删除的时候调整二茶搜索树的某些结构。