用顺序和二叉链表作存储结构实现二叉排序树全代码.docx

安徽新华学院数据结构课程设计报告题目：用顺序和二叉树存储结构实现二叉树排序学院：信息工程专业：信息与计算科学班级：12信科本一班姓名：李智学号：1242155110指导教师：李明设计时间：20131216至2(H31230课程设计任务书-设计任务研究关于如何创立二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。二.设计要求(1) .利用顺序存储和链式存储两种算法计算实现二叉搜索树的创立。(2) .利用顺序存储和链式存储两种算法计算实现中序遍历。(3) .利用顺序存储和链式存储两种算法计算实现查找结点。(4) .利用顺序存储和链式存储两种算法计算实现删除结点。.设计期限2013-12-16三2013-12-30前言数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树，一共要实现四项根本的功能。它们分别是二叉搜索树的创立、中序遍历、查找结点和删除结点。二叉树是树形结构的一个重要的类型，二叉树是n(n>=0)个结点的有限集，它或者是空集(n=0),或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的存储结构和算法比拟简单，特别适合计算机处理。即使一般形式的树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。目录1需求分析21. 1问题的提出2任务与分析22总体设计2二叉排序树的建立2二叉排序树的中序遍历3二叉排序树中元素的查找3二叉排序树中元素的删除32. 5总体设计流程图3详细设计错误!未定义书签。3.1 中序遍历模块73.2 删除模块74编码与调试94.1顺序存储104.2二叉链表存储105总结11总结错误!未定义书签。心得体会12参考文献12全部代码13二叉链表结构C13二叉链表结构C+15顺序存储结构Cl81需求分析1.1 问题的提出研究关于如何创立二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。1.2 任务与分析用顺序和二叉链表作存储结构实现二叉排序树：(I)以回车('n')为输入结束标志,输入数列1.,生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)输入元素X,查找二叉排序树T,假设存在含X的结点,那么删除该结点,并作中序遍历(执行操作2)；否那么输出信息“无x”O2总体设计二叉排序树的建立建二叉树的结点至少应当包含三个域，分别存放结点的数据data,左子女结点指针IeftChild和右子女结点指针righlChik1.整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。假设P为根结点指针，b为当前待插入元素，其过程可以描述为：假设为空树(p=nil),动态生成一个结点，其数据域为当前待插入元素b,左、右指针域为“空”,P指向该结点。假设非空树，比拟b与根结点数据daia(p)如果b<data(p),将b插入左子树中；如果b>data(p),将b插入右子树中；左、右子树的插入方式与二叉排序树的插入方式相同。不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。由此可见，建立二叉排序树就是屡次调用二叉排序树的插入算法。二叉排序树的中序遍历中序遍历二叉树算法的框架是：假设二叉树为空，那么空操作；否那么中序遍历左子树(1.)；访问根结点(V)；中序遍历右子树(R)o0二叉排序树中元素的查找在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比拟判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为X的元素，查找过程从根结点开始。如果根指针为NU1.1.,那么查找不成功；否那么用给定值X与根结点的关键码进行比拟；如果给定值等于根结点的关键码，那么查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，那么继续递归查找根结点的左子树；否那么，递归搜索根结点的右子树。二叉排序树中元素的删除对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*P(指向结点的指针是P),其双亲结点为*f(结点指针为f),且不失一般性，可设*P是*f的左孩子，假设*P结点为叶子结点，即P和1均为空，只需修改其双亲结点指针即可。假设*P结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。假设左子树和右子树都不为空，令*P的直接前驱替代*P,然后从二叉排序树中删除它的直接前驱，即可。总体设计流程图3.详细设计>Tnode的声明typedefstructTnodeintdata;structTnode*lchild,*rchild;*node,BSTnode; searchBST的声明SearchBST(nodet,intkey,nodef,node*p)(if(1t)*p=f;return(O);elseif(key=t->data)*p=t;return(1);elseif(key<t->data)searchBST(t->lchild,key,t,p);elsesearchBST(t->rchiId,key,t,p);) insertBST的声明insertBST(node*t,intkey)(nodep=NU1.1.,s=NU1.1.;if(!searchBST(*t,key,NU1.1.,&p)(s=(node)malIoc(siZeof(BSTnode);s->data-key;s->lchild=s->rchiId=NU1.1.;if(!p)*t=s;elseif(key<p->data)p->lchild=s;elsep->rchild=s;return(1);)elsereturn(O);) inorderTraverse类的声明inorderTraverse(node*t)if(inorderTraverse(&(*t)->lchiId)printf(zz%d,z,(*t)->data);if(inorderTraverse(&(*t)->rchild);return(1);)Delete类的声明nodeDelete(nodet,intkey)nodep=t,q=NU1.1.,s,f;whiIe(p!=NU1.1.)if(p->data=key)break;q=P；if(p->data>key)p=p->lchild;elsep=p->rchild;)if(P=NU1.1.)returnt;if(p->IchiId=NU1.1.)(if(q=NU1.1.)t=p->rchild;elseif(q->lchild-p)q->lchild=p->rchiId;elseq->rchild=p->rchiId;free(p);)elsef=P；s=p->lchild;while(s->rchild)f=s;s=s->rchild;if(f=p)f->lchild=s->lchiId;elsef->rchild=s->lchiId;p->data=s->data;free(三);returnt;1.1 中序遍历模块系统将提示用户输入新添加的数据，输入结束后进行中序遍历关键代码：InorderTraverse(node*t)/*中序遍历函数*/(if(*t)if(inorderTraverse(&(*t)->lchild)/*中序遍历根的左子树*/printfCz%d",(*t)->data);/*输出根结点*/if(inorderTraverse(&(*t)->rchiId);/*中序遍历根的右子树*/)return(1);3. 2删除模块系统将对用户输入的数进行查找，查找到之后删除此数，并对全部数据进行中序遍历。关键代码：nodeDelete(nodet,intkey)*删除函数*/nodep=t,q=NU1.1.,s,f;while(p!=NU1.1.)*查找要删除的点*/(if(p->data-key)break;q=p;if(p->data>key)p=p->lchild;elsep=p->rchiId;)if(p=NU1.1.)returnt;*查找失败*/if(p->lchiId=NU1.1.)*p指向当前要删除的结点*/(if(q=NU1.1.)t=p->rchild;*q指向要删结点的父母*/elseif(q->lchild=p)q->lchild=p->rchiId;*p为q的左孩子*/elseq->rchild=p->rchild;/*p为q的右孩子*/free(p);)else*P的左孩子不为空*/f=p;s=p->lchiId;While(s->rchild)*左拐后向右走到底*/f=s;s=s->rchiId;if(f-p)f->lchild=s->lchiId;/*重接f的左子树*/elsef->rchi1d=s->!child;/*重接f的右子树*/p->data=s->data;free(三);returnt;4编码与调试首先进入VC+6.0,翻开工程zjr.dsw,然后进入源程序，也可以不翻开工程，直接双击Zjr文件夹下的zjr.exe文件即可运行程序。4.1顺序存储图.1翻开程序，成功显示提示信息图输入数据，以O结束输入，操作成功图功能1：中序输出数据，操作成功图功能2：删除数据，显示提示信息，操作成功图删除数据，操作成功图重复执行程序，操作成功4. 2二叉链表存储图翻开程序，显示提示信息，操作成功图功能1：输入数据，进行中序遍历，操作成功图功能2：输入数据，进行删除，操作失败，因为没有此数据，显示错误信息功能2：输入数据，进行中序遍历，操作成功通过上述测试，本系统实现了二叉树的生成，中序遍历，查找删除功能，能防止数据的输入错误等。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度(它表示随问题的规模n的增大，算法执行时间的增长率和f(n)的增长率相同)和空间复杂度。遍历二叉树的算法中的根本操作是访问结点，那么不管按哪一次次序进行遍历，对含n个结点的二叉树，其时间复杂度都为O(n)o所需空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n,那么空间复杂度也为0(n)o5总结这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创立、中序遍历、删除二叉排序树中某个结点，。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。通过这一次的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创立，中序遍历，查找和某个删除结点等根本操作。但我同时也发现了自己许多缺乏之处。首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了根本的结点以及链表，在数据结构的选择上避重就轻，覆盖面较小，不能很好的表达各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。在今后的工作、学习中我将认真总结经验教训，努力使自己成为一名技术过硬、工作严谨、思维活泼的工程人员，为提高人们的生活质量做出更大的奉献。心得体会课程设计结束了，在这次的课程设计中不仅检验了我所学的知识，也培养了我如何去把握一件事情，如何去做一件事情，课程设计是我们专业课程知识综合应用的实践训练是我们迈向社会，从事职业工作前一个必不可少的过程。我这次设计的科目是数据结构，数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。这次通过对二叉排序树的深入研究，我又一次的温习了C,C+和数据结构的有关知识，尽管这中间经历好多困难，但我通过查找多种资料，利用网络优势，完成了任务。我这次课程设计代码中主要使用了链表的循环和遍历这两种操作。循环链表是单链表的另一种形式。遍历是指沿着某条收索路线，依次对树中每个节点均作一次且仅作一次访问。通过这次的课程设计，更是让我深刻认识到自己在学习中的缺乏，同时也找到了克服这些缺乏的方法，这是一笔很大的资源。在以后的学习中，我们应该利用更多的时间去上机实验，加强自学的能力、多编写程序，相信不久以后我们的编程能力都会有很大的提高,能创作出更多更完善更有新意的作品出来。参考文献1谭浩强编著.程序设计.北京:清华大学出版社，20002王珊珊，张志航编著.C+程序设计教程.北京:机械工业出版社，20113严蔚敏，吴伟民编著.数据结构.北京:清华大学出版社，2001全部代码二叉链表结构C#include<stdio.h>#include<stdlib.h>typedefstructTnodeintdata;*输入的数据*/structTnode*lchild,*rchild;/*结点的左右指针，分别指向结点的左右孩子*/)*nodc,BSTnode;searchBST(nodet,intkey,nodef,node*p)*查找函数*/(if(it)*p=f;retum(O);)/*查找不成功*/elseif(key=t->data)*p=t;return(1);(/*查找成功*/elseif(key<t->data)searchBST(t->lchild,key,t,p);/*在左子树中继续查找*/elsesearchBST(t->rchild,key,t,p);/*在右子树中继续查找*/)insertBST(node*t,intkey)/*插入函数*/(nodep=NU1.1.,s=NU1.1.;if(!searchBST(*t,key,NU1.1.,&p)/*查找不成功*/1s=(node)malloc(sizeof(BSTnode);s->data=key;s->lchild=s->rchi1d=NU1.1.;if(!p)*t=s;/*被插结点*s为新的根结点*/elseif(key<p->data)p->lchild=s;/*被插结点*s为左孩子*/elsep->rchild=s;/*被插结点*s为右孩子*/return(1);Ielsereturn(O);/*树中已有关键字相同的结点，不再插入*/)inorderTraverse(node*t)/*中序遍历函数*/(if(*t)if(inorderTraverse(*t)->lchild)/*中序遍历根的左子树*/printf("%d",(*t)->data);/*输出根结点*/if(inordcrTraverse(<fe(*t)->rchild);/*中序遍历根的右子树*/return(1);)nodeDelete(nodet,intkey)/*删除函数*/(nodep=t,q=NU1.1.,s,f;while(p!=NU1.1.)/*查找要删除的点*/(if(p->data=key)break;q=p;if(p->data>key)p=p->lchild;elsep=p->rchild;)if(p=NU1.1.)returnt;/*查找失败*/if(p->lchiId=NU1.1.)*p指向当前要删除的结点*/(if(q=NU1.1.)t=p->rchild;*q指向要删结点的父母*/elseif(q->lchild=p)q->lchild=p->rchild;*p为q的左孩子*/elseq->rchild=p->rchild*p为q的右孩子*/free(p);Ielse*p的左孩子不为空*/f二P；s=p->lchild;while(s->rchild)/*左拐后向右走到底*/(f=s;s=s->rchild;1if(f=p)f->lchild=s->lchild;/*重接f的左子树*/elsef->rchild=s->lchild;/*重接f的右子树*/p->data=s->data;free(三);)returnt;)voidmain()nodeT=NU1.1.;intnum;ints=O,j=O,i=O;intch=0;nodep=NU1.1.;Printf("输入-串数，每个数以空格分开:")；doscanf(',%d",<fenum);if(!num)Printf("完成输入!n");elseinsertBST(&T,num);)while(num);printf("n1:中序输出”)；printf(',n2:输入元素")；while(ch=ch)(scanf(',%d",<fech);switch(ch)case0:exit(0);*0一退出*/case 1:printf("中序遍历输出结果为:n")；inorderTraverse(<feT);/*1中序遍历*/break;case 2:Printf("输入元素X,查找二叉排序树T,假设存在含X的结点,那么删除该结点,并作中序遍历，否那么输出无Xscanf("%d,<fcnum);/*3一删除某个结点if(searchBST(T,num,NU1.1.,&p)(T=Delete(T,num);printf(11删除成功!中序遍历输出：n");inorderTraverse(&T);)elseprintf(',无d",num);break;default:Printf("无此结点n");break;/*输入无效字符*/二叉链表结构C+#includc<iostream>usingnamespacestd;classnodepublic:node(inti):data(i),Ieft(NU1.1.),right(NU1.1.)voidinorder(node*&root)中序遍历，符合升序输出(if(root!=NU1.1.)(inorder(root->left);cout<<root->data<<,'inorder(root->right);)voidinsert(nodc*<fcptr,intitem)在查找树中插入元素(if(ptr=NU1.1.)ptr=newnode(item);elseif(item<ptr->data)insert(ptr->left,item);elseinsert(ptr->right,item);)node*find(node*&ptr,intitem)在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。(if(ptr=NU1.1.)returnNU1.1.;if(ptr->data=item)returnptr;elseif(item<ptr->data)find(ptr->left,item);elsefind(ptr->right,item);1node*&findy(node*&ptr,intitem)在查找树中查找肯定存在的元素,并返回其引用(if(ptr->data=item)returnptr;elseif(item<ptr->data)findy(ptr->left,item);elsefindy(ptr->right,item);1node*rl()returnleft;)node*rr()returnright;)voiddele(node*&ptr)删除值为item所在结点(if(ptr->rl()=NU1.1.&&ptr->rr()=NU1.1.)ptr=NU1.1.;elseif(ptr->rr()=NU1.1.)ptr=ptr->rl();elseptr=ptr->rr();)private:intdata;node*left;左孩子结点node*right;右孩子结点I；intmain()(intt,i=O,j;CoUt«”输入数字个数(结点个数):"；cin>>t;COUt«"输入"<vt<v"个数字，数字之间用空格隔开:"；cin>>j;node*x=newnode(j);fbr(;i<t-l;i+)(cin>>j;x->insert(x,j);1COUt<<”中序遍历为:"；x->inorder(x);作中序遍历cout<<,n输入操作(当输入J时程序结束):"<<endl;cin>>j;while(j!=-l)(node*t=x->find(x,j);定位结点if(t!=NU1.1.)(node*<fey=x->findy(x,j);x->dele(y);CoUt«"中序遍历为严;x->inorder(x);)elseCoUt«"无"v<j;cout<<"n输入操作(当输入时程序结束):“<<endl;cin>>j;)return0;顺序存储结构C#include"stdio.h"#include"malloc.h"#include"windows.h"#defineendflag999999#defineN100OintbN;typedefstruct(intdata;intother;intflagl;)1.ink;voidBuild(1.inkaN)(intw,ij,k;for(i=0;i<=N;i+)(ai.flag1=0;ai.data=0;)printf("nttt请输入树的根结点：”)；scanf(',%d",<fea1.data);al.flagl=l;printf("nttt请输入结点个数：，,);scanf(',%d",<fek);for(j=l;j<=k;j+)(printf("nttt请输入结点的数值：”);scanf("%d",&w);printf("nttt第d位:%d"J,w);a0.data=w;a0.flagl=l;i=l；if(aO.data<ai.data)(lpnf(a2*i.flagI=O)(a2*i.data=aO.data;a2*i.flag1=a0.flag1;if(a2*i.flagl=l)(i=2*i;if(aO.data<ai.data)gotoloop;if(aO.data>ai.data)gotoloop1;)1if(aO.data<ai.data)100pI:if(a2*i+l.flagl=0)(a2*i+1.data=aO.data;a2*i+l.flagl=a0.flagl;)if(a2*i+l.flagl=l)(i=2*i+l;if(aO.data<ai.data)gotoloop;if(aO.data>ai.data)gotoloop1;voidSdel(1.inkaN)(inti;intflag=O;intq;intnumber=1;intj=luntbN;printf("nttt请输入需要删除的结点的数值：”);scanf(',%d",<feq);for(i=l;i<=N;i+)if(ai.data=q)(ai.data=O;printf("nttt已删除d：,1,q);flag=l;for(i=l;i<=N;i+)(if(ai.data!=O)(bj=ai.data;j+；number+;for(i=l;i<=N;i+)ai.flag1=0;ai.data=0;)al.data=bl;al.flagl=l;fbr(j=2;j<=number-1;j+)(aO.data=bj;a0.flag1=1;i=l；if(aO.data<ai.data)(loop:if(a2*i.flag1=0)a2*i.data=a0.data;a2*i.flag1=aO.flag1;1if(a2*i.flag1=1)(i=2*i;if(aO.data<ai.data)gotoloop;if(aO.data>ai.data)gotoloop1;)1if(aO.data>ai.data)(lpkif(a2*i÷1.flag1=0)(a2*i+l.data=aO.data;a2*i÷l.flagl=a0.flagl;)if(a2*i+1.flag1=1)(i=2*l+l;if(aO.data<ai.data)gotoloop;if(aO.data>ai.data)gotoloop1;printf（,nnttt显示已经删除结点后的数据n"）;for(i=l;i<N;i+)if(ai.data!=O)Printf("nttt位于二叉排序树的第d位的数据为：",i);printf("->%dnn",ai.data);if(flag=O)printf(',nnnttt已经删除活不存在该结点，不能再删除n");)voidmain()(inti;1.inkaN;intflag=O;intch=0;printf("n1:建立二叉排序树并中序遍历输出”)；printf("n2:输入一个元素，删除后重构二叉排序树并中序输出”)；while(ch=ch)(scanf(',%d"ch);switch(ch)(case0:exit(0);*0退出*/case 1:printf("ttt请输入信息n”)；Build（八）;printf(,n11);for(i=l;i<N;i+)(if(ai.data!=O)(Printf("nttt位于二叉排序树的第d位的数值为1i);printf("->%dnn",ai.data);break;)case 2:Printf("输入元素x,查找二叉排序树T,假设存在含X的结点,那么删除该结点,并作中序遍历，否那么输出无XSdel（八）;break;default:Printf（"无此结点n"）;break;/*输入无效字符*/安徽新华学院课程设计成绩评定表（本科）课题名称用顺序和二叉树存储结构实现二叉树排序院系信息工程学院年级专业12信科一班学号姓名成绩1242155110李智课题设计目的与设计意义1、课题设计目的：利用顺序存储和链式存储两种算法计算实现二叉搜索树的创立。利用顺序存储和链式存储两种算法计算实现中序遍历。利用顺序存储和链式存储两种算法计算实现查找结点。利用顺序存储和链式存储两种算法计算实现删除结点。2、课题设计意义：这次课程设计使我对数据结构认识深刻了许多,其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创立、中序遍历、删除二叉排序树中某个结点，。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。通过这一次的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创立，中序遍历，查找和某个删除结点等根本操作。指导教师：年月日