二叉排序树（Binary Sort Tree）

#include "stdio.h"
#include "stdlib.h"

//二叉链表结点 
typedef struct Node{
    int data;
    struct Node *lchild,*rchild;
}Node,*BSTree;


/*
在指针pTree所指的二叉排序树中递归查找关键字为key的元素，
若查找成功，则返回ture，并将 查找到的数据对应的节点指针 保存在p中，
否则返回0，并将 查找路径上访问的最后一个节点指针 保存在p中。
这里的参数f指向每次递归遍历的子树的根节点的父节点，即始终是参数pTree的父节点， 
它的初始值为NULL，其目的是跟踪查找路径上访问的当前节点的父节点（即上一个访问节点）
该函数用来被后面的插入结点函数调用。
*/
int search_Node(BSTree pTree,int key,BSTree f,BSTree &p)
{
    if(!pTree){
        p = f;
        return 0;
    }else if(key == pTree->data){
        p = pTree;
        return 1;
    }else if(key > pTree->data){
        search_Node(pTree->rchild,key,pTree,p);
    }else{
        search_Node(pTree->lchild,key,pTree,p);
    }
    
}


/*
往二叉排序树种插入结点 
当在pTree所指向的二叉排序树中查找不到关键字为key的数据元素时，
将其插入该二叉排序树，并返回1，否则返回0。
树空时插入会改变根节点的值，因此要传入引用。

 */
int insertNode(BSTree &pTree,int key)
{
    BSTree p;
    if(!search_Node(pTree,key,NULL,p)){
        
        BSTree pNew = (BSTree)malloc(sizeof(Node));  //产生新元素的结点 
        pNew->lchild = pNew->rchild = NULL;
        pNew->data = key;
        
        if(!p){
            pTree = pNew;            //如何树空，直接将pNew置为根节点 
        }else{
            if(key > p->data){
                p->rchild = pNew;        //作为右孩子插入p的右边 
            }else{
                p->lchild = pNew;        //作为左孩子插入p的左边 
            }        
        }
        return 1;
    }else
        return 0;
    
}


//创建二叉排序树 
BSTree create_BSTree(int *arr,int num)
{
    BSTree pTree = NULL;
    int i;
    for(i=0;i<num;i++)
        insertNode(pTree,arr[i]);
    return pTree;
    
}

//递归中序遍历二叉树，得到元素从小到大的有序排列 
void InorderTraverse(BSTree pTree)
{
    if(pTree){        
        InorderTraverse(pTree->lchild);
        printf("%d ",pTree->data);
        InorderTraverse(pTree->rchild);    
    }
}

//修改左子树的方法删除结点 
int delete_Node1(BSTree &p)
{
    BSTree q,s;
    if(!p->lchild){                  //左子树为空，只需重新接上右子树    
        q = p;
        p = p->rchild;
        free(q);
    }else if(!p->rchild){        //右子树为空，只需重新接上左子树
        q = p;
        p = p->lchild;
        free(q);
    }else{                        //如果左右子树都不为空
                                //我们这里采取修改左子树的方法，也可以修改右子树，方法类似
        q = p;
        s = p->lchild;            //取待删节点的左节点
        while(s->rchild){        //一直向右，最终s为待删节点的前驱节点。
                                //如果将各节点元素按从小到大顺序排列成一个序列，
                                //则某节点的前驱节点即为序列中该节点的前面一个节点
            q = s;
            s = s->rchild;
        }
        //用s来替换待删节点p
        p->data = s->data;
        //根据情况，将s的左子树重接到q上
        if(p != q){
            q->rchild = s->lchild;
        }else{
            q->lchild = s->lchild;
        }    
        free(s); 
    }
    return 1;
}

//修改右子树的方法删除结点
int delete_Node2(BSTree &p)
{
    BSTree q,s;
    if(!p->lchild){                //左子树为空，只需重新接上右子树
        q = p;
        p = p->rchild;
        free(q);
    }else if(!p->rchild){        //右子树为空，只需重新接上左子树
        q = p;
        p = p->lchild;
        free(q);
    }else{
        q = p;
        s = p->rchild;
        while(s->lchild){
            q = s;
            s = s->lchild; 
        }
        //用s来替换待删节点p
        p->data = s->data;
        //根据情况，将s的左子树重接到q上
        if(p != q){
            q->lchild = s->rchild;
        }else{
            q->rchild = s->rchild;
        }
        free(s);
    }
    return 1;
} 

//删除结点 
int delete_BSTree(BSTree &pTree,int key)
{
    if(!pTree){            //不存在关键字为key的结点 
        return 0;
    }else{
        if(key == pTree->data){
        //    return delete_Node1(pTree);
            return delete_Node2(pTree);
        }else if(key > pTree->data){
            return delete_BSTree(pTree->rchild,key);
        }else{
            return delete_BSTree(pTree->lchild,key);
        }
    }
}


int main()
{
    BSTree pTree;
    int i,num,flag;
    printf("请输入节点的个数:");
    scanf("%d",&num);
//    printf("%d\n",num);
    
    int *arr = (int *)malloc( num * sizeof(int));
    for(i=0;i<num;i++)
        scanf("%d",arr+i);
    
    pTree = create_BSTree(arr,num);
    printf("中序遍历该二叉排序树的结果：");  
    InorderTraverse(pTree);printf("\n"); 
    
    printf("请输入要删除的结点：");
    scanf("%d",&num);
    flag = delete_BSTree(pTree,num);
    if(flag){
        printf("删除成功！\n");
    }else{
        printf("删除失败！\n");
    }
    printf("中序遍历该二叉排序树的结果：");
    InorderTraverse(pTree);printf("\n"); 


    return 0;
}