数据结构二叉排序树（Binary Sort Tree）（C语言实

源代码：gcc，Linux

//二叉排序树（Binary Sort Tree）或是一空树；或者是具有下列性质的二叉树：
//（1）若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
//（2）若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
//（3）它的左、右子树也分别为二叉排序树。

#include <stdlib.h>
#include <stdio.h>
typedef int KeyType;//关键字类型

//定义元素类型 
typedef struct ElemType{
    KeyType key;
}ElemType;

//二叉排序树的节点 
typedef struct BSTNode{
    struct ElemType data;
    struct BSTNode *Lchild,*Rchild;
}BSTNode,*BSTree;

//插入节点
//当二叉排序树T中不存在元素e，插入e并返回新二叉排序树的根结点指针 
//否则返回0，内存错误返回-1 
BSTree InsertBST(BSTree T,ElemType e){
    BSTree p,q,new_node;
    if(T==NULL){//如果树为空，则以新结点为根 
        new_node=(BSTree)malloc(sizeof(BSTNode));//申请节点
        if(new_node!=NULL){
            new_node->data=e;
            new_node->Lchild=new_node->Rchild=NULL;
            T=new_node;
            return T;
        }else{
            return NULL;
        }
    }
    p=T;
    q=NULL;//q为p的你节点指针
    while(p){//寻找插入位置
        q=p;
        if(e.key==p->data.key){
            return T;//e已经存在,返回 
        }
        if(e.key<p->data.key){
            p=p->Lchild;//在左子树找
        }else{
            p=p->Rchild;//在右子树找 
        } 
    }//end while 
    new_node=(BSTree)malloc(sizeof(BSTNode));//申请节点
    if(new_node!=NULL){
        new_node->data=e;
        new_node->Lchild=new_node->Rchild=NULL;
        if(e.key<q->data.key){
            q->Lchild=new_node;
        }else{
            q->Rchild=new_node;
        }
        return T;
    }else{
        return NULL;
    }
}

//在二叉排序树T中查找包含关键字key的元素的结点 
BSTree SearchBST( const BSTree T,KeyType k){
    BSTree p=T;
    while(p){
        if(k==p->data.key){
            return p;//查找成功 
        }
        if(k<p->data.key){
            p=p->Lchild;
        }else{
            p=p->Rchild;
        }
    }
    return NULL;//查找失败，返回空值 
}

//访问结点（打印出结点元素的key值） 
void _visit__(BSTree T){
    printf("%d ",T->data.key);
}

//中序遍历二叉树 
void traLDR(BSTree T){
    if(T){
        traLDR(T->Lchild);
        _visit__(T);
        traLDR(T->Rchild);
    }
}

//删除某节点
//删除的方法有很多，原则是删除后，仍保持二叉排序树的特性
BSTree DeleteBST(BSTree T,KeyType k){
    BSTree p,q,f,h;//设指针p指向待删除的节点，q为p的父节点指针
                   //h为p的直接前驱，f为h的父结点 
    p=T;
    q=NULL;
    while(p){//寻找被删除的节点
        if(k==p->data.key)break;//找到被删除的节点，退出 
        q=p;
        if(k<p->data.key){
            p=p->Lchild;//在左子树中查找 
        }else{
            p=p->Rchild;//在右子树中查找 
        }
    }
    if(p==NULL)return T;//没有找到
    if(p->Lchild==NULL){//p无左子树时
        if(q==NULL){
            T=p->Rchild;//p为根，删除后，其右子为根 
        }else if(q->Lchild==p){//p为q的左子树时，将p的右子树给q的左子树 
            q->Lchild=p->Rchild;            
        }else{//p为q的右子树时，将p的右子树给q的右子树 
            q->Rchild=p->Rchild;
        }
        free(p); 
    }else{//当p的左子树存在时，寻找p在中序的直接前驱h
        f=p;
        h=p->Lchild;
        while(h->Rchild){
            f=h;
            h=h->Rchild;
        }
        p->data=h->data;//以h节点代替p结点，相当于删除p结点
        if(f!=p){
            f->Rchild=h->Lchild;
        }else{
            f->Lchild=h->Lchild;
        }
        free(h); 
    }
    return T;
}

//释放二叉排序树的空间 
void DeleteBST_All(BSTree T){
    BSTree p=T; 
    if(T){
        DeleteBST_All(T->Lchild);
        free(p);
        DeleteBST_All(T->Rchild);
    }
}

int main(){
    BSTree bst=NULL;//新的二叉排序树 
    ElemType e;
    //插入若干元素 
    e.key=50;
    bst=InsertBST(bst,e);
    e.key=23;
    bst=InsertBST(bst,e);
    e.key=53;
    bst=InsertBST(bst,e);
    e.key=50;
    bst=InsertBST(bst,e);
    e.key=12;
    bst=InsertBST(bst,e);
    e.key=52;
    bst=InsertBST(bst,e);
    e.key=100;
    bst=InsertBST(bst,e);
    e.key=45;
    bst=InsertBST(bst,e);
    e.key=48;
    bst=InsertBST(bst,e);
    e.key=15;
    bst=InsertBST(bst,e);
    e.key=3;
    bst=InsertBST(bst,e);
    e.key=2;
    bst=InsertBST(bst,e);
    e.key=98;
    bst=InsertBST(bst,e);
    e.key=60;
    bst=InsertBST(bst,e);
    
    printf("原始数据："); 
    traLDR(bst);
    bst=DeleteBST(bst,2);
    bst=DeleteBST(bst,3);
    bst=DeleteBST(bst,48);
    printf("\n删除2，3，48后数据："); 
    traLDR(bst);
    
    DeleteBST_All(bst); 
    return 0;   
}