【二叉搜索樹】：一棵樹可以為空，如果不空亮隙，必須滿足以下性質(zhì)：
非空左子樹的所有的鍵值小于其根節(jié)點的鍵值
非空右子樹的所有的鍵值大于其根節(jié)點的鍵值
左途凫、右子樹都是二叉搜索樹

二叉搜索樹

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

#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); //返回最小元素節(jié)點的指針
BinTree FindMaxNode(BinTree bst); //返回最大元素的節(jié)點指針
BinTree FindX(ElementType X, BinTree bst); //查找元素X并返回其節(jié)點指針
BinTree DeleteX(ElementType X, BinTree bst);//刪除指定節(jié)點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;
}

/* 建立二叉樹溢吻、插入節(jié)點(只能插在葉節(jié)點) */
BinTree Insert(ElementType X,BinTree bst)
{
    if(!bst){
        /* 如果樹為空维费，生成并返回一個節(jié)點的二叉樹 */
        bst=(BinTree)malloc(sizeof(struct TNode));
        bst->Data=X;
        bst->Left=bst->Right=NULL;
    }else{
        /* 找到要插入節(jié)點的位置 */
        if(X<bst->Data){
            bst->Left=Insert(X,bst->Left); //遞歸插入左子樹
        }else if(X>bst->Data){
            bst->Right=Insert(X,bst->Right);//遞歸插入右子樹
        }else;
    }
    return bst;
}

/* 最小元素一定在樹的最左端分支的端節(jié)點 */
BinTree FindMinNode(BinTree bst)
{
    if(!bst)    return NULL;
    else if(!bst->Left) return bst;
    else    return FindMinNode(bst->Left);
}

/* 最大元素一定在樹的最右端分支的端節(jié)點 */
BinTree FindMaxNode(BinTree bst)
{
    if(!bst)    return NULL;
    else if(!bst->Right)    return bst;
    else return FindMaxNode(bst->Right);
    /*
        迭代實現(xiàn)
        if(bst){
            while(bst->Right)
                bst=bst->Right;
        }
        return bst;
    */
}

/* 
    查找元素X，并返回其指針
    x小于根節(jié)點鍵值促王，左子樹搜索
    x大于根節(jié)點鍵值犀盟，右子樹搜索
    結(jié)果相等，搜索完成蝇狼，返回指向此節(jié)點的指針 
 */
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;
    }
}

/* 
    二叉搜索樹刪除指定元素阅畴，并返回二叉樹指針 
    刪除葉節(jié)點：直接刪除，并修改其父節(jié)點指針為NULL
    刪除節(jié)點只有一個孩子節(jié)點：
    將其父節(jié)點的指針指向要刪除的節(jié)點的孩子節(jié)點
    刪除節(jié)點有兩個孩子節(jié)點：
    用另一個節(jié)點替代被刪除節(jié)點（右子樹的最小元素或者左子樹的最大元素）
*/
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) { //左右節(jié)點均存在
            temp=FindMaxNode(bst);
            bst->Data=temp->Data;
            bst->Right=DeleteX(bst->Data,bst->Right);
        }else{      //小于等于一個節(jié)點
            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);
    }
}