04-树7 二叉搜索树的操作集(c语言实现)

Myth丶恋晨 2021-10-29 23:42 262阅读 0赞

### 题目 ###

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

### 代码 ###

/*插入*/
    BinTree Insert( BinTree BST, ElementType X ){
    	if(!BST){
    		//若原树为空，生成并返回一个结点的二叉搜索树
    		BST=malloc(sizeof(struct TNode));
    		BST->Data=X;
    		BST->Left=BST->Right=NULL;
    	}else{										//开始找要插入元素的位置
    		if(X<BST->Data){
    			BST->Left=Insert(BST->Left,X);		//递归插入左子树
    		}else if(X>BST->Data){
    			BST->Right=Insert(BST->Right,X);	//递归插入右子树
    		}
    	}
    	return BST;
    }
    
    /*删除*/
    BinTree Delete( BinTree BST, ElementType X ){
    	Position Tmp;
    	if(!BST) printf("Not Found");			//树为空 找不到
    	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->Right && BST->Left){		//被删除结点有左右两个子结点
    			Tmp=FindMin(BST->Right);		//在右子树中找最小的元素填充删除结点
    			BST->Data=Tmp->Data;
    			BST->Right=Delete(BST->Right,BST->Data);	//在删除结点的右子树中删除最小元素
    		}else{								//被删除结点有一个或无子节点
    			Tmp=BST;
    			if(!BST->Left)					//有右孩子或无子结点
    				BST=BST->Right;
    			else if(!BST->Right)			//有左孩子或无子结点
    				BST=BST->Left;
    			free(Tmp);
    		}
    		return BST;
    }
    
    /*迭代查找*/
    Position Find( BinTree BST, ElementType X ){
    	while(BST){
    		if(X>BST->Data)
    			BST=BST->Right;
    		else if(X<BST->Data)
    			BST=BST->Left;
    		else
    			return BST;
    	}
    	return NULL;
    
    }
    
    /*最小值*/
    Position FindMin( BinTree BST ){
    	if(BST){
    		while(BST->Left){
    			BST=BST->Left;
    		}		
    	}
    	return BST;
    }
    
    /*最大值*/
    Position FindMax( BinTree BST ){
    	if(BST){
    		while(BST->Right){
    			BST=BST->Right;
    		}		
    	}
    	return BST;
    }

### 提交结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211029/98c367ddbbed4e27913f5a36ad28253a.png