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

1、通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。二、主要仪器设备Cfree三、实验内容和原理2.实习题1问题描述编写程序实现下面运算:在二叉排序树中查找关键字为key的记录。输入排序二叉树，以及要查找的数字（节点）。输出显示该节点是否存在。存储结构有序表采用顺序方式存储。算法的基本思想若二叉排序树为空树，查找失败，返回null或0；否则，将key与根节点的关键字比较： 若key=根节点的关键字，查找成功； 若key根节点的关键字，继续在右子树中查找。参考源程序#include stdio.h#define NULL 0typedef int KeyType;typedef stru

2、ct KeyType key; ElemType; /元素类型typedef struct BiTNodeElemType 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 （keydata.key） retur

3、n searchBST（bt-lchild,key）; else return searchBST（bt-rchild,key）;void insertBST（BiTree *bt,BiTree s）/*在二叉排序树中插入一个新结点,即依次插入输入的数*/ if （*bt=NULL） *bt=s; else if （s-data.keydata.key） insertBST（&（*bt）-lchild）,s）;data.keyrchild）,s）;main（） char ch; BiTree bt,s; int i=0;/*建立一棵二叉排序树，元素从键盘按先序输入，直到输入关键字等于-1为止*

4、/ 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）; else printf（n没有找到!n是否继续?（y/n）：%cch）; ch=getchar（）; while （ch=y | ch=Y） ; getchar（）;/main实验结果：