二叉排序树 算法实验

/*实现二叉排序树上的查找算法。具体实现要求：
1.    用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树。
2.    用广义表表示所建二叉树。
3.    按中序遍历这棵二叉排序树。
4.    在二叉排序树上插入结点。
5.    删除二叉排序树上的结点。
6.    在二叉排序树上实现查找算法。*/


#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;

typedef int KeyType;            //假定关键字类型为整数
typedef struct node                //结点类型
{
    KeyType key;                //关键字项
    InfoType otherinfo;            //其它数据域，InfoType视应用情况而定 下面不处理它
    struct node *lchild,*rchild;//左右孩子指针
}BSTNode;
typedef BSTNode *BSTree;        //BSTree是二叉排序树的类型

void main()
{
    void InsertBST(BSTree *Tptr,KeyType key);    //将关键字key插入二叉排序树中
    BSTree CreateBST(void);            //建立二叉排序树
    void ListBinTree(BSTree T);        //用广义表表示二叉树
    void DelBSTNode(BSTree Tptr,KeyType key);    //在二叉排序树中删除关键字key
    BSTNode *SearchBST(BSTree T,KeyType key);    //在二叉排序树中查找关键字key
    
    BSTree T;
    BSTNode *p;
    int key;
    
    
    printf("请输入关键字（输入0为结束标志）：\n");
    T=CreateBST();
    ListBinTree(T);
    printf("\n");
    printf("请输入欲插入关键字：");
    scanf("%d",&key);
    InsertBST(&T,key);
    ListBinTree(T);
    printf("\n");
    printf("请输入欲删除关键字：");
    scanf("%d",&key);
    DelBSTNode(T,key);
    ListBinTree(T);
    printf("\n");
    printf("请输入欲查找关键字：");
    scanf("%d",&key);
    p=SearchBST(T,key);
    if(p==NULL)
        printf("没有找到%d！\n",key);
    else
        printf("找到%d！\n",key);
    ListBinTree(p);
    printf("\n");
}

//将关键字key插入二叉排序树中
void InsertBST(BSTree *T,KeyType key)
{
    
    BSTNode *p,*q;
    if((*T)==NULL)
    {
        (*T)=(BSTree)malloc(sizeof(BSTNode));
        (*T)->key=key;
        (*T)->lchild=(*T)->rchild=NULL;
    }
    else
    {
        p=(*T);
        while(p)
        {
            q=p;
            if(p->key>key)
                p=q->lchild;
            else if(p->key<key)
                p=q->rchild;
            else
            {
                printf("\n该二叉排序树中含有关键字为%d的结点\n",key);
                return;
            }
        }
        p=(BSTree)malloc(sizeof(BSTNode));
        p->key=key;
        p->lchild=p->rchild=NULL;
        if(q->key>key)
            q->lchild=p;
        else
            q->rchild=p;
    }
}

//建立二叉排序树
BSTree CreateBST(void)
{
    
    BSTree T = NULL;
    KeyType key;
    scanf("%d",&key);
    while(key)
    {
        InsertBST(&T,key);
        scanf("%d",&key);
    }
    return T;
}

//在二叉排序树中删除关键字key
void DelBSTNode(BSTNode *Tptr,KeyType key)
{
   

    BSTNode *f,*p=Tptr;
    while(p&&p->key!=key)//查找值为x的结点
    {
        if(p->key>key)
        {
            f=p;p=p->lchild;
        }
        else
        {
            f=p;p->rchild;
        }
    }
    if(p==NULL) {printf("没找到");return ;}//没找到
    if(p->lchild==NULL)//被删结点没有左子树，直接将右子树接到其双亲上
    {
        if(f->lchild==p)f->lchild=p->rchild;
        else f->rchild=p->rchild;
        return ;
    }
    else//被删结点有左子树
    {
        BSTNode *q=p->lchild,*s=q;
        while(q->rchild!=NULL)//查找左子树最右下的结点(中序最后结点）
        {
            s=q;q=q->rchild;
        }
        if(s==p->lchild)//p左子树的根结点无右子女
        {
            p->key=s->key;
            p->lchild=s->lchild;
            free(s);
            return ;
            
        }
        else
        {
            p->key=q->key;
            s->rchild=q->lchild;
            free(q);//删除q结点
            return ;
        }
    }

}


//用广义表表示二叉树
void ListBinTree(BSTree T)
{
    //在此插入必要的语句
    if(T!=NULL)
    {
        printf("%d",T->key);
        if(T->lchild!=NULL||T->rchild!=NULL)
        {
            printf("(");
            ListBinTree(T->lchild);
            if(T->rchild!=NULL)
                printf(",");
            ListBinTree(T->rchild);
            printf(")");
        }
    }
}

//在二叉排序树中查找关键字key
BSTNode *SearchBST(BSTree T,KeyType key)
{
    //在此插入必要的语句
    if(T==NULL||key==T->key)
        return T;
    if(key<T->key)
        return SearchBST(T->lchild,key);
    else 
        return SearchBST(T->rchild,key);
}