数据结构：查找子系统

数据结构：查找子系统

*题目：编写循序查找程序

*编写二分查找程序

♦编写建立二叉排序树的程序

*编写在二义排序树上的查找、输入、删除结点的程序

*编写二叉排序树的中序输出的程序

*设计一个选择式菜单，一级菜单形式如下：

*查找子系统

**********************************

**1……顺序查找*

**2-一一二分查找*

**3……二叉排序树*

**0-------返回*

**********************************

*请选择菜单号(0-3)：

*二叉排序树的二级菜单如下：

*二义排序树

*************************************

**1……更新二叉排序树*

**2--查找站点*

*»3——插入结点*

**4……删除结点*

**5----中序输出排序树*

*♦0——返回*

*************************************

*请选择菜单号(0--5)：

*/

stdio.he<stdio.h>

string.h<string.h>

stdlib.h<stdlib.h>

#defineSEARCHMAX30

typedefstructnode

(

inttrData;〃根节点

structnode*lchild;〃左子树

structnode*rchild;〃右子树

JBtNode,*pBtNode;

voidseqSearch();

voidbinSearchO;

voidbtSearch();

pBtNodecreateBT();

voidsearchBT(pBtNodeT,intk);

voidinsBT(pBtNode*T,intk);

voiddelBT(pBtNode*T,intk);

第1页共9页

数据结构：查找子系统

voidinorderBT(pBtNodeT);

voidmain()

intchoice,k=1;

while(k)

printf("\n查找子系统\n");

II************京*****，*****，********

printf("*1---…顺序查找*\n");

printfC*2—…二分查我*\n")；

printfC*3—一二又排序树

printfC*0—一返回

printf(”*********************************\n”).

prints请选择菜单号（0--3）："）；

fflush(stdin);

scanf("%d”,&choice);

switch(choice)

case1:

5eqSearch();

break;

case2:

binSearch();

break;

case3:

btSearch{);

break;

case0:

k=0;

break；

default:

printf("输入错误,请重新输入。")；

getchar();

k=l;

break;

)

)

)

voidseqSearchO〃顺序杳找

(

inta[SEARCHMAX],x,y,i;

charch;

printf("建立一个整数的顺序表(以-1结束)：")；

for(i=0;i<SEARCHMAX;i++)

第2页共9页

数据结构：查找子系统

scanf("%d",&a[i]);

getchar();

if(a[i]==・l)〃记录结束位置,结束循环

(

y=i;

break；

)

}

printf("是否需要查找(Y/N)：");

scanf("%c",&ch);

while(ch=='y'||ch==Y)

(

printf(“请输入要查找的数据:\n");

scanf("%d",&x);

getchar();

i=O;〃找到数组的结束位置。

while(i<y-l&&a[i]!=x)〃找到要查找的数据的位置

(

i++；

}

if(i==-1)〃没找到

(

printf("对不起,没有找到。\n");

)

else

(

printf("该数据在第％(1个位置上。\n",i+1);

)

printf("是否继续查找(Y/N)：")；

scanf(''%c",&ch);

)

)

voidbinSearch()〃二分查找

{

intb[SEARCHMAX],i,y,x,low,mid,high,n;

charch;

printf("建立递增有序的查找顺序表(以-1结束)：\n");

for(i=0;kSEARCHMAX;i++)

(

scanf("%d",&b[i]);

getchar();

if(b[i]==-l)〃记录结束位置，结束循环

第3页共9页

数据结构：查找子系统

printf("共进行％d次比较。\n';n);

)

printf("是否需要查找(Y/N)：");

scanf("%c",&ch);

}

)

voidbtSearch()〃二叉排序树

{

intchoice,x,I=1;

pBtNodeT;

printf("建立•一棵二叉排序树存储\n");

T=createBT();

getchar();

while(I)

(

printf("\n二叉排序树\n");

printf(M***********************************\i

printf("*1一一更新二叉排序树*\n");

printf("*2--.一查找结点*\n");

printf("*3——插入结点*\n"),

printf("*4一一删除结点*\n");

printf("*5-一一中序输出排序树*\n")；

printfC*0——返回♦\n")；

printf(”************************************

printf("请选择菜单号(0-5)：

fflush(stdin);

scanf("%d",&choice);

switch(choice)

(

case1:

T=createBT();

break;

case2:

printf("请愉入要查找的数据：")；

scanf("%d",&x);

getchar();

searchBT(T,x);

break;

case3:

printf(”请输入要插入的数据:")；

scanf("%d",&x);

insBT(&T,x);

break;

case4:

第5页共9页

数据结构：查找子系统

printf("请输入要删除的数据：”);

scanf("%d",&x);

delBT(&T,x);

break;

case5:

inorderBT(T);

break；

case0:

1=0;

break;

default:

printf("输入错误,请重新输入。

getchar();

1=1；

break;

)

}

)

pBtNodecreateBT()〃建立二叉树

(

pBtNodeT;〃声明指针

intx;

T=NULL;

printf("请输入一个整数(输入。结束)：

fflush(stdin);

scanf("%d",&x);

getchar();

wh加(x)〃输入的数据非零时

(

insBT(&T,x);〃二叉树中插入数据

printf("请输入下一个整数(输入0结束)：");

fflush(stdin);

scanf(”%d",&x);

getchar();

)

returnT;〃返回指针

)

voidsearchBT(pBtNodeT,intk)〃杳找二叉树结点

(

pBtNodef=T;

while(f)

(

if(f->trData==k)〃判断是否找到该数据

第6页共9页

数据结构：查找子系统

printf("已找到数据。\n");

return;

)

f=(k<f->trData)?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=(k<p->trData)?p->lchild:p->rchild;〃判断插入的数据的位置

)

}

p=(BtNode*)malloc(sizeof(BtNode));〃分配空间

p->trData=k;

p->lchild=p->rchild=NULL;

if((*T)==NULL)

(

(*T)=p；

}

else

(

if(k<f->trData)

(

f->lchild=p;

)

else

(

f->rchild=p;

)

)

)

voiddelBT(pBtNode*T,intk)〃删除二叉树结点

第7页共9页

数据结构：查找子系统

pBtNodep,q,child,parent=NULL;

P=*T；

while(p)〃找到输入的数据的位置

(

if(p->trData==k)

(

break;

)

parent=p;〃记录上一个结点

p=(k<p->trData)?p->lchild:p->rchild;

}

if(!p)〃没有找到位置

(

printf(“没有找到你要删除的数据结点。\n");

return;

}

q=P；

if(q->lchild&&q->rchil