构建一棵二叉排序树的C程序的设计方案.doc_第1页
构建一棵二叉排序树的C程序的设计方案.doc_第2页
构建一棵二叉排序树的C程序的设计方案.doc_第3页
构建一棵二叉排序树的C程序的设计方案.doc_第4页
构建一棵二叉排序树的C程序的设计方案.doc_第5页
已阅读5页,还剩23页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

构建一棵二叉排序树的C程序的设计方案与目标一、目的 数据结构课程设计是学习了数据结构课后的一个综合性实践环节,是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。 二、目标1、结合c和数据结构的理论知识,按要求独立设计方案,培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。 2、学会查阅资料,熟悉常用算法的用途与技巧。3、认真撰写课程设计报告,培养严谨的作风和科学态度。2.问题分析本次程序需要完成如下要求:首先输入任一组数据,使之构造成二叉排序树,并对其作中序遍历,然后输出遍历后的数据序列;其次,该二叉排序树能实现对数据(即二叉排序树的结点)的查找、插入和删除等基本操作。 实现本程序需要 解决以下几个问题:1、 如何构造二叉排序树。2、 如何通过中序遍历输出二叉排序树。3、 如何实现多种查找。4、 如何实现插入删除等操作。二叉排序树的定义:其左子树非空,则左子树上所有结点的值均小于根结点的值。若其右子树非空,则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现:输入(插入)的第一个数据即为根结点;继续插入,当插入的新结点的关键值小于根结点的值时就作为左孩子,当插入的新结点的关键值大于根结点的值时就作为右孩子;在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后,要插入新的数据时,要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此,插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前,首先要进行查找,判断给出的结点是否已存在于二叉排序树之中;在删除时,为了保证删除结点后的二叉树仍为二叉排序树,要考虑各种情况,选择正确的方法。删除操作要分几种情况讨论,在后面有介绍。3.总体设计用二叉链表作为二叉排序树的存储结构,其中key为结点关键值,*lchlid、*rchild分别为左右孩子指针。该程序的流程图所示:节点是否为0输入节点值开始N非递归查找J=22递归查找输入J=1显示删除插入查找退出I=2I=4I=3I=1I=0输入i进入主菜单Y总流程图4.具体设计首先定义二叉排序树的数据类型如下:typedef struct nodeint key;/关键字项struct node *lchild,*rchild;/左右孩子指针Bstnode;然后按一定顺序来编写算法程序:4.1递归查找算法具体思想如下:(1)若二叉树为空,则查找失败。(2)否则,将根结点的关键值与待查关键字进行比较,若相等,则查找成功;若根结点关键值大于待查值,则进入左子树重复此步骤,否则,进入右子树重复此步骤;若在查找过程的中遇到二叉排序树的叶子结点时,还没有找到待查结点,则查找不成功。if(t=NULL)return NULL;elseif(t-data=x)return t;if(xdata)return(Bsearch(t-lchild,x);elsereturn(Bsearch(t-rchild,x); 二叉排序树归查找算法流程图4.2非递归查找算法查找过程是从根结点开始逐层向下进行的。并定义一个标记量记录是否找到结点。Bstnode *searchBST(Bstnode *t,int x)Bstnode *p;int flag=0;p=t;/定义*p结点用于逐层查找,丛根结点开始查找while(p!=NULL)/二叉排序树不为空 if(p-key=x)/查找成功printf(该结点值存在!);flag=1;break;/查找不成功,到下一层继续查找 if(xkey)p=p-lchild;/查找左子树elsep=p-rchild;/查找右子树if(flag=0)printf(找不到值为%d的结点!,x);p=NULL;return p;p=p-lchild;(p-key=x)下一层?Yp=p-rchild找不到节点YN查找成功二叉排序树非递归查找算法流程图4.3插入算法从根结点开始,根据比较规则,逐一与待插入结点的值比较,查找到插入结点在二叉排序树中的未来位置,然后插入该结点。将一个关键字的值为x的结点s插入到二叉排序树中,方法如下:(1)若二叉排序树为空,则关键字值为x的结点s成为二叉排序树的根。(2)若二叉排序树非空,则将x与二叉排序树的根进行比较,如果x的值等于根结点关键字的值,则停止插入;如果x的值小于根结点关键字的值,则将x插入左子树;如果x的值大于根结点关键字的值,则将x插入右子树。在左右子树中插入方法与整个二叉排序树相同。Bstnode *InsertBST(Bstnode *t,int x)/ 插入关键值为x的元素Bstnode *s,*p,*f;/*s为待插结点,*p为逐层查找结点,*f为待插结点的父结点p=t;while(p!=NULL)f=p;/查找过程中,f指向*p的父结点if(x=p-key)/若二叉树中已有关键值为x的元素,无需插入return t;if(xkey)p=p-lchild;elsep=p-rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL)/原树为空,新结点作为二叉排序树的根return s;if(xkey)f-lchild=s;/新结点作为*f左孩子else f-rchild=s;/新结点作为*f右孩子return t;开始输入节点数n调用插入函数结束插入算法流程图4.4二叉排序树的生成算法建立二叉排序树,就是反复在二叉排序树中插入新的结点。插入的原则是如果待插入结点的值小于根结点的值,则插入到左子树中,否则插入到右子树中。大致方法是:首先建一棵空二叉排序树,然后逐个读入元素,每读入一个元素,就建一个新结点,并调用上述二叉排序树的插入算法,将新结点插入到当前已生成的二叉排序树中,最终生成一棵二叉排序树。Bstnode *CreateBST()Bstnode *t;int key;t=NULL;/设置二叉排序树的初态为空scanf(%d,&key);while(key!=endflag)t=InsertBST(t,key);scanf(%d,&key);return t;4.5中序遍历算法void Inorder(Bstnode *t)if(t!=NULL)Inorder(t-lchild);Printf(“%4dn”,t-key);Inorder(t-rchild);先遍历左孩子,再遍历父结点,最后遍历右孩子。由于是对一个二叉排序树进行中序遍历,遍历结果则是一个有序序列4.6删除算法1.待删除结点*p无左孩子,也无右孩子,则*p的父结点对应的孩子指针置空;2.待删除结点*p有左孩子,无右孩子,则*p的左孩子替代自己;3.待删除结点*p无左孩子,有右孩子,则*p的右孩子替代自己;4.待删除结点*p有左孩子,也有右孩子,本课程(数据结构与算法)给出了两种法: 方法一: 首先找到待删结点*p的前驱结点*s,然后将*p的左子树改为*p父结点的左子树,而*p的右子树改为*s的右子树: f- lchild=p-lchild; s-rchild=p-rchild; free(p); 方法二: 首先找到待删结点*p的前驱结点*s,然后用结点*s的值替代结点*p的值,再将结点*s删除,结点*s的原左子树改为*s的双亲结点*q的右子树: p-data=s-data;q-rchild=s-lchild;free(s);我采用的是第二种算法。开始s-dataT-datap=NULLNYp=ss=InserBST(T-)lchilds=InserBST(T-)rchild结束删除算法流程图4.7主函数void main()int i,j,k;Bstnode *tree,*p; system(cls);printf( 请先建立一棵二叉排序树nn);printf(输入其结点信息(输入一组正整数,当输入0时结束):n); tree=CreateBST(); printf(中序遍历的二叉排序树:n);Inorder(tree); printf(二叉排序树的根为:%dn,tree-key); for(;)switch(i=mainmenu()case 0:exit(0);case 1:switch(j=searchmenu() case 1:search_Bitree(tree);break; case 2:printf(n请输入要查找的结点的值:); scanf(%d,&k);p=searchBST(tree,k); printf(n); break; /default:printf(输入有误!); break; case 2:tree=insert_Bitree(tree);break;case 3:tree=delete_Bitree(tree);break; case 4:printf(n); printf(二叉排序树的根为:%dn,tree-key); printf(中序遍历后的序列为:n); print_Bitree(tree); printf(中序遍历的二叉排序树:n); Inorder(tree); printf(n); break; /default:printf(输入有误!);4.8注意事项:其中,某些函数顺序一定不能颠倒。例如建立二叉排序树函数一定是在插入算法之后。编写完基本操作算法后,为最后主函数的输出模块作准备,又分别写了递归查找模块、插入模块、删除模块、显示模块。5.运行环境Microsoft Visual C+ 6.0;Microsoft Word 20106.上机调试6.1语法错误及修改在编写程序时,很容易出现分号漏写和括号不匹配的现象,以及缺少返回值的问题。例如:在编写非递归查找算法时:Bstnode * searchBST (Bstnode *t,int x)Bstnode *p;int flag=0;p=t;while(p!=NULL)if(p-key=x)printf(找到了!);flag=1;return p;break;if(xkey)p=p-lchild;elsep=p-rchild;if(flag=0)printf(找不到值为%d的结点,x); return NULL;结果编译时出现了警告warning : searchBST : not all control paths return a value然后我做了改动,改后程序如下:Bstnode *searchBST(Bstnode *t,int x)Bstnode *p;int flag=0;p=t;while(p!=NULL) if(p-key=x)printf(该结点值存在!);flag=1;break; if(xkey)p=p-lchild;elsep=p-rchild;if(flag=0)printf(找不到值为%d的结点!,x);p=NULL;return p;将NULL值赋给指针p,再在程序结尾返回p,此时,编译结果就正确了!6.2程序输出调整:在递归查找算法(Bsearch)中针对查找结果如何,没有用明确的输出函数表示出来。于是我添加了一个递归查找模块如下: search_Bitree(Bstnode *t)int s;Bstnode *p;printf(n请输入要查找的结点的值:);scanf(%d,&s); if(s!=0) p=Bsearch(t,s); if(p=NULL) printf(该结点值不存在!n); else printf(找不到值为%d的结点!n,s);这样主函数便可直接调用该函数来实现查找过程。6.3时间和空间性能分析:由于二叉排序树的中序遍历序列为一个递增的有序序列,这样可以将二叉排序树看作是一个有序表。其查找过程:若查找成功,则是从根结点出发走了一条从根到某个结点的路径;若查找不成功,则是从根结点出发走了一条从根到某个叶子结点的路径。和关键字比较次数不超过二叉排序树的深度。二叉排序树的平均查找长度与其形态有关。最坏情况是具有n个结点的单支树,其平均查找长度与顺序查找相同,为(n+1)/2;即平均查找长度的数量级为O(n)。在最好情况下,二叉排序树形态均匀,它的平均查找长度与二分查找相似,大约是log2n,其平均查找长度的数量级为O(log2n)。1、 经验与体会: 由于该设计问题是对数据结构与算法课程中二叉树章节的灵活应用,所以课本给了我很大的帮助,结合所学知识以及对二叉排序树的理解,来编写该程序。7.测试结果及分析4524531228901、 建立如图(a)的二叉排序树,输入的数据依次为:45 24 53 12 28 90 0(0为输入结束符),屏幕(图(1)上显示的是横置的二叉树452453122890 图(a) 图(b) 图(1)2、选择方框中给定的项目(输入04中任意数)。若输入错误会有提示,可以重新输入。图(2)3、 输入1,则出现查找菜单。选择查找方法。图(3)4、在查找菜单选1,则进行递归查找。图(4)5、同理,若选择2,则进行非递归查找。查找的值存在与否都会有显示。图(5)6、选2,则进行插入操作。插入关键值为13的结点后,显示如图(6),即插入13后的横置的二叉排序树(图(c)图(d)。4524531228901345245312289013 图(c) 图(d)图(6)1、 选3,进行删除操作。删除关键值为24的结点后,显示如图(7),即删除24后的横置的二叉排序树(图(e)图(f)、451353122890451353122890 图(e) 图(f)图(7)2、 选4则显示详细信息。如图(8)所示,按中序遍历(从小到大)依次输出,并显示每个结点的孩子情况,最后打印出横置的二叉排序树。图(8)3、 选0则退出程序。 图(9)8.用户使用说明用户可以根据本程序运行过程中出现的提示性语句来进行操作。要注意括号中的提示,若没有按照提示输入的话,程序可能将无法继续进行下去。例如开始输入数据时直到输入0时才算结束输入,从而进行下一步操作。在遇到选项时,选择错误会给你重新选择的机会。提示:进行一系列插入删除等操作后,可以选择显示项来显示最后的二叉排序树状态 (二叉排序树显示的是中序遍历后的序列) 。9.参考文献(1)王昆仑.李红.数据结构与算法.北京:中国铁道出版社,2007.6(2)王昆仑.李红.数据结构与算法试验指导,2009(3)谭浩强.c程序设计.北京:清华大学出版社,2005.7(4)严蔚敏.数据结构:语言版.北京:清华大学出版社,2002(5)耿国华.等.数据结构:用c语言描述.北京:高等教育出版社,2004设计过程中质疑(或答辩)记载:1 二叉树运行过程中用了什么排序?答:运用了中序遍历排序。2中序遍历排序是怎样的? 答:先遍历左孩子,再遍历父结点,最后遍历右孩子。3.在设计过程中遇到过那些困难? 答:在编程序的过程的程序一直不能正确运行,最后发现函数的调用出现了问题。最后通过修改解决。指导教师评语: 签名: 2016年 7 月5 日附录#include stdio.h#include malloc.h#include stdlib.h#define endflag 0/定义endflag为关键字输入结束的标志/二叉排序树的结点结构typedef struct nodeint key;/关键字项struct node *lchild,*rchild;/左右孩子指针Bstnode;/二叉排序树的查找算法之一(递归)Bstnode *Bsearch(Bstnode *t,int x)if(t=NULL)/二叉排序树为空,查找失败return NULL;elseif(t-key=x)/查找成功,返回当前结点return t;if(xkey)return(Bsearch(t-lchild,x);/进入左子树递归查找elsereturn(Bsearch(t-rchild,x);/进入右子树递归查找/递归查找函数(显示查找结果)void search_Bitree(Bstnode *t)int s;/定义待查结点的关键值Bstnode *p;/定义待查的结点printf(n请输入要查找的结点的值:);scanf(%d,&s); if(s!=0)p=Bsearch(t,s);/递归查找 if(p!=NULL) printf(该结点值存在!n); else printf(找不到值为%d的结点!n,s);/二叉排序树的查找算法之二(非递归)Bstnode * searchBST(Bstnode *t,int x)Bstnode *p;int flag=0;p=t;/定义*p结点用于逐层查找,丛根结点开始查找while(p!=NULL)/二叉排序树不为空 if(p-key=x)/查找成功printf(该结点值存在!);flag=1;break;/查找不成功,到下一层继续查找 if(xkey)p=p-lchild;/查找左子树elsep=p-rchild;/查找右子树if(flag=0)printf(找不到值为%d的结点!,x);p=NULL;return p;/二叉排序树的结点插入算法Bstnode *InsertBST(Bstnode *t,int x)/ 插入关键值为x的元素Bstnode *s,*p,*f;/*s为待插结点,*p为逐层查找结点,*f为待插结点的父结点p=t;while(p!=NULL)f=p;/查找过程中,f指向*p的父结点if(x=p-key)/若二叉树中已有关键值为x的元素,无需插入return t;if(xkey)p=p-lchild;elsep=p-rchild;s=(Bstnode *)malloc(sizeof(Bstnode);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL)/原树为空,新结点作为二叉排序树的根return s;if(xkey)f-lchild=s;/新结点作为*f左孩子else f-rchild=s;/新结点作为*f右孩子return t;/中序遍历(递归法)void Inorder(Bstnode *t)if(t!=NULL)/若二叉树不空Inorder(t-lchild);/遍历左孩子 printf(%4d,t-key);Inorder(t-rchild);/遍历右孩子 /二叉排序树的结点删除算法Bstnode *DeleteBST(Bstnode *t,int k)/删除关键值为k的元素Bstnode *p,*f,*s,*q;/*p为待删结点,*f为*p父结点,*s为*p的中序前驱结点,*q为*s的父结点p=t;f=NULL;/从根结点开始查找,并将*f置空/查找关键值为k的待删结点*pwhile(p!=NULL)if(p-key=k) break;/若找到,则退出循环f=p;/未找到时将*f替代*p,*p则下移进入左右子树继续查找if(p-keyk)p=p-lchild;elsep=p-rchild;if(p=NULL) return t;/若找不到,则返回原二叉排序树的根指针/查找成功后,对*p的删除过程if(p-lchild=NULL|p-rchild=NULL)/若*p无左子树或无右子树if(f=NULL)/若*p是原二叉排序树的根if(p-lchild=NULL) t=p-rchild;/无左孩子,右孩子做根 else t=p-lchild;/无右孩子,左孩子做根else if(p-lchild=NULL)/若*p无左子树if(f-lchild=p) f-lchild=p-rchild;/p是*f的左孩子else f-rchild=p-lchild;/p是*f的右孩子 else /若*p无右子树 if(f-lchild=p) f-lchild=p-lchild;/p是*f的左孩子else f-rchild=p-lchild;/p是*f的右孩子free(p);else/若*p有左右子树q=p;s=p-lchild;while(s-rchild)/在*p的左子树中查找最右下结点(即其中序前驱结点)q=s;s=s-rchild;if(q=p) q-lchild=s-lchild;else q-rchild=s-lchild;p-key=s-key;/将*s的值赋给*pfree(s);return t;/插入函数(显示插入结果)Bstnode *insert_Bitree(Bstnode *t)int s;/定义待插结点的关键值Bstnode *p;/定义待插的结点 printf(n); printf(请输入要插入的结点的值:); scanf(%d,&s); if(s!=0) p=Bsearch(t,s); if(p=NULL) t=InsertBST(t,s);printf(插入结点中序遍历后的二叉排序树:n); Inorder(t); printf(n二叉排序树的根为:%dn,t-key); else printf(该结点值存在,不插入!n); return t; /删除函数(显示删除结果)Bstnode *delete_Bitree(Bstnode *t)int s;/定义待删结点的关键值Bstnode *p;/定义待删的结点printf(n请输入要删除的结点的值:);scanf(%d,&s);if(s!=0)p=Bsearch(t,s);if(p=NULL)printf(找不到值为%d的结点!,s); else t=DeleteBST(t,s); printf(删除结点后中序遍历的二叉排序树:n); Inorder(t);printf(n二叉排序树的根为:%dn,t-key); return t;/设置二叉排序树的初值Bstnode *CreateBST()Bstnode *t;int s;t=NULL;/设置二叉排序树的初态为空 scanf(%d,&s); while(s!=endflag)/输到结束符为止t=InsertBST(t,s); scanf(%d,&s); return t; /显示函数void print_Bitree(Bstnode *t) if(t!=NULL)/中序遍历二叉排序树,并显示遍历结果 print_Bitree(t-lchild); printf(遍历结点%d,t-key); if(t-lchild!=NULL) printf(该结点的左孩子为%d,t-lchild-key); else printf(该结点的左孩子为空); if(t-rchild!=NULL) printf( 该结点的右孩子为%d),t-rchild-key); else printf( 该结点的右孩子为空); printf(nn); print_Bitree(t-rchild); /主菜单int mainmenu()int choice;int flag=1;/标记量printf(nnn);printf(ttt*对二叉排序树进行操作*n);printf(tttn); printf(ttt n);printf(ttt1.二叉排序树-查找n); printf(ttt2.二叉排序树-插入n); printf(ttt3.二叉排序树-删除n); printf(ttt4.二叉排序树-显示n); printf(ttt0.退出该程序n);printf(ttt n);printf(tttn); printf(ttt*n); printf(nnn); doif(flag=0)pr

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论