源代碼：gcc，Linux

//二叉排序樹（Binary Sort Tree）或是一空樹；或者是具有下列性質(zhì)的二叉樹：
//（1）若它的左子樹不為空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
//（2）若它的右子樹不為空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
//（3）它的左、右子樹也分別為二叉排序樹。

#include <stdlib.h>
#include <stdio.h>
typedef int KeyType;//關(guān)鍵字類型

//定義元素類型 
typedef struct ElemType{
    KeyType key;
}ElemType;

//二叉排序樹的節(jié)點 
typedef struct BSTNode{
    struct ElemType data;
    struct BSTNode *Lchild,*Rchild;
}BSTNode,*BSTree;

//插入節(jié)點
//當二叉排序樹T中不存在元素e，插入e并返回新二叉排序樹的根結(jié)點指針 
//否則返回0，內(nèi)存錯誤返回-1 
BSTree InsertBST(BSTree T,ElemType e){
    BSTree p,q,new_node;
    if(T==NULL){//如果樹為空，則以新結(jié)點為根 
        new_node=(BSTree)malloc(sizeof(BSTNode));//申請節(jié)點
        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的你節(jié)點指針
    while(p){//尋找插入位置
        q=p;
        if(e.key==p->data.key){
            return T;//e已經(jīng)存在,返回 
        }
        if(e.key<p->data.key){
            p=p->Lchild;//在左子樹找
        }else{
            p=p->Rchild;//在右子樹找 
        } 
    }//end while 
    new_node=(BSTree)malloc(sizeof(BSTNode));//申請節(jié)點
    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中查找包含關(guān)鍵字key的元素的結(jié)點 
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;//查找失敗，返回空值 
}

//訪問結(jié)點（打印出結(jié)點元素的key值） 
void _visit__(BSTree T){
    printf("%d ",T->data.key);
}

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

//刪除某節(jié)點
//刪除的方法有很多，原則是刪除后，仍保持二叉排序樹的特性
BSTree DeleteBST(BSTree T,KeyType k){
    BSTree p,q,f,h;//設(shè)指針p指向待刪除的節(jié)點，q為p的父節(jié)點指針
                   //h為p的直接前驅(qū)，f為h的父結(jié)點 
    p=T;
    q=NULL;
    while(p){//尋找被刪除的節(jié)點
        if(k==p->data.key)break;//找到被刪除的節(jié)點，退出 
        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在中序的直接前驅(qū)h
        f=p;
        h=p->Lchild;
        while(h->Rchild){
            f=h;
            h=h->Rchild;
        }
        p->data=h->data;//以h節(jié)點代替p結(jié)點，相當于刪除p結(jié)點
        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("原始數(shù)據(jù)："); 
    traLDR(bst);
    bst=DeleteBST(bst,2);
    bst=DeleteBST(bst,3);
    bst=DeleteBST(bst,48);
    printf("\n刪除2，3，48后數(shù)據(jù)："); 
    traLDR(bst);
    
    DeleteBST_All(bst); 
    return 0;   
}