04-树7 二叉搜索树的操作集

04-树7 二叉搜索树的操作集

分数 30
作者 陈越
单位 浙江大学

本题要求实现给定二叉搜索树的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
C (gcc)

思路

要掌握好递归算法。
其次要记住二叉搜索树的性质，
所有左子树上的点都比根结点小，所有右子树上的点都比根结点大。
左子树和右子树也是二叉搜索树。

AC代码：

BinTree Insert( BinTree BST, ElementType X )
{
    if(BST==NULL)
    {
        //如果BST是空树 为树申请空间
        BST=(struct TNode *)malloc(sizeof(struct TNode));
        BST->Data=X;
        BST->Left=NULL;
        BST->Right=NULL;
        return BST;
    }
    if(X<BST->Data)//小于根结点的值 放在左子树里
        BST->Left=Insert(BST->Left,X);
    if(X>BST->Data)//大于根结点的值 放在右子树里
        BST->Right=Insert(BST->Right,X);
    return BST;//返回树的根结点
}
BinTree Delete( BinTree BST, ElementType X )
{
    Position temp;
    if(!BST)//空树
        printf("Not Found\n");
    else
    {
        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)
            {
                //左右节点都不为空
                temp=FindMin(BST->Right);//寻找右结点中最小的点
                BST->Data=temp->Data;//将最小的点作为新的树的根结点
                BST->Right=Delete(BST->Right,BST->Data);//右节点为右子树删去右节点中最小的点
            }
            else//左或者右结点为空或者都为空
            {
                temp=BST;
                if(!BST->Left)//左节点为空
                    BST=BST->Right;
                else if(!BST->Right)//右节点为空
                    BST=BST->Left;
                free(temp);//释放，删除
            }
        }
    }
    return BST;//返回树的根结点
}
Position Find( BinTree BST, ElementType X )
{
    if(BST==NULL)//如果树为空，返回空
        return BST;
    if(BST->Data==X)
        return BST;//返回根结点
    if(BST->Data>X)
        return Find(BST->Left,X);//小于，再左子树找
    if(BST->Data<X)
        return Find(BST->Right,X);//大于，在右子树找
}
Position FindMin( BinTree BST )
{
    if(BST)
    {
        //左子树里放的都是小的数
        while(BST->Left!=NULL) BST=BST->Left;
    }
    return BST;
}
Position FindMax( BinTree BST )
{
    if(BST)
    {
        //右子树里放的都是大的数
        while(BST->Right!=NULL) BST=BST->Right;
    }
    return BST;
}