二叉排序树算法实验-白红宇

/*实现二叉排序树上的查找算法。具体实现要求：1.    用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树。2.    用广义表表示所建二叉树。3.    按中序遍历这棵二叉排序树。4.    在二叉排序树上插入结点。5.    删除二叉排序树上的结点。6.    在二叉排序树上实现查找算法。*/#include 
       #include 
        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
         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;}//在二叉排序树中删除关键字keyvoid 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(")");        }    }}//在二叉排序树中查找关键字keyBSTNode *SearchBST(BSTree T,KeyType key){    //在此插入必要的语句    if(T==NULL||key==T->key)        return T;    if(key
          key)        return SearchBST(T->lchild,key);    else         return SearchBST(T->rchild,key);}
 
感觉很难做的太少了吧