ecpx.c

在二叉排序树上实现对给定值进行查找操作.其中:1)用二叉链表来存储二叉排序树

#include <stdio.h>
typedef int elemtype;
typedef int keytype;
typedef struct Bitnode
{ elemtype data;
 struct   Bitnode *lchild, *rchild;}Bitnode,*Bitree;
Bitree insert(Bitree T,Bitree s)/*二叉排序树插入函数*/
{if(T==NULL) T=s;
 else if(s->data>T->data)
       T->rchild=insert(T->rchild,s);/*递归*/
 else if(s->data<T->data)
      T->lchild=insert(T->lchild,s);/*递归*/
   return T;}
Bitree creat(Bitree T)/*二叉排序树建立函数*/
{elemtype x;
 Bitree s;
 do{scanf("%d",&x);/*输入需要插入的数据*/
 s=(Bitree)malloc(sizeof(Bitnode));
 s->data=x;s->lchild=NULL;s->rchild=NULL;
 T=insert(T,s);/*调用二叉排序树插入函数*/
 }while(x!=-1);
return T;}
Bitree searchbst(Bitree T,keytype K)/*二叉排序树查找函数*/
{if(T==NULL||K==T->data) return T;
  else if(K>T->data) return(searchbst(T->rchild,K));/*递归查找二叉排序树右子树*/
  else return(searchbst(T->lchild,K));/*递归查找二叉排序树左子树*/
 }}
main()/*主函数*/
{Bitree T,p;
 keytype K;
 printf("\nplease input data ,stop with -1:\n");/*请求输入数据，以-1结束*/
 T=creat(T);/*调用二叉排序树建立函数*/
 printf("please input a data to search :");/*请求输入需要查找的数据*/
 scanf("%d",&K);
 p=searchbst(T,K);/*调用二叉排序树查找函数*/
 if(p==NULL)
  printf("\ncan't search this data!");/*输出“找不到”提示*/
 else
  printf("\nthe data is found!");/*输出“找到”提示*/
}