二叉搜索树操作集

【二叉搜索树】：一棵树可以为空，如果不空，必须满足以下性质：
非空左子树的所有的键值小于其根节点的键值
非空右子树的所有的键值大于其根节点的键值
左、右子树都是二叉搜索树

/* 搜索二叉树操作集 */

#include<stdio.h>
#include<stdlib.h>

#define SIZE 10
typedef int ElementType;
typedef struct TNode *BinTree;
typedef BinTree Position;
typedef struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree Insert(ElementType X,BinTree bst);//二叉搜索树建立、插入
void PreOrderTraversal(BinTree bst); //输出二叉树
BinTree FindMinNode(BinTree bst); //返回最小元素节点的指针
BinTree FindMaxNode(BinTree bst); //返回最大元素的节点指针
BinTree FindX(ElementType X, BinTree bst); //查找元素X并返回其节点指针
BinTree DeleteX(ElementType X, BinTree bst);//删除指定节点X并返回其指针

int main()
{
    int x=1;
    BinTree BST = NULL;
    BinTree MinNodeOfBST=NULL;
    BinTree MaxNodeOfBST=NULL;
    BinTree findNodeX=NULL;

    int arrary[SIZE] = { 5,2,1,3,6,7,8,9,4,0 };
    for (int i = 0; i < SIZE; i++) {
        BST=Insert(arrary[i],BST);
    }

    PreOrderTraversal(BST);

    putchar('\n');
    MinNodeOfBST=FindMinNode(BST);
    MaxNodeOfBST=FindMaxNode(BST);
    printf("Min= %d  Max= %d\n", MinNodeOfBST->Data,MaxNodeOfBST->Data);

    findNodeX=FindX(x,BST);
    printf("%d\n", findNodeX->Data);

    BST=DeleteX(1,BST);
    PreOrderTraversal(BST);
    putchar('\n');
    BST = DeleteX(1, BST);

    system("pause");

    return 0;
}

/* 建立二叉树、插入节点(只能插在叶节点) */
BinTree Insert(ElementType X,BinTree bst)
{
    if(!bst){
        /* 如果树为空，生成并返回一个节点的二叉树 */
        bst=(BinTree)malloc(sizeof(struct TNode));
        bst->Data=X;
        bst->Left=bst->Right=NULL;
    }else{
        /* 找到要插入节点的位置 */
        if(X<bst->Data){
            bst->Left=Insert(X,bst->Left); //递归插入左子树
        }else if(X>bst->Data){
            bst->Right=Insert(X,bst->Right);//递归插入右子树
        }else;
    }
    return bst;
}

/* 最小元素一定在树的最左端分支的端节点 */
BinTree FindMinNode(BinTree bst)
{
    if(!bst)    return NULL;
    else if(!bst->Left) return bst;
    else    return FindMinNode(bst->Left);
}

/* 最大元素一定在树的最右端分支的端节点 */
BinTree FindMaxNode(BinTree bst)
{
    if(!bst)    return NULL;
    else if(!bst->Right)    return bst;
    else return FindMaxNode(bst->Right);
    /*
        迭代实现
        if(bst){
            while(bst->Right)
                bst=bst->Right;
        }
        return bst;
    */
}

/* 
    查找元素X，并返回其指针
    x小于根节点键值，左子树搜索
    x大于根节点键值，右子树搜索
    结果相等，搜索完成，返回指向此节点的指针 
 */
BinTree FindX(ElementType X, BinTree bst)
{
    if(bst){
        if(X>bst->Data) //位于右子树
            return FindX(X,bst->Right);
        else if(X<bst->Data)    //位于左子树
            return FindX(X,bst->Left);
        else
            return bst;
    }
}

/* 
    二叉搜索树删除指定元素，并返回二叉树指针 
    删除叶节点：直接删除，并修改其父节点指针为NULL
    删除节点只有一个孩子节点：
    将其父节点的指针指向要删除的节点的孩子节点
    删除节点有两个孩子节点：
    用另一个节点替代被删除节点（右子树的最小元素或者左子树的最大元素）
*/
BinTree DeleteX(ElementType X,BinTree bst)
{
    BinTree temp;
    if(!bst)    printf("Not Find X\n");
    else if(X<bst->Data)    //位于左子树
        bst->Left=DeleteX(X,bst->Left);
    else if(X>bst->Data)    //位于右子树
        bst->Right=DeleteX(X,bst->Right);
    else    //要删除的点
        if(bst->Left&&bst->Right) { //左右节点均存在
            temp=FindMaxNode(bst);
            bst->Data=temp->Data;
            bst->Right=DeleteX(bst->Data,bst->Right);
        }else{      //小于等于一个节点
            temp=bst;
            if(!bst->Left)
                bst=bst->Right;
            else if(!bst->Right)
                bst=bst->Left;
            free(temp);
        }
        return bst;
}

/* 输出二叉树 */
void PreOrderTraversal(BinTree bst)
{
    if(bst){
        printf("%d ", bst->Data);
        PreOrderTraversal(bst->Left);
        PreOrderTraversal(bst->Right);
    }
}