/**题目：编写循序查找程序*编写二分查找程序*编写建立二叉排序树的程序*编写在二叉排序树上的查找、输入、删除结点的程序*编写二叉排序树的中序输出的程序*设计一个选择式菜单，一级菜单形式如下：*查找子系统************************************1------顺序查找***2------二分查找***3------二叉排序树***0------返回************************************请选择菜单号（0--3）：*二叉排序树的二级菜单如下：*二叉排序树***************************************1------更新二叉排序树***2------查找结点***3------插入结点***4------删除结点***5------中序输出排序树***0------返回***************************************请选择菜单号（0--5）：*/#include
#include#include#defineSEARCHMAX30typedefstructnode{inttrData;//根节点structnode*lchild;//左子树structnode*rchild;//右子树}BtNode,*pBtNode;voidseqSearch();voidbinSearch();voidbtSearch();pBtNodecreateBT();voidsearchBT(pBtNodeT,intk);voidinsBT(pBtNode*T,intk);voiddelBT(pBtNode*T,intk);voidinorderBT(pBtNodeT);voidmain(){intchoice,k=1;while(k){printf("\n查找子系统\n");printf("*********************************\n");printf("*1------顺序查找*\n");printf("*2------二分查找*\n");printf("*3------二叉排序树*\n");printf("*0------返回*\n");printf("*********************************\n");printf("请选择菜单号（0--3）：");fflush(stdin);scanf("%d",&choice);switch(choice){case1:seqSearch();break;case2:binSearch();break;case3:btSearch();break;case0:k=0;break;default:printf("输入错误，请重新输入。");getchar();k=1;break;}}}voidseqSearch()//顺序查找{inta[SEARCHMAX],x,y,i;charch;printf("建立一个整数的顺序表（以-1结束）：");for(i=0;ix)//在左边{high=mid-1;}elseif(b[mid]high){printf("对不起，没有找到该数据。\n");printf("共进行%d次比较。\n",n);if(b[mid]trData==k)//判断是否找到该数据{printf("已找到数据。\n");return;}f=(ktrData)?f->lchild:f->rchild;//判断下一个查找的位置}printf("没有找到数据。\n");}voidinsBT(pBtNode*T,intk)//插入二叉树结点{pBtNodef,p;p=(*T);//指向指针的指针while(p)//当结点不为空{if(p->trData==k){printf("树中已有%d，不需要插入。",k);return;}else{f=p;p=(ktrData)?p->lchild:p->rchild;//判断插入的数据的位置}}p=(BtNode*)malloc(sizeof(BtNode));//分配空间p->trData=k;p->lchild=p->rchild=NULL;if((*T)==NULL){(*T)=p;}else{if(ktrData){f->lchild=p;}else{f->rchild=p;}}}voiddelBT(pBtNode*T,intk)//删除二叉树结点{pBtNodep,q,child,parent=NULL;p=*T;while(p)//找到输入的数据的位置{if(p->trData==k){break;}parent=p;//记录上一个结点p=(ktrData)?p->lchild:p->rchild;}if(!p)//没有找到位置{printf("没有找到你要删除的数据结点。\n");return;}q=p;if(q->lchild&&q->rchild){for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild){;}}child=(p->lchild)?p->lchild:p->rchild;//下一个指针的指向if(!parent){*T=child;}else{if(p==parent->lchild){parent->lchild=child;}else{parent->rchild=child;}if(p!=q){q->trData=p->trData;}}free(p);}voidinorderBT(pBtNodeT)//中序遍历二叉树{if(T!=NULL){inorderBT(T->lchild);printf("%5d",T->trData);inorderBT(T->rchild);}}
浙公网安备 33021202002483