数据结构与算法题目集--函数题（已完结）

约定不等于承诺〃 2022-10-10 11:14 535阅读 0赞

**目录**

6-1 单链表逆转

6-2 顺序表操作集 (20 分)

6-3 求链式表的表长 (10 分)

6-4 链式表的按序号查找 (10 分)

6-5 链式表操作集 (20 分)

6-6 带头结点的链式表操作集

6-7 在一个数组中实现两个堆栈

6-8 求二叉树高度

6-9 二叉树的遍历

6-10 二分查找

6-11 先序输出叶结点

6-12 二叉搜索树的操作集

--------------------

# 6-1 单链表逆转 #

要求实现一个函数，将给定的单链表逆转。

`L`是给定单链表，函数`Reverse`要返回被逆转后的链表。

程序：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElementType;
    typedef struct Node *PtrToNode;
    struct Node {
        ElementType Data;
        PtrToNode   Next;
    };
    typedef PtrToNode List;
    
    List Read(); /* 细节在此不表 */
    void Print( List L ); /* 细节在此不表 */
    
    List Reverse( List L );
    
    int main()
    {
        List L1, L2;
        L1 = Read();
        L2 = Reverse(L1);
        Print(L1);
        Print(L2);
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    List Reverse( List L )
    {
        if(!L)
            return 0;
        
        PtrToNode pre,tmp;
        pre=NULL;
        tmp=NULL;
        while(L)         
        {
            tmp=L->Next;      tmp只是暂存节点，使链表节点可链接，它并不参与逆置的主过程
            L->Next=pre;
            pre=L;
            L=tmp;           //头指针随着tmp指针移动，当他们为null时，
                             //链表遍历完毕，退出循环
        }
        return pre;         //L 最后一定为NULL，因此不返回L，
                            //而返回pre，将其作为新链表的头指针
        
    }

**笔记：**

这道题坑就坑在没有头节点，L为头指针，如果没注意到这点，很容易犯错。

当有头节点时，L指向头节点，用就地逆置的方法，程序如下

List Reverse( List L )
    {
        
        PtrToNode pre,tmp;
        pre=L->Next;
        L->Next=NULL;
        while(pre)
        {
            tmp=pre->Next;      //tmp只是暂存节点，使链表节点可链接，它并不参与逆置的主过程
            pre->Next=L->Next;
            L->Next=pre;
            pre=tmp;
    
        }
        return L;
        
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70][]

# 6-2 顺序表操作集 (20 分) #

本题要求实现顺序表的操作集。

**`List MakeEmpty()`：**创建并返回一个空的线性表；

**`Position Find( List L, ElementType X )`：**返回线性表中X的位置。若找不到则返回ERROR；

**`bool Insert( List L, ElementType X, Position P )`：**将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；

**`bool Delete( List L, Position P )`：**将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。

程序：

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 5
    #define ERROR -1
    typedef enum {false, true} bool;
    typedef int ElementType;
    typedef int Position;
    typedef struct LNode *List;
    struct LNode
    {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    
    List MakeEmpty();
    Position Find( List L, ElementType X );
    bool Insert( List L, ElementType X, Position P );
    bool Delete( List L, Position P );
    
    int main()
    {
        List L;
        ElementType X;
        Position P;
        int N;
    
        L = MakeEmpty();
        scanf("%d", &N);
        while ( N-- )
        {
            scanf("%d", &X);
            if ( Insert(L, X, 0)==false )              //都是从下标为0的位置插入，故数据的存放和输入的顺序刚好相反
                printf(" Insertion Error: %d is not in.\n", X);
        }
        scanf("%d", &N);
        while ( N-- )
        {
            scanf("%d", &X);
            P = Find(L, X);           //从先前建立的L表中查找数
            if ( P == ERROR )
                printf("Finding Error: %d is not in.\n", X);
            else
                printf("%d is at position %d.\n", X, P);
        }
        scanf("%d", &N);
        while ( N-- )
        {
            scanf("%d", &P);
            if ( Delete(L, P)==false )             //将P位置的元素删除
                printf(" Deletion Error.\n");
            if ( Insert(L, 0, P)==false )          //将0插入到位置P中
                printf(" Insertion Error: 0 is not in.\n");
        }
        return 0;
    }
    
    
    
    /* 你的代码将被嵌在这里 */
    List MakeEmpty()
    {
        List L;
        L=(List)malloc(sizeof(struct LNode));
        L->Last=-1;
        return L;
    
    }
    Position Find( List L, ElementType X )
    {
        int i;
        for(i=0; i<=4; i++)
        {
            if(X==L->Data[i])
                return i;
        }
    
        return  ERROR;
    }
    bool Insert( List L, ElementType X, Position P )
    {
        if(L->Last==MAXSIZE-1)   //last 为数组中下标值
        {
            printf("FULL");
            return false;
        }
        if(P<0||P>(L->Last+1))
        {
            printf("ILLEGAL POSITION");
            return false;
        }
        Position j=0;
        for(j=L->Last; j>=P; j--)
        {
            L->Data[j+1]=L->Data[j];
        }
        L->Data[P]=X;
        L->Last++;
    
        return true;
    }
    bool Delete( List L, Position P )
    {
        if(P<0||P>L->Last)
        {
            printf("POSITION %d EMPTY",P);
            return false;
        }
        for(int j=P; j<L->Last; j++)
        {
            L->Data[j]=L->Data[j+1];
        }
        L->Last--;
        return true;
    }

# 6-3 求链式表的表长 (10 分) #

本题要求实现一个函数，求链式表的表长。

`L`是给定单链表，函数`Length`要返回链式表的长度。

程序：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode List;
    
    List Read(); /* 细节在此不表 */
    
    int Length( List L );
    
    int main()
    {
        List L = Read();
        printf("%d\n", Length(L));
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    
    //求链式表的表长
    int Length( List L )
    {
        PtrToLNode p;
        int count=0;
        p=L;
        while(p!=NULL)
        {   
            count++;
            p=p->Next;
           
        }

# 6-4 链式表的按序号查找 (10 分) #

本题要求实现一个函数，找到并返回链式表的第K个元素。

`L`是给定单链表，函数`FindKth`要返回链式表的第`K`个元素。如果该元素不存在，则返回`ERROR`。

程序：

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR -1
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode List;
    
    List Read(); /* 细节在此不表 */
    
    ElementType FindKth( List L, int K );
    
    int main()
    {
        int N, K;
        ElementType X;
        List L = Read();
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &K);
            X = FindKth(L, K);
            if ( X!= ERROR )
                printf("%d ", X);
            else
                printf("NA ");
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    
    
    //找到并返回链式表的第K个元素
    ElementType FindKth( List L, int K )
    {
        PtrToLNode p;
        int count=1;
        p=L;
        while(count<K)
        {
            p=p->Next;
            count++;
        }
        if(p==NULL||K<=0)
            return ERROR;
       
        return p->Data;
    }

# 6-5 链式表操作集 (20 分) #

**本题要求实现链式表的操作集。**

各个操作函数的定义为：

**`Position Find( List L, ElementType X )`**：返回线性表中首次出现X的位置。若找不到则返回ERROR；

**`List Insert( List L, ElementType X, Position P )`**：将X插入在位置P指向的结点之前，返回链表的表头。如果参数P指向非法位置，则打印“Wrong Position for Insertion”，返回ERROR；

**`List Delete( List L, Position P )`**：将位置P的元素删除并返回链表的表头。若参数P指向非法位置，则打印“Wrong Position for Deletion”并返回ERROR。

程序：

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR NULL
    typedef int ElementType;
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode Position;
    typedef PtrToLNode List;
    
    Position Find( List L, ElementType X );
    List Insert( List L, ElementType X, Position P );
    List Delete( List L, Position P );
    
    int main()
    {
        List L;
        ElementType X;
        Position P, tmp;
        int N;
    
        L = NULL;
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            L = Insert(L, X, L);
            if ( L==ERROR ) printf("Wrong Answer\n");
        }
        scanf("%d", &N);
        while ( N-- ) {
            scanf("%d", &X);
            P = Find(L, X);
            if ( P == ERROR )
                printf("Finding Error: %d is not in.\n", X);
            else {
                L = Delete(L, P);
                printf("%d is found and deleted.\n", X);
                if ( L==ERROR )
                    printf("Wrong Answer or Empty List.\n");
            }
        }
        L = Insert(L, X, NULL);      //在表尾插入
        if ( L==ERROR ) printf("Wrong Answer\n");
        else
            printf("%d is inserted as the last element.\n", X);
        P = (Position)malloc(sizeof(struct LNode));
        tmp = Insert(L, X, P);
        if ( tmp!=ERROR ) printf("Wrong Answer\n");
        tmp = Delete(L, P);
        if ( tmp!=ERROR ) printf("Wrong Answer\n");
        for ( P=L; P; P = P->Next ) printf("%d ", P->Data);
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    Position Find( List L, ElementType X )
    {
         //返回线性表中首次出现X的位置。若找不到则返回ERROR；
        List p;
        p=L;
        while(p)
        {
            if(p->Data==X)
                return p;
            p=p->Next;
    }
        return ERROR;
        
    }
    List Insert( List L, ElementType X, Position P )
    {
       /* 将X插入在位置P指向的结点之前，返回链表的表头。如果参数P指向非法位置，
        则打印“Wrong Position for Insertion”，返回ERROR；*/
        
        List node=(List)malloc(sizeof(struct LNode));
        node->Next=NULL;
        node->Data=X;
        //在表头插入
        if(P==L)
        {
            node->Next=L;
            return node;
        }
        //在表中插入
        List tmp;
        tmp=L;
        while(tmp)
        {
            if(tmp->Next==P)      //在这里写成tmp==P,调试好久
            {
                node->Next=tmp->Next;
                tmp->Next=node;
                return L;
             }
            tmp=tmp->Next;
        }
       
        printf("Wrong Position for Insertion\n");
        return ERROR; 
    }
    List Delete( List L, Position P )
    {
        /*将位置P的元素删除并返回链表的表头。若参数P指向非法位置，
        则打印“Wrong Position for Deletion”并返回ERROR */
         if(P==L)
        {
            L=L->Next;
            return L;
        }
        //在表中删除
        List tmp;
        tmp=L;
        while(tmp)
        {
            if(tmp->Next==P)
            {
                tmp->Next=P->Next;
                return L;
             }
            tmp=tmp->Next;
        }
       
        printf("Wrong Position for Deletion\n");
        return ERROR; 
        
        
    }

注：直接对L进行改动，也是可以的，我习惯了不用头指针操作

# 6-6 带头结点的链式表操作集 #

本题要求实现带头结点的链式表操作集。

List MakeEmpty()
    {
        List head = (List)malloc(sizeof(struct LNode));   //创建头节点
        head->Next=NULL;
        return head;
    }
    Position Find( List L, ElementType X )
    {
      //  L=L->Next;
        while(L)
        {
            if(L->Data==X)
                return L;
            L=L->Next;
        }
        return ERROR;
    
    }
    bool Insert( List L, ElementType X, Position P )
    {
        List node=(List)malloc(sizeof(List));
        node->Data=X;
        node->Next=NULL;
    
        //List tmp=L;
        while(L)
        {
            if(L->Next==P)
            {
                node->Next=L->Next;
                L->Next=node;
                return true;
            }
            L=L->Next;
        }
        printf("Wrong Position for Insertion\n");
        return false;
    
    
    }
    bool Delete( List L, Position P )
    {
       /* if(L==P)       //删除头节点
        {
            L=L->Next;
            return true;
        }
        */
        while(L)
        {
            if(L->Next==P)
            {
                L->Next=P->Next;
                return true;
            }
            L=L->Next;
        }
        printf("Wrong Position for Deletion\n");
        return false;
    
    }

# 6-7 在一个数组中实现两个堆栈 #

本题要求在一个数组中实现两个堆栈

函数定义：

Stack CreateStack( int MaxSize );  
bool Push( Stack S, ElementType X, int Tag );  
ElementType Pop( Stack S, int Tag );

其中`Tag`是堆栈编号，取1或2；`MaxSize`堆栈数组的规模；

`Stack`结构定义如下：

typedef int Position;
    struct SNode {
        ElementType *Data;
        Position Top1, Top2;
        int MaxSize;
    };
    typedef struct SNode *Stack;

注意：如果堆栈已满，`Push`函数必须输出“Stack Full”并且返回false；如果某堆栈是空的，则`Pop`函数必须输出“Stack Tag Empty”（其中Tag是该堆栈的编号），并且返回ERROR。

程序样例：

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 1e8
    typedef int ElementType;
    typedef enum { push, pop, end } Operation;
    typedef enum { false, true } bool;
    typedef int Position;
    struct SNode {
        ElementType *Data;
        Position Top1, Top2;
        int MaxSize;
    };
    typedef struct SNode *Stack;
    
    Stack CreateStack( int MaxSize );
    bool Push( Stack S, ElementType X, int Tag );
    ElementType Pop( Stack S, int Tag );
    
    Operation GetOp();  /* details omitted */
    void PrintStack( Stack S, int Tag ); /* details omitted */
    
    int main()
    {
        int N, Tag, X;
        Stack S;
        int done = 0;
    
        scanf("%d", &N);
        S = CreateStack(N);
        while ( !done ) {
            switch( GetOp() ) {
            case push: 
                scanf("%d %d", &Tag, &X);
                if (!Push(S, X, Tag)) printf("Stack %d is Full!\n", Tag);
                break;
            case pop:
                scanf("%d", &Tag);
                X = Pop(S, Tag);
                if ( X==ERROR ) printf("Stack %d is Empty!\n", Tag);
                break;
            case end:
                PrintStack(S, 1);
                PrintStack(S, 2);
                done = 1;
                break;
            }
        }
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

**实现代码：**

Stack CreateStack( int MaxSize )
    {
        Stack s=(Stack)malloc(sizeof(Stack));
        s->Data=(ElementType *)malloc(sizeof(ElementType)*MaxSize);
        s->Top1=-1;
        s->Top2=MaxSize;
        s->MaxSize=MaxSize;
        return s;
    }
    bool Push( Stack S, ElementType X, int Tag )
    {
      //  if(S==NULL)
        //    return false;
        if(S->Top1+1==S->Top2)
        {
            printf("Stack Full\n");
            return false;
        }
        if(Tag==1)
        {
            S->Data[++S->Top1]=X;
    
        }
        else
        {
            S->Data[--S->Top2]=X;
    
        }
        return true;
    }
    ElementType Pop( Stack S, int Tag )
    {
       // if(S==NULL)
         //   return ERROR;
        if((Tag==1&&S->Top1==-1)||(Tag==2&&S->Top2==S->MaxSize))
       {
            printf("Stack %d Empty\n",Tag);
            return ERROR;
        }
        if(Tag==1)
       {
        return S->Data[S->Top1--];
        }
    
        else
        {
            return S->Data[S->Top2++];
        }
    
    }

解析：在CreateStack函数中，创建一个顺序栈，然后对其初始化，即data指针指向一个新分配的大小为MaxSize的数组空间，top1,2 分别有各自的初始值，还有这个栈的大小——MaxSize要初始化。其他的则很容易，只要注意 top2的入栈-1，出栈+1

# 6-8 求二叉树高度  #

本题要求函数返回给定二叉树BT的高度值。

函数接口定义：

int GetHeight( BinTree BT );

其中`BinTree`结构定义如下：

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

程序样例:

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree(); /* 实现细节忽略 */
    int GetHeight( BinTree BT );
    
    int main()
    {
        BinTree BT = CreatBinTree();
        printf("%d\n", GetHeight(BT));
        return 0;
    }
    /* 你的代码将被嵌在这里 */

**代码实现：**

int GetHeight( BinTree BT )
    {
        int depthL,depthR;    
        if(BT==NULL)                  //空树，深度为0
            return 0;
        if(BT->Left==NULL&&BT->Right==NULL)    //叶子节点，深度为1
            return 1;
        depthL=GetHeight(BT->Left);           //左子树深度
        depthR=GetHeight(BT->Right);          //左子树深度
        return depthL>depthR ? 1+depthL:1+depthR;     //返回左右子树深度大的，加1（根节点）
    }

# 6-9 二叉树的遍历  #

本题要求给定二叉树的4种遍历。中序，先序，后序和层次遍历注解

函数接口定义：

void InorderTraversal( BinTree BT );
    void PreorderTraversal( BinTree BT );
    void PostorderTraversal( BinTree BT );
    void LevelorderTraversal( BinTree BT );

其中`BinTree`结构定义如下：

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

要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。

程序样例：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElementType;
    typedef struct TNode *Position;
    typedef Position BinTree;
    struct TNode{
        ElementType Data;
        BinTree Left;
        BinTree Right;
    };
    
    BinTree CreatBinTree(); /* 实现细节忽略 */
    void InorderTraversal( BinTree BT );
    void PreorderTraversal( BinTree BT );
    void PostorderTraversal( BinTree BT );
    void LevelorderTraversal( BinTree BT );
    
    int main()
    {
        BinTree BT = CreatBinTree();
        printf("Inorder:");    InorderTraversal(BT);    printf("\n");
        printf("Preorder:");   PreorderTraversal(BT);   printf("\n");
        printf("Postorder:");  PostorderTraversal(BT);  printf("\n");
        printf("Levelorder:"); LevelorderTraversal(BT); printf("\n");
        return 0;
    }
    /* 你的代码将被嵌在这里 */

**代码实现**

void InorderTraversal( BinTree BT )
    {
        //中序遍历
        if(BT==NULL)
            return;
        InorderTraversal(BT->Left);
        printf(" %c",BT->Data);
        InorderTraversal(BT->Right);
    
    }
    void PreorderTraversal( BinTree BT )
    {
        //先序遍历
        if(BT==NULL)
            return;
        printf(" %c",BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
    void PostorderTraversal( BinTree BT )
    {
        if(BT==NULL)
            return;
        PostorderTraversal(BT->Left);
        PostorderTraversal(BT->Right);
        printf(" %c",BT->Data);
    
    }
    void LevelorderTraversal( BinTree BT )
    {
        //层次遍历（用队列实现--先进先出）
        int Maxsize=1000;
        BinTree Queue[Maxsize];
        if(BT==NULL)
            return;
        int front=-1,rear=0;
        Queue[rear]=BT;
        while(rear!=front)    //队列不空，继续遍历
        {
            front++;   //出队
            printf(" %c",Queue[front]->Data);
            if(Queue[front]->Left!=NULL)     //如果该节点有左孩子，则入队
            {
                rear++;
                Queue[rear]=Queue[front]->Left;
            }
            if(Queue[front]->Right!=NULL)   //如果该节点有右孩子，也要入队
            {
                rear++;
                Queue[rear]=Queue[front]->Right;
            }
        }
    
    }

注解：

先序遍历：

1.  若二叉树为空，则return
2.  二叉树不为空，访问根节点
3.  访问左子树
4.  访问右子树

# 6-10 二分查找  #

本题要求实现二分查找算法。也称 折半查找

函数接口定义：

Position BinarySearch( List L, ElementType X );

其中`List`结构定义如下：

typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };

`L`是用户传入的一个线性表，其中`ElementType`元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数`BinarySearch`要查找`X`在`Data`中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记`NotFound`。

程序样例：

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    #define NotFound 0
    typedef int ElementType;
    
    typedef int Position;
    typedef struct LNode *List;
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last; /* 保存线性表中最后一个元素的位置 */
    };
    
    List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
    Position BinarySearch( List L, ElementType X );
    
    int main()
    {
        List L;
        ElementType X;
        Position P;
    
        L = ReadInput();
        scanf("%d", &X);
        P = BinarySearch( L, X );
        printf("%d\n", P);
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

**代码实现**

Position BinarySearch( List L, ElementType X )
    {
      int low=1,high=L->Last,mid=0;
      while(low<=high)
      {
        
        mid=(low+high)/2;
        if(X==L->Data[mid])
          return mid;
        else if(X>L->Data[mid])
          low=mid+1;
        else
          high=mid-1;
      }
      return NotFound;
    }

# 6-11 先序输出叶结点 #

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。

函数接口定义：

void PreorderPrintLeaves( BinTree BT );

其中`BinTree`结构定义如下：

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

函数`PreorderPrintLeaves`应按照先序遍历的顺序输出给定二叉树`BT`的叶结点，格式为一个空格跟着一个字符。

程序样例：

**程序实现**

void PreorderPrintLeaves( BinTree BT )
    {
      if(BT==NULL)
        return;
      if(BT->Left==NULL&&BT->Right==NULL)
        printf(" %c",BT->Data);
      PreorderPrintLeaves(BT->Left);
      PreorderPrintLeaves(BT->Right); 
    }

# 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;
    }
    /* 你的代码将被嵌在这里 */

**代码实现**

BinTree Insert( BinTree BST, ElementType X ){
        //如果是一个空节点
        if(!BST){
            BST = (BinTree)malloc(sizeof(struct TNode));//既然为空所以要生成一个
            BST->Data = X;
            BST->Left = NULL;
            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);//递归插入右子树
            }
            //如果相等说明X已经存在，什么也不做
        }
        return BST;
    }
    Position Find( BinTree BST, ElementType X ){
        while(BST){//直接循环查找，类似链表
            if(X < BST->Data){
                BST = BST->Left;//小于节点，找左子树
            }
            else if(X > BST->Data){//大于节点，找右子树
                BST = BST->Right;
            }
            else{//相等则找到
                return BST;
            }
        }
        return NULL;
    }
    Position FindMin( BinTree BST ){
        if(!BST){
            return NULL;
        }
        else if(!BST->Left)
            return BST;
        else return FindMin(BST->Left);
    }
    Position FindMax( BinTree BST ){
        if(!BST)return NULL;
        else if(!BST->Right)return BST;
        else return FindMax(BST->Right);
    }
    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{//当前BST就是要删除的节点
                  if(BST->Left && BST->Right){//要被删除的节点有左右两个孩子，就从右子树中找最小的数填充删除的节点
                    temp = FindMin(BST->Right);//找最小
                    BST->Data = temp->Data;//填充删除的节点
                    BST->Right = Delete(BST->Right,temp->Data);//删除拿来填充的那个节点
                  }
                  else{//只有一个子节点
                    temp = BST;
                    if(!BST->Left){//只有右节点
                        BST = BST->Right;//直接赋值就可以
                    }
                    else if(!BST->Right){//只有左节点
                        BST = BST->Left;//直接赋值就可以
                    }
                    free(temp);//如果啥也没有直接删除就可以，当然上面两种情况赋值后也要删除
                  }
            }
        }
        return BST;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lheWFfMTIzNDU2Nzg_size_16_color_FFFFFF_t_70]: /images/20221005/66c677aa0851469b92d15edde77849a1.png