关于二叉查找树

其实这个相当与折半查找，左子树一定比根节点的元素值小，右子树一定比根节点的元素大。
这个寻找最小跟最大元素的算法就会很简单，
1：FindMin与FindMax
寻找最小时候就一直往左子树上走，寻找最大的时候就一直往右子树上走.

SearchNode FindMin(SearchTree T)
{
if(T==NULL)
return NULL;
else
{
while(T->left)
T=T->left;
return T;
}
SearchTree FindMAX(SearchTree T)
{
if(T==NULL)
return NULL;
else
{
if(T->left==NULL)
return T;
else
return FindMAX(T->right);
}
}

2:Insert
建立的时候呢，就是一个节点一个节点的插入，比较插入比较插入的过程，然后就是递归插入。
3:Delete
删除的时候则比较麻烦。删除有好几种情况
第一种：如果节点是一片树叶，那么它立即直接被删除。这里就不做分析
第二种：如果节点有一个二字，则该节点可以在其父节点调整指针绕过该节点后被删除。即如下图所示：

即：

SearchNode *temp;
if(T->left==NULL)
    T=T->right;
else if(T->right==NULL)
   T=T->left;
free(temp);//如上图，则能删除节点4

3：复杂的情况是处理有两个儿子的节点，一般的删除策略是永右子树的最小数据代替该节点的数据并递归的删除那个节点。
                        
算法如下：

temp=FindMin(T->right);
T->data=temp->data;
T->right=Delete(T->right,T->data)

整个代码的实现如下：

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

#define OK 1
#define ERROR 0
typedef struct Node
{
    int  data;
    struct Node *left;
    struct Node *right;
}SearchNode,*SearchTree;

//创建只含有一个元素的树
SearchTree search_tree_create(int data)
{
    SearchTree T;
    T=(SearchTree)malloc(sizeof(SearchNode));
    T->data=data;
    T->left=NULL;
    T->right=NULL;
    return T;
}
//插入元素，创建树
SearchTree  search_tree_insert(SearchTree T,int t)
{
    if(T==NULL)
    {
        T=(SearchTree)malloc(sizeof(SearchNode));
        if(T==NULL)
            printf("错误!\n");
        else
        {
            T->data=t;
            T->left=T->right=NULL;
        }
    }
    else if(t<T->data)
            T->left=search_tree_insert(T->left,t);
    else if(t>T->data)
            T->right=search_tree_insert(T->right,t);
    return T;
}
//寻找树中最小元素
SearchTree  FindMin(SearchTree T)
{
    if(T==NULL)
    {
        printf("没有元素，无法寻找!\n");
        return NULL;
    }
    else
    {
        while(T->left)
            T=T->left;
        printf("the min is %d\n",T->data);
        return T;
    }
}
//寻找树中最右边的元素，即最大值
SearchTree  FindMax(SearchTree T)
{
    if(T==NULL)
    {
        printf("没有元素，无法找到!\n");
        return NULL;
    }
    else
    {
        while(T->right)
            T=T->right;
        printf("the max is %d\n",T->data);
        return T;
    }

}
//删除数组a中第三个元素a[2]
SearchTree Delete(SearchTree T,int x)
{
    SearchNode *p;
    if(T==NULL)
        printf("ERROR");
    else if(x<T->data)
            T->left=Delete(T->left,x);
    else if(x>T->data)
        T->right=Delete(T->right,x);
    else if(T->left&&T->right)
    {
        p=FindMin(T->right);
        T->data=p->data;
        T->right=Delete(T->right,T->data);
    }
    else
    {
        p=T;
        if(T->left==NULL)
            T=T->right;
        else if(T->right==NULL)
            T=T->left;
        free(p);
    }
    return T;
}
void Output(SearchTree T,int layer)
{
    int i;
    if(T==NULL)
        return;
    Output(T->right,layer+1);
    for(i=0;i<layer;i++)
        printf(" ");
    printf("%d\n",T->data);
    Output(T->left,layer+1);
}
int main()
{
    SearchTree T;
    int layer=0;
    int a[7];
    int i;
    printf("please input the number you want:");
    for(i=0;i<7;i++)
        scanf("%d",&a[i]);
    T=search_tree_create(a[0]);
    printf("After Insert:\n");
    for(i=1;i<7;i++)
        search_tree_insert(T,a[i]);
    Output(T,layer);
    FindMin(T);
    FindMax(T);
    T=Delete(T,a[2]);
    Output(T,layer);
}