PTA 数据结构与算法题目集（中文）6-12 二叉搜索树的操作集

深藏阁楼爱情的钟 2022-05-15 10:14 173阅读 0赞

6-12 二叉搜索树的操作集（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

作者: 陈越

单位: 浙江大学

时间限制: 400 ms

内存限制: 64 MB

代码长度限制: 16 KB

BinTree Insert( BinTree BST, ElementType X )
    {
        if(BST == NULL)
        {
            BST = (struct TNode*)malloc(sizeof(struct TNode));
            BST->Data = X;
            BST->Left = BST->Right = NULL;
            return BST;
        }
        else if(BST->Data>X)
        {
            BST->Left = Insert(BST->Left,X);
        }
        else
        {
            BST->Right = Insert(BST->Right,X);
        }
        return BST;
    }
    BinTree Delete( BinTree BST, ElementType X )
    {
        if(BST == NULL)
        {
            printf("Not Found\n");
            return BST;
        }
        if(BST->Data == X)
        {
            if(BST->Left==NULL&&BST->Right==NULL)
            {
                free(BST);
                return NULL;
            }
            else if(BST->Left!=NULL)
            {
                BinTree p,q;
                p = BST;
                q = p->Left;
                if(q->Right == NULL)
                {
                    BST->Data = q->Data;
                    p->Left = q->Left;
                    free(q);
                    return BST;
                }
                while(q->Right)
                {
                    p = q;
                    q = q->Right;
                }
                BST->Data = q->Data;
                p->Right = NULL;
                if(q->Left!=NULL)
                {
                    p->Right = q->Left;
                    free(q);
                }
            }
            else
            {
                BinTree p,q;
                p = BST;
                q = p->Right;
                if(q->Left == NULL)
                {
                    BST->Data = q->Data;
                    p->Right = q->Right;
                    free(q);
                    return BST;
                }
                while(q->Left)
                {
                    p = q;
                    q = q->Left;
                }
                BST->Data = q->Data;
                p->Left = NULL;
                if(q->Right!=NULL)
                {
                    p->Left = q->Right;
                    free(q);
                }
            }
            return BST;
        }
        if(BST->Data>X)BST->Left = Delete(BST->Left,X);
        else BST->Right = Delete(BST->Right,X);
        return BST;
    }
    Position Find( BinTree BST, ElementType X )
    {
        if(BST == NULL)return BST;
        if(BST->Data == X)
        {
            return BST;
        }
        return BST->Data>X?Find(BST->Left,X):Find(BST->Right,X);
    }
    Position FindMin( BinTree BST )
    {
        if(BST==NULL)return NULL;
        while(BST->Left)BST = BST->Left;
        return BST;
    }
    Position FindMax( BinTree BST )
    {
        if(BST==NULL)return NULL;
        while(BST->Right)BST = BST->Right;
        return BST;
    }