在二叉排序树中查找关键字为key地记录簿

一、实验目的与要求

通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。

二、主要仪器设备

Cfree

三、实验内容和原理

2.实习题1

[问题描述]

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

[输入]

排序二叉树，以及要查找的数字（节点）。

[输出]

显示该节点是否存在。

[存储结构]

有序表采用顺序方式存储。

[算法的基本思想]

若二叉排序树为空树，查找失败，返回null或0；

否则，将key与根节点的关键字比较：

若key=根节点的关键字二叉排序树查找，查找成功；

若key<根节点的关键字，继续在左子树中查找；

若key>根节点的关键字，继续在右子树中查找。

[参考源程序]

#include <malloc.h>

#include <stdio.h>

#define NULL 0

typedef int KeyType;

typedef struct {

KeyType key;

}ElemType; //元素类型

typedef struct BiTNode{

ElemType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

BiTree searchBST(BiTree bt,KeyType key){

/*在二叉排序树 bt 中查找其关键字等于给定值的结点是否存在，并输出相应信息*/

if (bt==NULL) return NULL;//在排序二叉树中进行递归查找

else if (bt->data.key==key) return bt;

else if (key<bt->data.key) return searchBST(bt->lchild,key);

else return searchBST(bt->rchild,key);

}

void insertBST(BiTree *bt,BiTree s){

/*在二叉排序树中插入一个新结点,即依次插入输入的数*/

if (*bt==NULL) *bt=s;

}else if(phead->data == key){//单独处理第一个结点。 }else if(phead->data == key){//单独处理第一个结点 。 }else if(phead->data == key){//处理第一个结点是否为目标结点 。

else if (s->data.key>(*bt)->data.key) insertBST(&((*bt)->rchild),s);

}

main(){

char ch;

KeyType key;

BiTree bt,s;

int i=0;

/*建立一棵二叉排序树二叉排序树查找，元素从键盘按先序输入，直到输入关键字等于-1为止*/

printf("\n请输入元素(-1:结束)：\n");//以-1为结束

scanf("%d",&key);

bt=NULL;

while (key!=-1){

s=(BiTree)malloc(sizeof(BiTNode));

(s->data).key=key;s->lchild=s->rchild=NULL;

insertBST(&bt,s);

scanf("%d",&key);

}//while

/*二叉排序树的查找，可多次查找，并输出查找的结果*/

do {

printf("\n输入你想要查找的元素：");

scanf("%d",&key);

s=searchBST(bt,key);

if (s!=NULL) printf("\n成功! 这个等价元素是 %d.\n",s->data.key);

else printf("\n没有找到!\n");

printf("\n是否继续?(y/n)：");

scanf("%c",&ch);

ch=getchar();

}

while (ch=='y' || ch=='Y') ;

getchar();

}//main

实验结果：

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-111472-1.html