何彬实验报告.doc

《何彬实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学与工程学院《算法与数据结构》实验报告(九)专业班级2013网络工程01实验地点423机房学生学号指导教师赵卿松学生姓名实验时间实验项目查找技术综合应用实验类别基础性（）设计性（√）综合性（）其它（）实验目的及要求（1）熟练掌握查找的常用算法；（2）设计和应用查找算法解决比较简单的实际问题。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：赵卿松日期：2015年6月13日实验内容实验内容：二叉排序树。任意给定一组数据，设计一个算法

2、，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：typedefstructBiTNode{//结点结构structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;二叉排序树插入算法伪代码如下：1.若root是空树，则将结点s作为根结点插入；否则2.若s->data＜root->data，则把结点s插入到root的左子树中；否则3.把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1.若结点p是叶子，则直接删除结点p；2.

3、若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则只需重接p的右子树；3.若结点p的左右子树均不空，则3.1查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2将结点s数据域替换到被删结点p的数据域；3.3若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4删除结点s；实验内容#include#include#include#defineMax100typedefintKeyType;typedefst

4、ructnode{KeyTypekey;structnode*lchild,*rchild;}BSTNode;intInsertBST(BSTNode*&p,KeyTypek)//插入关键字为k的结点{if(p==NULL){p=(BSTNode*)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;return1;}elseif(k==p->key)return0;elseif(kkey)returnInsertBST(p->lchild,k);elsereturnInse

5、rtBST(p->rchild,k);}BSTNode*CreateBST(KeyTypeA[],intn)//创建二叉排序树{BSTNode*bt=NULL;inti=0;while(i

6、

7、bt->key==k)returnbt;if(kkey)returnSearchBST(bt->lchild,k);elsereturnSearchBST(bt->rch

8、ild,k);}voidcharu(BSTNode*&bt){KeyTypen;printf("请输入你要插入的元素：");scanf("%d",&n);InsertBST(bt,n);}voidchazhao(BSTNode*bt){system("cls");//清屏intk;BSTNode*a;printf("请输入要查找的元素：");scanf("%d",&k);a=SearchBST(bt,k);if(a!=NULL)printf("找到了元素%d",k);elseprintf("找不到该元素");}voidshuru(BSTN

9、ode*&e,int&n){system("cls");//清屏intm,a[Max]={0},i;printf("请输入二叉排序树中元素的个数：");scanf("%d",&m);n=m;for(i=0;ilchild);printf("%d",b->key);print1(b->rchild);}

10、}voidprint(BSTNode*b){system("cls");//清屏print1(b);}intDeleteBST(BSTN