折半查找和二叉排序树一、实验目的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、实验心得实验代码：#include<stdio.h>#include<stdlib.h>typedef struct BiTNode{int data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int bub[100];void menu(){printf("********主目录*******\n");printf(" 折半或顺序查找1\n");printf(" 二叉排序树2\n");printf(" 结束程序0\n");printf("*********************\n");}void menu1(){printf("*******目录①*******\n");printf(" 输出元素1\n");printf(" 顺序查找2\n");printf(" 折半查找3\n");printf(" 结束此查找0\n");printf("********************\n");}void menu2(){printf("**********目录②*********\n");printf("输出树的中序遍历结果1\n");printf(" 插入数据元素2\n");printf(" 删除数据元素3\n");printf(" 结束二叉排序0\n");printf("*************************\n"); }void Search(){int i,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){case 1:for(i=1;i<=m;i++){printf("%d,",bub[i]);}printf("\n");break;case 2:for(i=m;i>=0;i--){if(bub[i]==key){if(i!=0){printf("查找的数据元素在第%d位！\n",i);break;}else{printf("查找失败\n");}}}break;case 3:k = Search_Bin(m,key);if(k!=0)printf("查找的数据元素在第%d位！\n",k);elseprintf("查找失败\n");break;case 0:printf("查找结束\n");break;default:printf("选择错误\n");}}while(n!=0);}int Search_Bin(int m,int key){int low,high,mid;low = 1;high = m;while(low<=high){mid = (low+high)/2;if(key==bub[mid])return mid;else if(key<bub[mid])high = mid-1;elselow = mid+1;}return 0;}BiTree Insert(){BiTree T=NULL,q=NULL,p=NULL;int m;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(m<p->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);}return T;}void Inorder(BiTree T){if(T){Inorder(T->lchild);printf("%d,",T->data);Inorder(T->rchild);}}int Search_CH(BiTree T,int elem,BiTree f,BiTree *p) {if(!T){*p = f;return 0;}else if(elem==T->data){*p = T;return 1;}else if(elem<T->data)Search_CH(T->lchild,elem,T,p);elseSearch_CH(T->rchild,elem,T,p);}BiTree InsertBST(BiTree T,int elem){BiTree p=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;else if(elem<p->data)p->lchild = s;elsep->rchild = s;printf("插入成功\n");return T;}printf("输入已有元素，插入失败\n");return T;}BiTree Delete(BiTree T,int elem){BiTree p=NULL,q=NULL,f=NULL,s=NULL;p = T;while(p){if(elem == p->data)break;q = p;if(elem <p->data)p = p->lchild;elsep = p->rchild;}if(!p)printf("查找失败，删除失败\n");return T;}if(!(p->lchild)){if(!q)T = p->rchild;else if(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");return T;}void ErChaPaiXu(){BiTree T;int m,key;T = Insert();domenu2();printf("输入你的选择：");scanf("%d",&m);switch(m){case 1:printf("中序遍历结果为：");Inorder(T);printf("\n");break;case 2:printf("输入要插入的元素：");scanf("%d",&key);T = InsertBST(T,key);break;case 3:printf("输入要删除的元素：");scanf("%d",&key);T = Delete(T,key);break;case 0:printf("结束二叉排序\n");break;default:printf("输入错误\n");}}while(m!=0);}void main(){int m;do{menu();printf("输入你的选择：");scanf("%d",&m);switch(m){case 1:Search();break;case 2:ErChaPaiXu();break;case 0:printf("程序已结束\n");break;default:printf("输入错误\n");}}while(m!=0);}。
