shuju1.txt

编写程序实现下面运算：在二叉排序树中查找关键字为key的记录。

#include <stdlib.h>
#include <stdio.h>
#define NULL 0  //表示空
typedef int KeyType;

int c=0;  //全局变量
typedef struct{
    KeyType key;
}ElemType;   //元素类型

typedef struct BiTNode
{   ElemType data;  //数据域
    struct BiTNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;
void Insert(BiTree *p,BiTree t) //在二叉排序树中插入一个新结点
{ if (*p==NULL) *p=t;
    else if(t->data.key<(*p)->data.key) Insert(&((*p)->lchild),t);
    else if(t->data.key>(*p)->data.key) Insert(&((*p)->rchild),t);
}//Insert

void preorder(BiTree p)  //先序遍历所建二叉排序树，将得到一个按关键字有序的元素序列
{
  if(p!=NULL)
  { printf("%3d",(p->data).key);
    preorder(p->lchild);
    preorder(p->rchild);
  }//if
}//preorder

BiTree find(BiTree root,KeyType key)  
{//在二叉排序树中查找其关键字等于给定值的结点是否存在，并输出相应信息
 BiTNode *p;
 c++;
 p=root;
 if (p) {
 if (p->data.key==key)   //查找成功 
	 {printf("关键字%d在二叉树中需要%d次查找，记录为：%d\n",key,c,p->data.key); 
	 exit(1);}
    else if (key<p->data.key)   //若要查找的关键字比当前结点的关键字小，到左子树中继续查找 
		 find(p->lchild,key);
    else  find(p->rchild,key)  ;//若要查找的关键字比当前结点的关键字大，到左子树中继续查找 
	}//if
 else 
	 printf("此二叉排序树中没有关键字%d.",key);
	 return 0;
}//BiTree find

void main()
{ KeyType key;
  BiTree p,s;
  int i=0;
  printf("请输入二叉排序树的关键字的先序序列（0表结束）：\n");
//建立一棵二叉排序树，元素值从键盘输入，直到输入关键字等于0为止
  scanf("%3d",&key);
  p=NULL;
  while(key!=NULL){    
    s=(BiTree)malloc(sizeof(BiTNode));  //为结点s分配存储空间
    (s->data).key=key;
    s->lchild=s->rchild=NULL;
    Insert(&p,s);  //调用函数Insert()，将结点插入二叉排序树
    scanf("%d",&key);
  }
  printf("二叉排序树的先序序列为：\n");
  preorder(p);   //先序遍历已建立的二叉排序树
  printf("\n");
  printf("请输入要查找的记录的关键字:");
  scanf("%3d",&key);
  find(p,key);//调用函数find(),在二叉排序树中查找其关键字为k的结点是否存在
  printf("\n");
}//main