折半查找和二叉排序树

折半查找和二叉排序树一、实验目的1、掌握查找的特点。2、掌握折半查找的基本思想及其算法。3、熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作。二、实验内容1、设有关键字序列k={5,14,18,21,23,29,31,35}，查找key=21和key=25的数据元素。2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树，并完成插入13删除关键字53和24的操作。三、实验环境TC或VC++或Java四、实验步骤1、折半查找（1）从键盘输入上述8个整数5,14,18,21,23,29,31,35，存放在数组bub[8]中，并输出其值。（2）从键盘输入21，查找是否存在该数据元素，若存在，则输出该数据元素在表中的位置，否则给出查找失败的信息。（3）从键盘输入25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。2、二叉排序树（1）二叉排序树存储定义（2）从键盘上输入六个整数45、24、53、12、37、9构造二叉排序树（3）输出其中序遍历结果。（4）插入数据元素13，输出其中序遍历结果。（5）删除数据元素24和53，输出其中序遍历结果。五、问题讨论1、折半查找递归算法该怎么描述？2、二叉排序树中序遍历结果有什么特点？3、在二叉树排序树中插入一个新结点，总是插入到叶结点下面吗？4、在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同吗？六、实验报告内容1、实验目的2、实验内容和具体要求3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法4、程序清单5、所输入的数据及相应的运行结果6、问题回答7、实验心得实验代码：#includestdio.h#includestdlib.htypedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;intbub[100];voidmenu(){printf(********主目录*******\n);printf(折半或顺序查找1\n);printf(二叉排序树2\n);printf(结束程序0\n);printf(*********************\n);}voidmenu1(){printf(*******目录①*******\n);printf(输出元素1\n);printf(顺序查找2\n);printf(折半查找3\n);printf(结束此查找0\n);printf(********************\n);}voidmenu2(){printf(**********目录②*********\n);printf(输出树的中序遍历结果1\n);printf(插入数据元素2\n);printf(删除数据元素3\n);printf(结束二叉排序0\n);printf(*************************\n);}voidSearch(){inti,m,n,key,k;printf(输入元素个数：);scanf(%d,&m);printf(依次输入元素：);for(i=1;i=m;i++){scanf(%d,&bub[i]);}printf(输入关键字：);scanf(%d,&key);bub[0]=key;do{menu1();printf(选择查找方式：);scanf(%d,&n);switch(n){case1:for(i=1;i=m;i++){printf(%d,,bub[i]);}printf(\n);break;case2:for(i=m;i=0;i--){if(bub[i]==key){if(i!=0){printf(查找的数据元素在第%d位！\n,i);break;}else{printf(查找失败！！！\n);}}}break;case3:k=Search_Bin(m,key);if(k!=0)printf(查找的数据元素在第%d位！\n,k);elseprintf(查找失败！！！\n);break;case0:printf(查找结束！！！\n);break;default:printf(选择错误！！！\n);}}while(n!=0);}intSearch_Bin(intm,intkey){intlow,high,mid;low=1;high=m;while(low=high){mid=(low+high)/2;if(key==bub[mid])returnmid;elseif(keybub[mid])high=mid-1;elselow=mid+1;}return0;}BiTreeInsert(){BiTreeT=NULL,q=NULL,p=NULL;intm;printf(输入数据(-10000停止输入)：);scanf(%d,&m);while(m!=-10000){q=(BiTree)malloc(sizeof(BiTNode));q-data=m;q-lchild=q-rchild=NULL;if(!T)T=q;else{p=T;while(1){if(mp-data){if(p-lchild==NULL){p-lchild=q;break;}p=p-lchild;}else{if(p-rchild==NULL){p-rchild=q;break;}p=p-rchild;}}}scanf(%d,&m);}returnT;}voidInorder(BiTreeT){if(T){Inorder(T-lchild);printf(%d,,T-data);Inorder(T-rchild);}}intSearch_CH(BiTreeT,intelem,BiTreef,BiTree*p){if(!T){*p=f;return0;}elseif(elem==T-data){*p=T;return1;}elseif(elemT-data)Search_CH(T-lchild,elem,T,p);elseSearch_CH(T-rchild,elem,T,p);}BiTreeInsertBST(BiTreeT,intelem){BiTreep=NULL,s=NULL;if(!Search_CH(T,elem,NULL,&p)){s=(BiTree)malloc(sizeof(BiTNode));s-data=elem;s-lchild=s-rchild=NULL;if(!p)T=s;elseif(elemp-data)p-lchild=s;elsep-rchild=s;printf(插入成功！！！\n);returnT;}printf(输入已有元素，插入失败！！！\n);returnT;}BiTreeDelete(BiTreeT,intelem){BiTreep=NULL,q=NULL,f=NULL,s=NULL;p=T;while(p){if(elem==p-data)break;q=p;if(elemp-data)p=p-lchild;elsep=p-rchild;}if(!p){printf(查找失败，删除失败！！！\n);returnT;}if(!(p-lchild)){if(!q)T=p-rchild;elseif(q-lchild==p)q-lchild=p-rchild;elseq-rchild=p-rchild;free(p);}else{f=p;s=p-lchild;while(s-rchild){f=s;s=s-rchild;}if(f==p)f-lchild=s-lchild;elsef-rchild=s-lchild;p-data=s-data;free(s);}printf(删除成功！！！\n);returnT;}voidErChaPaiXu(){BiTreeT;intm,key;T=Insert();do{menu2();printf(输入你的选择：);scanf(%d,&m);switch(m){case1:printf(中序遍历结果为：);Inorder(T);printf(\n);break;case2:printf(输入要插入的元素：);scanf(%d,&key);T=InsertBST(T,key);break;case3:printf(输入要删除的元素：);scanf(%d,&key);T=Delete(T,key);break;case0:printf(结束二叉排序！！！\n);break;default:printf(输入错误！！！\n);}}while(m!=0);}voidmain(){intm;do{menu();printf(输入你的选择：);scanf(%d,&m);switch(m){case1:Search();break;case2:ErChaPaiXu();break;case0:printf(程序已结束！！！\n);break;default:printf(输入错误！！！\n);}}while(m!=0);}