资源描述：
《在二叉排序树中查找关键字为key的记录》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、可编辑版学院名称专业班级实验成绩学生姓名学号实验日期课程名称数据结构实验题目4查找一、实验目的与要求通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。二、主要仪器设备Cfree三、实验内容和原理2.实习题1[问题描述]编写程序实现下面运算:在二叉排序树中查找关键字为key的记录。[输入]排序二叉树，以及要查找的数字（节点）。[输出]显示该节点是否存在。[存储结构]有序表采用顺序方式存储。[算法的基本思想]若二叉排序树为空树，查找失败，返回null或0；否则，将key与根节点的关键字比较：若key=根节点的关键字，查找成功；若ke
2、y<根节点的关键字，继续在左子树中查找；若key>根节点的关键字，继续在右子树中查找。Word完美格式可编辑版[参考源程序]#include#include#defineNULL0typedefintKeyType;typedefstruct{KeyTypekey;}ElemType;//元素类型typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreesearchBST(BiTreebt
3、,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){/*在二叉排序树中插入一个新结点,即依次插入
4、输入的数*/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;Word完美格式可编辑版KeyTypekey;BiTreebt,s;inti=0;/*建立一棵二叉排序树，元素从键盘按先序输入，直到输入关键字等于-1为止*/printf("请输入元素(-1:结束)：
5、");//以-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("输入你想要查找的元素：");scanf("%d",&key);s=searchBST(bt,key);if(s!=NUL
6、L)printf("成功!这个等价元素是%d.",s->data.key);elseprintf("没有找到!");printf("是否继续?(y/n)：");scanf("%c",&ch);ch=getchar();}while(ch=='y'
7、
8、ch=='Y');getchar();}//main实验结果：Word完美格式可编辑版五、实验结果与分析（2）习题1：采用先序遍历的方式生成二叉树，程序中多次使用的递归的算法。使程序看起来很简洁。如果把头结点的生成也放到生成树的函数中，会使程序看起来更加调理。六、实验心得及
9、体会查找是很多程序的基础，很多程序中都会用到查找。比如在线性表的插入和删除时要查找合适的位置。所以学好查找是很必要的。本次实验只要是采取了这般查找的方法。其实还有很多查找的方法。如顺序查找，索引顺序表查找。每种查找方法各有优劣。如折半查找的平均查找长度小于顺序查找，但它要求查找的表为有序的。所以需将无序表排序成有序表。这又会浪费运行时间。编写程序时遇到了很多的困难，如先序生成树更好还是中序生成更好。Word完美格式可编辑版太原理工大学学生实验报告学院名称计算机科学与技术专业班级计Z1002班实验成绩学生姓名郑海兵学号2010001420实
10、验日期1月2日课程名称数据结构实验题目5内排序一、实验目的与要求通过本次实验，掌握线性表的排序方法，并分析时间复杂度。二、主要仪器设备Cfree三、实验内容和原理[问题描述]设计一个用链表表示
