erchpxs.c

将一个记录集合用一棵二叉排序树表示

#include <stdio.h>
#define null 0

typedef struct btreenode   /*定义二又排序树结构体*/
   {int data;
    struct btreenode *lchild;
    struct btreenode *rchild;
    }bnode;

bnode *p;

bnode *creat(int x,bnode *lbt,bnode *rbt)   /*创建根结点*/
    {bnode *p;
    p=(bnode*)malloc(sizeof(bnode));
    p->data=x;
    p->lchild=lbt;
    p->rchild=rbt;
    return(p);
    }

bnode *ins_lchild(bnode *p,int x)    /*结点作为左孩子插入*/
    {bnode *q;
    if(p==null)
       printf("Illegal insert.");
    else
      {q=(bnode*)malloc(sizeof(bnode));
       q->data=x;
       q->lchild=null;
       q->rchild=null;
       p->lchild=q;
      }
    }

bnode ins_rchild(bnode *p,int x)    /*结点作为右孩子插入*/
    {bnode *q;
    if(p==null)
       printf("Illegal insert.");
    else
      {q=(bnode*)malloc(sizeof(bnode));
       q->data=x;
       q->lchild=null;
       q->rchild=null;
       p->rchild=q;
      }
    }

void prorder(bnode *p,int counter)    /*输出二又树结构*/
    {if(p==null)
      return;
    counter++;
    printf("%d\t%u\t%d\t%u\t%u\n",counter,p,p->data,p->lchild,p->rchild);
    if(p->lchild!=null)
       prorder(p->lchild,counter);
    if(p->rchild!=null)
       prorder(p->rchild,counter);
    }

bnode *bs_search(bnode *t,int k)    /*在二又排序树中查找关键字为k的结点*/
    {bnode *s;
    if(t==null)
      {printf("empty tree.");
      return(t);}
    s=t;
    if(s->data==k)
      {printf("Find it.");
       return(s);}
    else
      if(s->data>k)    /*在左于树上继续查找*/
        return(bs_search(s->lchild,k));
      else
       return(bs_search(s->rchild,k));    /*在右子树上继续查找*/
    }


main()
   {int k;
    bnode *bt,*p,*q;
    int x,counter=0;
    printf("Input root:");
    scanf("%d",&x);
    p=creat(x,null,null);    /*创建二又排序树*/
    bt=p;
    scanf("%d",&x);
    while(x!=-1)
      {p=bt;
       while(x!=p->data&&p!=null)
	{q=p;
         if(x<p->data)
	   p=p->lchild;
         else
	   p=p->rchild;
        }
       if(x==p->data)
	 {printf("The data is exit.");
          return;}
       else
	 if(x<q->data)
	   ins_lchild(q,x);
         else
	   ins_rchild(q,x);
       scanf("%d",&x);
    }
    p=bt;
    prorder(p,counter);
    printf("Search key=");
    scanf("%d",&k);
    q=bs_search(p,k);
    printf("q=%u",q);
    printf("\n");
    getchar();
    getchar();
}