用顺序和二叉链表作存储结构实现二叉排序树全代码(共36页).doc

《用顺序和二叉链表作存储结构实现二叉排序树全代码(共36页).doc》由会员分享，可在线阅读，更多相关《用顺序和二叉链表作存储结构实现二叉排序树全代码(共36页).doc（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上安徽新华学院数据结构课程设计报告题目：用顺序和二叉树存储结构实现二叉树排序 学院：信息工程 专业：信息与计算科学 班级：12信科本一班 姓名：李智 学号： 指导教师：李明 设计时间： 2013-12-16至2013-12-30 课程设计任务书一 设计任务研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。二 设计要求（1）. 利用顺序存储和链式存储两种算法计算实现二叉搜索树的创建。（2）. 利用顺序存储和链式存储两种算法计算实现中序遍历。（3）. 利用顺序存储和链式存储两种算法计算实现查找结点。（4）. 利用顺序存

2、储和链式存储两种算法计算实现删除结点。三 设计期限2013-12-16至2013-12-30前言数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树，一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。二叉树是树形结构的一个重要的类型，二叉树是n（n=0）个结点的有限集，它或者是空集（n=0），或者由个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 二叉树的存储结构和算法比较简单，特别适合计算机处理。即使一般形式的

3、树也可简单的转换为二叉树。二叉树的顺序存储结构是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存储单元中。遍历二叉树就是沿某有前序遍历、中条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。在遍历方案中主要序遍历、后序遍历。 现实中有许多应用到二叉树的例子，所以我们要把理论与现实结合起来。在学习中主要掌握怎么求二叉树的高度、叶子结点个数、总结点个数以及熟练三种遍历的方法。目 录2. 5 总体设计流程图3 专心-专注-专业1 需求分析1.1 问题的提出 研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。1.2任务与分析 用顺

4、序和二叉链表作存储结构实现二叉排序树：（1）以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。2 总体设计2.1二叉排序树的建立建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的

5、定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。若非空树，比较b与根结点数据data（p）如果bdata) *p=t;return (1); else if(keydata) searchBST(t-lchild,key,t,p); else searchBST(t-rchild,key,t,p); insertBST的声明 insertBST(node *t,int key

6、) node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) s=(node)malloc(sizeof(BSTnode); s-data=key; s-lchild=s-rchild=NULL; if(!p) *t=s; else if(keydata) p-lchild=s; else p-rchild=s; return (1); else return (0); inorderTraverse类的声明inorderTraverse(node *t) if(*t) if(inorderTraverse(&(*t)-lchild) printf(%

7、d ,(*t)-data); if(inorderTraverse(&(*t)-rchild); return(1) ; Delete类的声明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-datakey) p=p-lchild; else p=p-rchild; if(p=NULL) return t; if(p-lchild=NULL) if(q=NULL) t=p-rchild; else if(q-lchild=p) q-lchild=p-rc

8、hild; else q-rchild=p-rchild; free(p); else f=p; s=p-lchild; while(s-rchild) f=s; s=s-rchild; if(f=p) f-lchild=s-lchild; else f-rchild=s-lchild; p-data=s-data; free (s); return t;3.1 中序遍历模块系统将提示用户输入新添加的数据，输入结束后进行中序遍历关键代码： inorderTraverse(node *t) /*中序遍历函数*/ if(*t) if(inorderTraverse(&(*t)-lchild) /*

9、中序遍历根的左子树*/ printf(%d ,(*t)-data); /*输出根结点*/ if(inorderTraverse(&(*t)-rchild); /*中序遍历根的右子树*/ return(1) ;3.2 删除模块系统将对用户输入的数进行查找，查找到之后删除此数，并对全部数据进行中序遍历。关键代码：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-datakey) p=p-lchild; else p=

10、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-lc

11、hild=s-lchild; /*重接f的左子树*/ else f-rchild=s-lchild; /*重接f的右子树*/ p-data=s-data; free (s);return t;4编码与调试首先进入VC+6.0，打开工程zjr.dsw，然后进入源程序，也可以不打开工程，直接双击zjr文件夹下的zjr.exe文件即可运行程序。4.1 顺序存储图7.1.1 打开程序，成功显示提示信息图7.1.2 输入数据，以0结束输入，操作成功图7.1.3 功能1：中序输出数据，操作成功图7.1.4 功能2：删除数据，显示提示信息，操作成功图7.1.5 删除数据，操作成功图7.1.6 重复执行程序，

12、操作成功4.2 二叉链表存储图7.2.1打开程序，显示提示信息，操作成功图7.2.2功能1：输入数据，进行中序遍历，操作成功图7.2.3功能2：输入数据，进行删除，操作失败，因为没有此数据，显示 错误信息图7.2.4功能2：输入数据，进行中序遍历，操作成功通过上述测试，本系统实现了二叉树的生成，中序遍历，查找删除功能，能避免数据的输入错误等。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度（它表示随问题的规模n的增大，算法执行时间的增长率和f（n）的增长率相同）和空间复杂度。遍历二叉树的算法中的基本操作是访问结

13、点，则不论按哪一次次序进行遍历，对含n个结点的二叉树，其时间复杂度都为O（n）。所需空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O（n）。5 总结这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、删除二叉排序树中某个结点,。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。通过这一次的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，查找和某个删除结点等基本操作。但我同时

14、也发现了自己许多不足之处 。首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了基本的结点以及链表，在数据结构的选择上避重就轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。在今后的工作、学习中我将认真总结经验教训，努力使自己成为一名技术过硬、工作严谨、思维活跃的工程人员，为提

15、高人们的生活质量做出更大的贡献。心得体会课程设计结束了，在这次的课程设计中不仅检验了我所学的知识，也培养了我如何去把握一件事情，如何去做一件事情，课程设计是我们专业课程知识综合应用的实践训练是我们迈向社会，从事职业工作前一个必不可少的过程。我这次设计的科目是数据结构，数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。这次通过对二叉排序树的深入研究，我又一次的温习了c，c+和数据结构的有关知识，尽管这中间经历好多困难，但我通过查找多种资料，利用网络优势，完成了任务。我这次课程设计代

16、码中主要使用了链表的循环和遍历这两种操作。循环链表是单链表的另一种形式。遍历是指沿着某条收索路线，依次对树中每个节点均作一次且仅作一次访问。通过这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这是一笔很大的资源。在以后的学习中，我们应该利用更多的时间去上机实验，加强自学的能力、多编写程序，相信不久以后我们的编程能力都会有很大的提高，能创作出更多更完善更有新意的作品出来。参考文献1 谭浩强 编著. 程序设计. 北京:清华大学出版社，2000 2 王珊珊，张志航 编著. C+程序设计教程. 北京:机械工业出版社，20113 严蔚敏，吴伟民 编著. 数据结构.

17、北京:清华大学出版社，2001全部代码二叉链表结构c#include#includetypedef struct Tnode int data; /*输入的数据*/ struct Tnode *lchild,*rchild; /*结点的左右指针，分别指向结点的左右孩子*/ *node,BSTnode;searchBST(node t,int key,node f,node *p) /*查找函数*/ if(!t)*p=f;return (0); /*查找不成功*/else if(key=t-data) *p=t;return (1); /*查找成功*/ else if(keydata) sear

18、chBST(t-lchild,key,t,p); /*在左子树中继续查找*/else searchBST(t-rchild,key,t,p); /*在右子树中继续查找*/insertBST(node *t,int key) /*插入函数*/ node p=NULL,s=NULL; if(!searchBST(*t,key,NULL,&p) /*查找不成功*/ s=(node)malloc(sizeof(BSTnode); s-data=key; s-lchild=s-rchild=NULL; if(!p) *t=s; /*被插结点*s为新的根结点*/ else if(keydata) p-lc

19、hild=s;/*被插结点*s为左孩子*/ else p-rchild=s; /*被插结点*s为右孩子*/ return (1); else return (0);/*树中已有关键字相同的结点，不再插入*/ inorderTraverse(node *t) /*中序遍历函数*/ if(*t) if(inorderTraverse(&(*t)-lchild) /*中序遍历根的左子树*/ printf(%d ,(*t)-data); /*输出根结点*/ if(inorderTraverse(&(*t)-rchild); /*中序遍历根的右子树*/ return(1) ;node Delete(no

20、de t,int key) /*删除函数*/ node p=t,q=NULL,s,f; while(p!=NULL) /*查找要删除的点*/ if(p-data=key) break; q=p; if(p-datakey) 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

21、-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 s=0,j=0,i=0; int ch=0; node p=NULL

22、; printf(输入一串数，每个数以空格分开:); do scanf(%d,&num); if(!num) printf(完成输入!n); else insertBST(&T,num); while(num); printf(n 1: 中序输出); printf(n 2: 输入元素); while(ch=ch) scanf(%d,&ch); switch(ch) case 0: exit(0); /*0退出*/ case 1: printf( 中序遍历输出结果为:n ); inorderTraverse(&T); /*1中序遍历*/ break; case 2: printf( 输入元素x,

23、查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历，否则输出无x :); scanf(%d,&num); /*3删除某个结点*/ if(searchBST(T,num,NULL,&p) T=Delete(T,num); printf( 删除成功!中序遍历输出：n ); inorderTraverse(&T); else printf( 无%d,num); break; default: printf(无此结点n); break; /*输入无效字符*/ 二叉链表结构c+#include using namespace std;class nodepublic: node(int i)

24、:data(i),left(NULL),right(NULL) void inorder(node *&root) /中序遍历，符合升序输出 if(root!=NULL) inorder(root-left); coutdataright); void insert(node *&ptr,int item) /在查找树中插入元素 if(ptr=NULL) ptr=new node(item); else if(itemdata) insert(ptr-left,item); else insert(ptr-right,item); node *find(node *&ptr,int item)

25、 /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 if(ptr=NULL) return NULL; if(ptr-data=item) return ptr; else if(itemdata) find(ptr-left,item); else find(ptr-right,item); node *&findy(node *&ptr,int item) /在查找树中查找肯定存在的元素,并返回其引用 if(ptr-data=item) return ptr; else if(itemdata) findy(ptr-left,item); else findy(ptr-rig

26、ht,item); node* rl()return left; node* rr()return right; void dele(node *&ptr) /删除值为item所在结点 if(ptr-rl()=NULL&ptr-rr()=NULL) ptr=NULL; else if(ptr-rr()=NULL) ptr=ptr-rl(); else ptr=ptr-rr(); private: int data; node *left; /左孩子结点 node *right; /右孩子结点;int main() int t,i=0,j; coutt; cout输入tj; node *x=ne

27、w node(j); for(;ij; x-insert(x,j); coutinorder(x); /作中序遍历 coutn输入操作(当输入-1时程序结束):j; while(j!=-1) node *t=x-find(x,j); /定位结点 if(t!=NULL) node *&y=x-findy(x,j); x-dele(y); coutinorder(x); else cout无j; coutn输入操作(当输入-1时程序结束):j; return 0;顺序存储结构c#includestdio.h#includemalloc.h#includewindows.h#define endfl

28、ag #define N 1000int bN;typedef struct int data;int other;int flag1;Link;void Build(Link aN)int w,i,j,k; for(i=0;i=N;i+) ai.flag1=0; ai.data=0; printf(nttt 请输入树的根结点：);scanf(%d,&a1.data);a1.flag1=1;printf(nttt 请输入结点个数：);scanf(%d,&k);for(j=1;j=k;j+)printf(nttt 请输入结点的数值：);scanf(%d,&w);printf(nttt 第%d位：

29、%d,j,w);a0.data=w;a0.flag1=1;i=1;if(a0.dataai.data)loop:if(a2*i.flag1=0) a2*i.data=a0.data;a2*i.flag1=a0.flag1;if(a2*i.flag1=1)i=2*i;if(a0.dataai.data)goto loop1; if(a0.dataai.data) loop1:if(a2*i+1.flag1=0) a2*i+1.data=a0.data;a2*i+1.flag1=a0.flag1;if(a2*i+1.flag1=1)i=2*i+1;if(a0.dataai.data)goto lo

30、op1; void Sdel(Link aN)int i;int flag=0;int q;int number=1;int j=1;int bN;printf(nttt 请输入需要删除的结点的数值：);scanf(%d,&q);for(i=1;i=N;i+)if(ai.data=q)ai.data=0;printf(nttt 已删除%d：,q);flag=1;for(i=1;i=N;i+)if(ai.data!=0)bj=ai.data;j+;number+;for(i=1;i=N;i+)ai.flag1=0;ai.data=0;a1.data=b1;a1.flag1=1;for(j=2;j=number-1;j+)a0.data=bj;a0.flag1=1;i=1;if(a0.dataai.data)loop:if(a2*i.flag1=0) a2*i.data=a0.data;a2*i.flag1=a0.flag1; if(a2*i.flag1=1)i=2*i;if(a0.dataai.data)goto loop1;if(a0.dataai