二叉排序树算法

二叉排序树的创建，查找与删除，以下代码是其所有左子树的结点均小于根的值，其右子树的值均小于其根的值。

#include<stdio.h>
#include<malloc.h>
typedef int datatype;
#define ENDKEY 0
typedef struct BSTree
{
    datatype data;
    struct BSTree *lchild;
    struct BSTree *rchild;
}BSTreenode,*BSTree;
typedef struct node
{
    BSTree BST;

    struct node *next;
}QueueNode;
typedef struct Queue
{
    QueueNode *front;
    QueueNode *tail;
}Queue;
void InitQueue(Queue *Q)
{
    Q->front=(QueueNode *)malloc(sizeof(QueueNode));
    if(Q->front)/*初始化为一个空的队列*/
    {
        Q->tail=Q->front;
        Q->front->next=NULL;

    }
}
void EnterQueue(Queue *Q,BSTree p)
{
    QueueNode *newnode;
    newnode=(QueueNode *)malloc(sizeof(QueueNode));
    if(newnode)
    {
        newnode->BST=p;
        newnode->next=NULL;
        Q->tail->next=newnode;
        Q->tail=newnode;

    }
}
void DeQueue(Queue *Q,BSTree *p)
{
    QueueNode *q;
    if(Q->front==Q->tail)
        return ;
    q=Q->front->next;
    Q->front->next=q->next;
    if(Q->tail==q)
        Q->tail=Q->front;
    *p=q->BST;
    free(q);
}
int Empty(Queue Q)
{
    if(Q.front==Q.tail)
        return 1;
    return 0;
}
void Output(BSTree BT)//利用队列层析显示二叉排序树的初始状态元素
{
    Queue Q;

    BSTree p,q;
    InitQueue(&Q);
    q=p=BT;
    if(p)
        EnterQueue(&Q,p);
    while(!Empty(Q))
    {
        DeQueue(&Q,&q);
        printf("%3d",q->data);
        if(q->lchild)
            EnterQueue(&Q,q->lchild);
        if(q->rchild)
            EnterQueue(&Q,q->rchild);
    }

}
void InsertBT(BSTree *BT,datatype key)//插入方式建立二叉树
{
    BSTreenode *bst;
    if((*BT)==NULL)
    {
        bst=(BSTreenode *)malloc(sizeof(BSTreenode));
        bst->data=key;
        bst->lchild=NULL;
        bst->rchild=NULL;
        *BT=bst;
    }
    else if(key<(*BT)->data)//小于根的元素放到左子树
    {
        InsertBT(&((*BT)->lchild),key);
    }
    else if(key>(*BT)->data)//大于根的元素放到右子树
    {
        InsertBT(&((*BT)->rchild),key);
    }


}
void Create_BSTree(BSTree *BT)
{
    datatype key;
    (*BT)=NULL;
    printf("Input the key (input 0 to end the input ):");
    scanf("%d",&key);
    while(key!=ENDKEY)
    {
        InsertBT(BT,key);
        scanf("%d",&key);
    }
}
void InorderOutput(BSTree *BT)//利用中序遍历输出二叉树的元素
{
    if(*BT)
    {
        InorderOutput(&((*BT)->lchild));
        printf("%3d",(*BT)->data);
        InorderOutput(&((*BT)->rchild));
    }
}
BSTree FindBT(BSTree BT,int key)
{
    BSTree p;
    p=BT;
    while(p)
    {
        if(p->data==key) return p;
        else if(key<p->data) p=p->lchild;
        else p=p->rchild;
    }
    return NULL;
}
BSTree DeleteKey(BSTree BT,int key)
{
    BSTree f,p,s,q;
    p=BT;
    f=NULL;
    while(p)
    {
        if(p->data==key) break;

        f=p;
        if(p->data<key) p=p->rchild;
        else
            p=p->lchild;
    }
    if(p==NULL)
        printf("Cannot find the data\n");
    if(p->lchild==NULL&&p->rchild==NULL)//如果p是叶子节点
    {
        if(f)
        {
            if(f->lchild==p)
                f->lchild=NULL;
            else
                f->rchild=NULL;
        }
        free(p);
        printf("the data has been deleted\n");
        return BT;
    }
    if(p->lchild==NULL)//要找的结点没有左子树
    {
        if(f==NULL)
            BT=p->rchild;
        else if(f->lchild==p)
            f->lchild=p->lchild;
        else
            f->rchild=p->rchild;
        free(p);
    }
    else//要找的结点有左子树
    {
        q=p;
        s=p->lchild;
        while(s->rchild)
        {
            q=s;
            s=s->rchild;
        }
        if(p==q) q->lchild=s->lchild;
        else
            q->rchild=s->lchild;
        p->data=s->data;
        free(s);

    }
    return BT;


}
void main()
{
    BSTreenode *BT,*find,*BST;
    int key;
    int Delete_key;
    Create_BSTree(&BT);//创建一颗二叉树
    Output(BT);
    printf("\nafter Inorder the tree as follow :\n");
    InorderOutput(&BT);//中序遍历可以把二叉树按递增的顺序输出
    printf("\nInput the data you wan to find :");
    scanf("%d",&key);
    find=FindBT(BT,key);
    if(find)

        printf("find the data %d\n",find->data);
    else
        printf("cannot find the data\n");
    printf("Input the data you want to delete: ");
    scanf("%d",&Delete_key);
    BST=DeleteKey(BT,Delete_key);
    InorderOutput(&BST);//删除后再次显示二叉树序列
    printf("\n");
}

熟练掌握二叉排序树的算法。