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

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

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

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

二、主要仪器设备

Cfree

三、实验内容和原理

2.实习题1

[问题描述]

编写程序实现下面运算:

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

[输入]

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

[输出]

显示该节点是否存在。

[存储结构]

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

[算法的基本思想]

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

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

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

若key<

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

若key>

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

[参考源程序]

#include<

malloc.h>

stdio.h>

#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（key<

bt->

data.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）;

data.key>

rchild）,s）;

main（）{

charch;

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

}//while

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

do{

\n输入你想要查找的元素：

"

s=searchBST（bt,key）;

if（s!

=NULL）printf（"

\n成功!

这个等价元素是%d.\n"

s->

data.key）;

elseprintf（"

\n没有找到!

\n是否继续?

（y/n）：

%c"

ch）;

ch=getchar（）;

}

while（ch=='

y'

||ch=='

Y'

）;

getchar（）;

}//main

实验结果：