1305120411-何彬-实验报告09

计算机科学与工程学院《算法与数据结构》实验报告(九)专业班级2013网络工程01实验地点423机房学生学号指导教师赵卿松学生姓名实验时间实验项目查找技术综合应用实验类别基础性（）设计性（√）综合性（）其它（）实验目的及要求（1）熟练掌握查找的常用算法；（2）设计和应用查找算法解决比较简单的实际问题。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师：赵卿松日期：2015年6月13日计算机科学与工程学院《算法与数据结构》实验报告2实验内容实验内容：二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：二叉排序树插入算法伪代码如下：二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：typedefstructBiTNode{//结点结构structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;1.若root是空树，则将结点s作为根结点插入；否则2.若s-data＜root-data，则把结点s插入到root的左子树中；否则3.把结点s插入到root的右子树中。1.若结点p是叶子，则直接删除结点p；2.若结点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；计算机科学与工程学院《算法与数据结构》实验报告3实验内容#includestdio.h#includestdlib.h#includeconio.h#defineMax100typedefintKeyType;typedefstructnode{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;计算机科学与工程学院《算法与数据结构》实验报告4elseif(kp-key)returnInsertBST(p-lchild,k);elsereturnInsertBST(p-rchild,k);}BSTNode*CreateBST(KeyTypeA[],intn)//创建二叉排序树{BSTNode*bt=NULL;inti=0;while(in){InsertBST(bt,A[i]);i++;}returnbt;}BSTNode*SearchBST(BSTNode*bt,KeyTypek)//{if(bt==NULL||bt-key==k)returnbt;if(kbt-key)returnSearchBST(bt-lchild,k);elsereturnSearchBST(bt-rchild,k);计算机科学与工程学院《算法与数据结构》实验报告5}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\n,k);elseprintf(找不到该元素\n);}voidshuru(BSTNode*&e,int&n){计算机科学与工程学院《算法与数据结构》实验报告6system(cls);//清屏intm,a[Max]={0},i;printf(请输入二叉排序树中元素的个数：\n);scanf(%d,&m);n=m;for(i=0;in;i++){printf(请输入二叉排序树的第%d个元素的个数：,i+1);scanf(%d,&a[i]);}e=CreateBST(a,n);}voidprint1(BSTNode*b){if(b!=NULL){print1(b-lchild);printf(%d,b-key);print1(b-rchild);}}voidprint(BSTNode*b){计算机科学与工程学院《算法与数据结构》实验报告7system(cls);//清屏print1(b);}intDeleteBST(BSTNode*&T,intx){//从二叉树排序树T中删除任意结点,其关键字为xBSTNode*p,*q,*pParent,*pChileNode;p=T;//从根结点开始查找pParent=NULL;//T的双亲为NULLwhile(p)//开始查找关键字为x的结点p,及双亲pParent{if(x==p-key)break;pParent=p;p=xp-key?p-rchild:p-lchild;}if(p==NULL){printf(要删除的结点不存在\n);return0;}//至此已找到目标结点p//pChileNode=p存在的孩子或NULL,左右都存在时，取左pChileNode=p-lchild!=NULL?p-lchild:p-rchild;if(p-lchild==NULL||p-lchild==NULL)计算机科学与工程学院《算法与数据结构》实验报告8{if(pParent==NULL)T=pChileNode;else{if(p==pParent-lchild)pParent-lchild=pChileNode;elsepParent-rchild=pChileNode;}free(p);//释放空间}//当2个孩子都存在时else{//pChileNode已指向p-lchildq=p;while(pChileNode-rchild){//在p的左字树中查找中序p的前驱pChileNode，q为其双亲q=pChileNode;pChileNode=pChileNode-rchild;}p-key=pChileNode-key;//p的前驱pChileNodede的关键值赋给pif(q!=p)//将删除p转化为删除pChileNodede(最多只有左子树)结点{q-rchild=pChileNode-lchild;//p的左子树有右孩子计算机科学与工程学院《算法与数据结构》实验报告9}else{q-lchild=pChileNode-lchild;//p的左子树有右孩子}free(pChileNode);}return1;}voidshanchu(BSTNode*&bt){system(cls);//清屏intk,i;printf(请输入你要查找的元素);scanf(%d,&k);i=DeleteBST(bt,k);if(i==0)printf(删除不成功！\n);elseprintf(删除成功！\n);}voidmenu(){计算机科学与工程学院《算法与数据结构》实验报告10system(cls);//清屏printf(\n********************************菜单**********************************\n\n);chara[50]=1.输入二叉排序树;charb[50]=2.查找;charc[50]=3.删除;chard[50]=4.插入;chare[50]=5.显示;charf[50]=6.退出;printf(\t%-35s%-35s\n\n\t%-35s%-35s\n\n\t%-35s%-35s\n\n,a,b,c,d,e,f);printf(********************************************************************************\n);printf(请选择你要执行的操作对应的序号：\n);}voidmain(){intn;inta[Max]={0};printf(----------------------------二叉排序树----------------------------\n\n);printf(\t本程序可以实现对一组数据进行查找、插入、删除等操作。\n\n);BSTNode*e=NULL;}for(;;)/*无限循环*/{计算机科学与工程学院《算法与数据结构》实验报告11printf(按任意键进入主菜单。);getch();menu();/*显示菜单*///intn;inti=100;/*初始化*/fflush(stdin);/*清空输入缓冲区*/scanf(%d,&i);if(i=0&&i=6){switch(i){case1:shuru(e,n);break;/*输入记录*/case2:chazhao(e);break;case3:shanchu(e);break;case4:charu(e);break;case5:print(e);break;case6:exit(0);/*退出*/}}else{printf(不要乱按!!!\n);}}实验内容计算机科学与工程学院《算法与数据结构》实验报告12计算机科学与工程学院《算法与数据结构》实验报告13计算机科学与工程学院《算法与数据结构》实验报告14计算机科学与工程学院《算法与数据结构》实验报告15实验总结计算机科学与工程学院《算法与数据结构》实验报告16