折半查找和二叉排序树.docx
- 文档编号:18609376
- 上传时间:2023-08-20
- 格式:DOCX
- 页数:14
- 大小:16.52KB
折半查找和二叉排序树.docx
《折半查找和二叉排序树.docx》由会员分享,可在线阅读,更多相关《折半查找和二叉排序树.docx(14页珍藏版)》请在冰点文库上搜索。
折半查找和二叉排序树
折半查找和二叉排序树
一、实验目的
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
#include
typedefstructBiTNode
{
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);
else
printf("查找失败!
!
!
\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(key high=mid-1; else low=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(m { 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(elem Search_CH(T->lchild,elem,T,p); else Search_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(elem p->lchild=s; else p->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(elem p=p->lchild; else p=p->rchild; } if(! p) { printf("查找失败,删除失败! ! ! \n"); returnT; } if(! (p->lchild)) { if(! q) T=p->rchild; elseif(q->lchild==p) q->lchild=p->rchild; else q->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; else f->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); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 折半 查找 二叉排序树