前言碎语

这因为学习树结构里面的最基本操作了，但是作为小白入门，哪怕是最基础的也会感觉困难重重，所以，最稳的方法：乐观好心态，咱一步一步，一点一点来。

几点说明

树的结构在定义的时候，用的是嵌套结构，即树的左右子树也都是树。

在建立树的时候，每一次只申请一块栈空间，所以需要for循环来调用；BST、BST -> Left、BST -> Right表示的都是地址，所以Insert函数那里，最后返回的是地址。

原题描述

 二叉搜索树的操作集 (30 point(s))
本题要求实现给定二叉搜索树的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

具体实现如下

#include <cstdio>
#include <cstdlib>

//BinTree 结构定义
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode {
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

//实现前序、中序、后序遍历
//这里的遍历就是把print
void PreorderTraversal(BinTree BT);
void InorderTraversal(BinTree BT);
void PostorderTraversal(BinTree BT);
//层序遍历
//需要用到队列结构
//void LevelorderTraversal(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;
}


//中序遍历
void InorderTraversal(BinTree BT)
{
    if (BT) {
        InorderTraversal(BT -> Left);
        printf("%d ", BT -> Data);
        InorderTraversal(BT -> Right);
    }
}

//前序遍历
void PreorderTraversal(BinTree BT)
{
    if (BT) {
        printf("%d ", BT -> Data);
        PreorderTraversal(BT -> Left);
        PreorderTraversal(BT -> Right);
    }
}

//后序遍历
void PostorderTraversal(BinTree BT)
{
    if (BT) {
        PostorderTraversal(BT -> Left);
        PostorderTraversal(BT -> Right);
        printf("%d ", BT -> Data);
    }
}

//二叉搜索树的插入
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 -> 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 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 = FindMax(BST -> Left);
                BST -> Data = Temp -> Data;
                //重新赋值，“相当于”结点的删除
                //然后把这个结点删掉就好
                BST -> Left = Delete(BST -> Left, BST -> Data);
            }
            else {
                Temp = BST;
                if (!BST -> Left)
                    BST = BST -> Right;
                else
                    BST = BST -> Left;
                free(Temp);
            }
        }
    }
    return BST;
}

//直接查找，while循环
Position Find(BinTree BST, ElementType X)
{
    while (BST) {
        if (X < BST -> Data)
            BST = Find(BST -> Left, X);
        else if (X > BST -> Data)
            BST = Find(BST -> Right, X);
        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);
}