在二叉排序树中查找关键字为key的记录.docx

在二叉排序树中查找关键字为key的记录.docx

《在二叉排序树中查找关键字为key的记录.docx》由会员分享，可在线阅读，更多相关《在二叉排序树中查找关键字为key的记录.docx（4页珍藏版）》请在冰点文库上搜索。

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

学院名称

专业班级

实验成绩

学生姓名

学号

实验日期

课程名称

数据结构

实验题目

4查找

一、实验目的与要求

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

二、主要仪器设备

Cfree

三、实验内容和原理

2.实习题1

[问题描述]

编写程序实现下面运算:

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

[输入]

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

[输出]

显示该节点是否存在。

[存储结构]

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

[算法的基本思想]

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

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

若key=根节点的关键字，查找成功；

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

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

[参考源程序]

#include

#include

#defineNULL0

typedefintKeyType;

typedefstruct{

KeyTypekey;

}ElemType;//元素类型

typedefstructBiTNode{

ElemTypedata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

BiTreesearchBST（BiTreebt,KeyTypekey）{

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

if（bt==NULL）returnNULL;//在排序二叉树中进行递归查找

elseif（bt->data.key==key）returnbt;

elseif（keydata.key）returnsearchBST（bt->lchild,key）;

elsereturnsearchBST（bt->rchild,key）;

}

voidinsertBST（BiTree*bt,BiTrees）{

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

if（*bt==NULL）*bt=s;

elseif（s->data.key<（*bt）->data.key）insertBST（&（（*bt）->lchild）,s）;

elseif（s->data.key>（*bt）->data.key）insertBST（&（（*bt）->rchild）,s）;

}

main（）{

charch;

KeyTypekey;

BiTreebt,s;

inti=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）;

elseprintf（"\n没有找到!

\n"）;

printf（"\n是否继续?

（y/n）：

"）;

scanf（"%c",&ch）;

ch=getchar（）;

}

while（ch=='y'||ch=='Y'）;

getchar（）;

}//main

实验结果：