二叉排序树的实现.docx

目录1、设计内容22、概要设计21.1 所需模块21.2 功能模块关系图23 .算法描述31 .1模块流程图33 . 2各模块代码41.1.1 1主函数菜单模块 41.1.2 查找模块51.1.3 插入模块51.1.4 中序遍历模块51.1.5 删除模块64 .运行结果及算法分析71 .1运行结果74 . 2算法分析95 .实验心得96 .程序代码107 .参考资料12K设计内容用二叉链表为存储结构1）以回车（'n'）为输入结束标志,输入数列L,生成一棵二叉排序树T;2）对二叉排序树T作中序遍历,输出结果；3）输入元素X,查找二叉排序树T,假设存在含X的结点,那么删除该结点,并作中 序遍历（执行操作；否那么输出信息“无x .2、概要设计2. 1所需模块根据程序功能,确定所需模块如下:1）主函数菜单模块；2）查找模块；3）插入模块；4）中序遍历模块；5）删除模块.2 . 2功能模块关系图二叉树排序树的实现主函数菜单模块删除艮一中序遍历模块-一插入模块.查找模块图1功能模块图3 .算法描述3.1 模块流程图Main()开始退出程序删除功能删除成功中序遍历功能显示相应的报错、运行结果及相应的界面.3.2.1主函数菜单模块该模块功能主要是给用户提供清楚的可操作界面，易于人机操作.并能很好 的调用其他各模块,使程序更加优化,思路更加清楚,结构更加明了，提升了程 序 的实用性.其算法如下：void main() node T=NULL;int num;int ch=O;node p=NULL;printf(',please input a list of numbers end with zero:");doscanf("%d",&num);if(!num) printf("you have finished your input!n");else insertBST(&T,num);while(num);printf("nn-the menu of the Opperationn"); *主程序菜单*/printf("n 0: exit");printf("n 1: inorder travel the tree");printf("n 2: delete");while(ch=ch)printf("n choose the opperation to continue:");scanf("%d",ch);switch(ch)case O: exit(O); *0退出 */case 1: printf(" The result of the inorder traverse is:n ");inorderTraverse(<fcT); *1 中序遍历*/break;case 2: printf(,' Please input the number you want to delete:");scanf("%d",&num); *3删除某个结点 */if(scarchBST(T,num,NULL,(fep)T=Delete(T,num);printf(" You have delete the number successfulIy !n ");inordcrTraverse(<feT);)else PrintfC No node %d you want to delete! ",num);break;default: printf("Your input is wrong!please input again!n");break;*输入无效字符*/3. 2. 2查找模块该模块是给用户提供查找功能.其查找过程是：假设二叉排序树为空,那么查 找 失败,结束查找,返回信息NULL;否那么,将要查找的值与二叉排序树根结点的 值进行比拟,假设相等,那么查找成功,结束查找,返回被查到结点的地址,假设不 等，那么根据要查找的值与根结点值的大小关系决定是到根结点的左子树还是右 子树 中继续查找(查找过程同上)，直到查找成功或者查找失败为止.其算法如下:searchBST(node t,int key,node f,node *p)/* 查找函数*/(if(!t) *p=f;return (0);/*查找不成功率/else if(key=t->data) (*p=t;retum (1);/*查找成功*/else if(key<t->data) searchBST(t->lchild,key,t,p);/*在左子树中继续查找*/else searchBST(t->rchild,key,t,p);/*在右子树中继续查找*/)4. 2. 3插入模块在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定 义.插入过程:假设二叉排序树为空,那么待插入结点*p作为根结点插入到空树中； 当非空时,将待插结点关键字p->item和树根关键字t-> item进行比拟,假设 p->item = t-> item,那么无须插入,假设p-> item < t-> item,那么插入到根的 左子 树中，假设p->item > t-> item,那么插入到根的右子树中.而子树中的插 入过程 和在树中的插入过程相同,如此进行下去,直到把结点*p作为一个新的树 叶插 入到二叉排序树中，或者直到发现树已有相同关键字的结点为止.其算法如 下：insertBST(node *t,int 卜必丫)/*插入函数*/(node p=NULL,s=NULL;if(!searchBST(*l,key,NULL,&p) /*查找不成功*/ s=(node)malloc(sizeof(BSTnode);s->data=key;s->lchild=s->rchild=NULL;if(!p) *t=s;信被插结点*s为新的根结点*/else if(key<p->data) p->lchild=sj*被插结点*s 为左孩子*/else p->rchild=s; /*被插结点*s 为右孩子*/ return (I);else return (0);/*树中已有关键字相同的结点,不再插入*/)5. 2. 4中序遍历模块遍历(TraVerSal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅 做一次访问.访问结点所做的操作依赖于具体的应用问题.二叉树共有三个部 分 组成,即根结点,根结点的左子树,根结点的右子树.限定以从左至右方式共 有三种遍历方式,即前序遍历,中序遍历,后序遍历.中序遍历的原那么：假设被遍历的 二叉树为非空,那么依次执行如下操作：a)以中序遍历方式遍历左子树；b)访问根结点；C)以中序遍历方式遍历右子树.其算法如下：inorderTraverse(node *t)/*中序遍历 函数*/if(*t)if(inorderTraverse(<fe(*t)->lchild)/* 中序遍历根的左子树 */printf("%d ",(*t)->data); /*输出根结点*/if(inorderTraverse(<fe(*l)->rchild);/*中序遍历根的右子树*/ re(um(l);)6. 2. 5删除模块删除模块：删除结点函数,采用边查找边删除的方式.如果没有查找到，那么不对 树做任何的修改；如果查找到结点,那么分四种情况分别进行讨论： a)该结点左右子树均为空,可以直接进行删除；b)该结点仅左子树为空,右子树不为空,用右子树的根结点取代被删除结 点 的位置；c)该结点仅右子树为空,左子树不为空；d)该结点左右子树均不为空,找到被删除结点右子树中值的最小的结点，并 用该结点取代被删除节点的位置.其算法如下：node Delete(node t,int key) /*删除函数*/ node p=t,q=NULL,s,f;while(p! =NULL) /* 查找要删除的点*/ if(p->data=key) break; q=p; if(p->data>key) p=p->lchild; else p=p->rchild;if(p=NULL) return t; /*查找失败*/if(p->lchild=NULL)*p指向当前要删除的结点*/ if(q=NULL) t=p->rchild; *q 指向要删结点的父母*/else if(q->lchild=p) q->lchild=p->rchild; *p 为 q 的左孩子*/else q->rchild=p">rchild;/*P 为 q 的右孩子*/ free(p);else(*p的左孩子不为空*/f=p；s=p->lchild;WhiIe(S->rchild) /*左拐后向右走到底*/f=s;s=s->rchild;if(f=p) f->lchild=s->lchild; 重接 f 的左子树*/else f->rchild=s->lchild;/*重接 f 的右子树*/p->data=s->data;free (s); return t;7. 运行结果及算法分析7.1 运行结果目输入串叔字并以向'结束二卫23 * 56 78灯后 尔己经输入莞毕;匚|建输入一车数字舁R,4结束二12 " *bb i '18yDri7WWVr7主程序菜单一一乍 r L)6乍槃eO果图4中序排列效果S节：等屣文件夹Debug二叉律序冏的实现.果"主程序菜单-一89是数8 7 白BvU T：是:2除 粉作果56作删 罚i操要 个性45个相 a±薄-用23-l23怪 州选序选 ;葬12蓼1鼠?8作*个图5删除成成效果 图百锄人车数手并以 S 结来：12兀 叫56关 而 修 你L,纣输八:图6删除不成成效果图4 . 2算法分析假设二叉树有n个结点深度为h,中序遍历算法的时间复杂度为0(n),空间 复杂度为0(h).5 .实验心得课程设计是培养学生综合运用所学知识，发现提出分析和解决实际问题,锻 炼实践水平的重要环节，是对学生实际水平的具体练习和考察过程.回忆数据设 计这些日子，至今我感慨颇多，确实，学到了很多的东西包括以前在课本上没有 学到的知识,还使我懂的了理论和时间结合是很重要通过这次课程设计,我加深了对数据结构这门课程的理解，更好的掌握了各 种二叉数的递归与非递归，树与二叉树的转换.以及树的中序的递归，非递归算 法,层次序的非递归算法的实现,更稳固了自己的C和C+的知识.在老师的指导、书本上和网络上查找资料下，终于把程序编出来,在此非常 感谢老师对我的指导.6 .程序代码#includc<stdio.h># include<stdlib.h> typedef struct Tnode 产输入的数据*/*结点的左右指针,分别指向结点的左右孩子*/int data;struct Tnodc *lchild,*rchild;*node,BSTnode;searchBST(nodc t,int key,nodc f,nodc *p) /*查找函数*/ if(!t) *p=f;return (0);)/*查找不成功*/else if(key=t->data) *p=l;retum (1); /*查找成功*/else if(key<t->data) searchBST(t->lchild,key,t.p);/*在左子树中继续查找*/elsesearchBST(t->rchiId,key,(,); /* 在右子树中继续查找 */IinsertBST(node *tjnt 卜©丫)/*插入函数*/ (node P=NULL,s=NULL;(s=(node)malloc(sizeof(BSTnode);s->data=key;s->lchild=s->rchild=NULL;if(!p) *t=s;/*被插结点*s为新的根结点*/else if(key<p->data)p->lchild=sj*被插结点*s 为左孩子*/else p->rchild=s; /*被插结点*s为右孩子*/return (1);)else return (0);/*树中已有关键字相同的结点,不再插入*/ inordcrTraverse(nodc *t) /* 中序遍历函数*/(if(*t)(if(inordcrTraverse(<,(*t)->lchild)/* 中序遍历根的左子树 */printf("%d ",(*t)->data); /*输出根结点*/if(inordcrTraverse(*t)->rchild); /* 中序遍历根的右子树*/ )return(1);)node Delete(node t.int key) /*删除函数*/node p=t,q=NULL,s,f;while(p!=NULL)/*查找要删除的点*/(if(p->data=key) break;q=p;if(p->data>key) p=p->lchild;else p=p->rchild;)if(p=NULL) return t; /*查找失败*/if(p->lchild=NULL) *p指向当前要删除的结点*/ if(q=NULL) t=p->rchild; *q 指向要删结点的父母*/else if(q->lchild=p) q->lchild=p->rchild; *p 为 q 的左孩子*/ else q->rchild=p->rchild*p 为 q 的右孩子*/free(p); else*p的左孩子不为空*/f=p；s=p->lchild;while(s->rchild)/*左拐后向右走到底*/(f=s; s=s->rchild; if(f=p) f->lchild=s->lchild; /*重接 f 的左子树 else f->rchild=s->lchild;/*重接 f 的右子树*/p->data=s->data;free (s); return t;void main() node T=NULL;int num;int ch=0;node p=NULL;printf("please input a list of numbers end with zero:"); do scanf("%d"num);if(!num) printf("you have finished your input!n");else insertBST(&T,num);while(num);printf("nn-the menu of the opperation一n"); *主程序菜单*/printf("n 0: exit");printf("n 1: inorder travel the tree");printf("n 2: delete");while(ch=ch)rintf("n choose the Opperation to continue:");scanf("%d"ch);switch(ch)case O: exit(O); *0退出 */case 1: printf(" The result of the inorder traverse is:n ,);inorderTraverse(4feT); *1中序遍历 */ break;case 2: PrintfPlease input the number you want to delete:'1);scanf("%d",&num); *3删除某个结点 */if(searchBST(T,num,NULL,&p)(T=Delete(T,num);printf(" You have delete the number successfully!n ");inorderTraverse(&T);else printf(,* No node %d you want to delete! ",num);break;default: printf("Your input is wrong !please input again !n");break;*输入无效字符*/7.参考资料?数据结构教程？（第二版）唐发根编著北京航空航天大学出版社