数据结构：查找子系统

/**题目编写循序查找程序编写二分查找程序编写建立二叉排序树的程序编写在二叉排序树上的查找、输入、删除结点的程序编写二叉排序树的中序输出的程序设计一个选择式菜单，一级菜单形式如下查找子系统5^Cjjcjjc5|C^|C顺序查找1——二分查找2——二叉排序树3—返回*0——sjcS^CS^C3^CS^CsjcSjCSjCsjcsjc3^C|CSjCjjc3jC3^CSjCSjCSjC请选择菜单号

（一）03二叉排序树的二级菜单如下二叉排序树更新二叉排序树*1查找结点2插入结点34删除结点5中序输出排序树*0返回*请选择菜单号（）0—5*/stdio.he stdio.hstring.h string.hstdlib.h stdlib.h#define SEARCHMAX30typedef struct node〃根节点int trData;〃左子树struct node*lchild;〃右子树structnode*rchild;}BtNode,*pBtNode;void seqSearch;void binSearch;void btSearch;pBtNode createBT;void searchBTpBtNode T,int k;void insBTpBtNode*T,int k;void delBTpBtNode*T,int k;void inorderBTpBtNode T;void mainintchoice,k=1;while k查找子系统printf\n\n;printf\n;printfn*1----顺序查找*\nH；printf*2-----------二分查找*\nH;二叉排序树；printf*3-----------*\n返回printf*0-----------*\n;printf printf请选择菜单号0-3;\n;fflushstdin;scanf%d,choice;switchchoicecase1:seqSearch;break;case2:binSearch;break;case3:btSearch;break;case0:k=0;break;default:输入错误，请重新输入;printfgetchar;k=1;break;}}〃顺序查找void seqSearchinta[SEARCHMAX],x,y,i;char ch;“建立一个整数的顺序表以结束”;printf-1for i=0;iSEARCHMAX;i++，scanf%d“a[i];getchar;〃记录结束位置，结束循环ifa[i]==-ly=i;break;}}是否需要查找printf Y/N;scanf%c,ch;while ch==y||ch==Y请输入要查找的数据:printf\n;scanf%d,x;getchar;〃找到数组的结束位置i=0;〃找到要查找的数据的位置while iy-la[i]!=x i++;}〃没找到if i==-1{对不起,没有找到printf\n;}else该数据在第％个位置上printf1\n,i+1;是否继续查找printf Y/N;scanf%c,ch;}〃二分查找void binSearchintb[SEARCHMAX],i,y,x,low,mid,high,n;char ch;建立递增有序的查找顺序表以结束printf-1\n;for i=0;iSEARCHMAX;i++，scanf%d”b[i];getchar;〃记录结束位置，结束循环ifb[i]==-ly=i;break;}}是否需要查找printf Y/N;scanf%c,ch;while ch==y||ch==Y请输入要查找的数据”；printfscanf%d,x;getchar;〃低low=0;〃高high=y-1;〃记录次数n=0;while low=highmid=low+high/2;n++;〃在左边if b[mid]xhigh=mid-1;〃在右边else if b[mid]xlow=mid+1;〃找到elsebreak;}if lowhigh对不起，没有找到该数据；printf\n共进行％次比较printf d\n,n;〃查找最后小于该数据的位置ifb[mid]xmid++;}可将此数据插入第个％位置，printf dmid+1;}elseprintf找到该数据在第％€个位置\nH,mid+1;共进行％次比较printf d\n,n;是否需要查找printf Y/N;scanf%c,ch;}〃二叉排序树void btSearchintchoice,x,I=1;pBtNodeT;建立一棵二叉排序树存储printf\n“;T=createBT;getchar;while I二叉排序树printf\n\n“;printf\nH;更新二叉排序树printf*1-----*\n;printf*2-----查找结点*\nH;插入结点printf*3-----*\n;删除结点printf*4-----*\n;中序输出排序树printf*5-----*\n;返回printf*0-----------*\n;printf\nH;请选择菜单号printf0-5;fflushstdin;scanf%d,choice;switchchoicecase1:T=createBT;break;case2:1请输入要查找的数据;printf，scanf%d“x;getchar;searchBTT,x;break;case3:1请输入要插入的数据;printfscanfH%d,x;insBTT,x;break;请输入要删除的数据;printfscanf%d,x;delBTT,x;break;case4:inorderBTT;break;case0:I=0;break;default:输入错误，请重新输入”；printfgetchar;I=1;break;}}}〃建立二叉树pBtNode createBT〃声明指针pBtNodeT;int x;T=NULL;“请输入一个整数输入结束;printf0fflushstdin;scanfC^d,x;getchar;〃输入的数据非零时while x〃二叉树中插入数据insBTT,x;“请输入下一个整数输入结束”;printf0fflushstdin;，scanf“%d“x;getchar;}〃返回指针return T;〃查找二叉树结点void searchBTpBtNodeT,int kpBtNodef=T;while f〃判断是否找到该数据iff-trData==k已找到数据printf\n;return;}〃判断下一个查找的位置f=kf-trData f-lchild:f-rchild;没有找到数据printf\n;〃插入二叉树结点void insBTpBtNode*T,int kpBtNodef,p;；〃指向指针的指针P=*T〃当结点不为空while pif p-trData==k树中已有％不需要插入printf d,,k;return;else|二fp;〃判断插入的数据的位置p=kp-trDatap-lchild:p-rchild;}〃分配空间p=BtNode*mallocsizeofBtNode;p-trData=k;p-lchild=p-rchild=NULL;if*T==NULL；*T=p}elseif kf-trDataf-lchild=p;}elsef-rchild=p;}}〃删除二叉树结点void delBTpBtNode*T,int kpBtNodep,q,child,parent=NULL;P=*T;〃找到输入的数据的位置while pif p-trData==kbreak;}〃记录上一个结点parent=p;p=kp-trDatap-lchild:p-rchild;}〃没有找到位置if!p没有找到你要删除的数据结点printf\n;return;}；q=Pif q-lchildq-rchildfor parent=q,p=q-rchild;p-lchild;parent=p,p=p-lchild}〃下一个指针的指向child=p-lchildp-lchild:p-rchild;if!parent*T=child;}elseif p==parent-lchild{parent-lchild=child;}elseparent-rchild=child;}ifp!=qq-trData=p-trData;}freep;〃中序遍历二叉树void inorderBTpBtNodeT ifT!=NULLinorderBTT-lchild;printf%5d,T-trData;inorderBTT-rchild;}。