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

1、数学与计算机学院课程设计说明书课 程 名 称: 数据结构课程设计 课 程 代 码: 6013799 题 目: 二叉排序树的实现 年级/专业/班: 10 级计科（3）班 学 生 姓 名: 学 号: 开 始 时 间: 2012 年 12 月 25 日完 成 时 间: 2013 年 01 月 8 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日二叉排序树的实现 目 录 1 1 引引 言言.11.1 问题的提出 .11.2 任务与分析.12 2 程序的主要功能程序的主要功能.22.1 二叉排序树的建立.22.

2、2 二叉排序树的中序遍历.22.3 二叉排序树中元素的查找.22.4 二叉排序树中元素的删除.33 3 程序运行平台程序运行平台.44 4 总体设计总体设计.55 5 程序类的说明程序类的说明.66 6 模块模块.96.1 中序遍历模块 .96.2 删除模块 .97 7 系统测试系统测试.127.1 顺序存储 .127.2 二叉链表存储 .168 8 结论结论.19总 结.19心得体会.20参考文献参考文献.21全部代码全部代码.22二叉链表结构C.22二叉链表结构C+ .26顺序存储结构C.29 二叉排序树的实现摘摘 要要 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们

3、之间的关系和操作等的学科。本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设中的二叉排序树，一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。关键词：二叉排序树；中序遍历；搜索结点；删除结点；CC+-1-二叉排序树的实现1 引 言 1.1 问题的提出 研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。1.2 任务与分析 用顺序和二叉链表作存储结构实现二叉排序树：（1）以回车(n)为输入结束标志,输入数列 L，生成一棵二叉排序树 T；（2）对二叉排序树 T 作中序遍历，输出结果；（3）

4、输入元素 x,查找二叉排序树 T,若存在含 x 的结点,则删除该结点,并作中序遍历(执行操作 2)；否则输出信息“无 x” 。-2-二叉排序树的实现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); insertBSTinsertBST 的声明的声明 insertBST(node *t,int key) node p=NULL,s=NULL; if(!s

6、earchBST(*t,key,NULL,&p) s=(node)malloc(sizeof(BSTnode); s-data=key; s-lchild=s-rchild=NULL; if(!p) *t=s; else-8-二叉排序树的实现 if(keydata) p-lchild=s; else p-rchild=s; return (1); else return (0);inorderTraverseinorderTraverse 类的声明类的声明inorderTraverse(node *t) if(*t) if(inorderTraverse(&(*t)-lchil

7、d) printf(%d ,(*t)-data); if(inorderTraverse(&(*t)-rchild); return(1) ;DeleteDelete 类的声明类的声明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) -9-二叉排序树的实现 if(q=NULL) t=p-rchi

8、ld; else if(q-lchild=p) q-lchild=p-rchild; 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;-10-二叉排序树的实现 6 模块6.1 中序遍历模块系统将提示用户输入新添加的数据，输入结束后进行中序遍历关键代码： inorderTraverse(node *t)

9、 /*中序遍历函数*/ if(*t) if(inorderTraverse(&(*t)-lchild) /*中序遍历根的左子树*/ printf(%d ,(*t)-data); /*输出根结点*/ if(inorderTraverse(&(*t)-rchild); /*中序遍历根的右子树*/ return(1) ;6.2 删除模块系统将对用户输入的数进行查找，查找到之后删除此数，并对全部数据进行中序遍历。关键代码：node Delete(node t,int key) /*删除函数*/ node p=t,q=NULL,s,f; while(p!=NULL) /*查找要删除的点*

10、/-11-二叉排序树的实现 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-rchild=p-rchild;/*p 为 q 的右孩子*/ free(p); else /*p 的左

11、孩子不为空*/ f=p; s=p-lchild;-12-二叉排序树的实现 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;-13-二叉排序树的实现7 系统测试首先进入 VC+6.0，打开工程 zjr.dsw，然后进入源程序，也可以不打开工程，直接双击 zjr 文件夹下的 zjr.exe 文件即可运行程序。7.1 顺序存储图 7.1

12、.1 打开程序，成功显示提示信息-14-二叉排序树的实现图 7.1.2 输入数据，以 0 结束输入，操作成功-15-二叉排序树的实现图 7.1.3 功能 1：中序输出数据，操作成功图 7.1.4 功能 2：删除数据，显示提示信息，操作成功-16-二叉排序树的实现图 7.1.5 删除数据，操作成功-17-二叉排序树的实现图 7.1.6 重复执行程序，操作成功7.2 二叉链表存储图 7.2.1 打开程序，显示提示信息，操作成功-18-二叉排序树的实现图 7.2.2 功能 1：输入数据，进行中序遍历，操作成功-19-二叉排序树的实现图 7.2.3 功能 2：输入数据，进行删除，操作失败，因为没有此数

13、据，显示 错误信息图 7.2.4 功能 2：输入数据，进行中序遍历，操作成功通过上述测试，本系统实现了二叉树的生成，中序遍历，查找删除功能，能避免数据的输入错误等。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度（它表示随问题的规模 n 的增大，算法执行时间的增长率和 f（n）的增长率相同）和空间复杂度。遍历二叉树的算法中的基本操作是访问结点，则不论按哪一次次序进行遍历，对含 n 个结点的二叉树，其时间复杂度都为 O（n） 。所需空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为 n，则空间复杂度也为 O（

14、n） 。-20-二叉排序树的实现8 结论总 结这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、删除二叉排序树中某个结点,。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。通过这一次的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，查找和某个删除结点等基本操作。但我同时也发现了自己许多不足之处 。首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了基本的结点以及链表，在数据结构的选择上避重就

15、轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。在今后的工作、学习中我将认真总结经验教训，努力使自己成为一名技术过硬、工作严谨、思维活跃的工程人员，为提高人们的生活质量做出更大的贡献。-21-二叉排序树的实现心得体会课程设计结束了，在这次的课程设计中不仅检验了我所学的知识，也培养了

16、我如何去把握一件事情，如何去做一件事情，课程设计是我们专业课程知识综合应用的实践训练是我们迈向社会，从事职业工作前一个必不可少的过程。我这次设计的科目是数据结构，数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。这次通过对二叉排序树的深入研究，我又一次的温习了 c，c+和数据结构的有关知识，尽管这中间经历好多困难，但我通过查找多种资料，利用网络优势，完成了任务。我这次课程设计代码中主要使用了链表的循环和遍历这两种操作。循环链表是单链表的另一种形式。遍历是指沿着某条收索路线，依次对

17、树中每个节点均作一次且仅作一次访问。通过这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这是一笔很大的资源。在以后的学习中，我们应该利用更多的时间去上机实验，加强自学的能力、多编写程序，相信不久以后我们的编程能力都会有很大的提高，能创作出更多更完善更有新意的作品出来。-22-二叉排序树的实现参考文献1 谭浩强 编著. 程序设计. 北京:清华大学出版社，2000 2 王珊珊，张志航 编著. C+程序设计教程. 北京:机械工业出版社，20113 严蔚敏，吴伟民 编著. 数据结构. 北京:清华大学出版社，2001-23-二叉排序树的实现全部代码全部代码二叉链表结

18、构二叉链表结构 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) searchBST(t-lchild,ke

19、y,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-lchild=s;/*被插结

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

21、 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) /*p 指向当前要删除的结点*/ if(q=NULL) t=p-rchild; /*q 指向要删结点的父母*/ else if(q-lchild=p) q-lchild=p-rchild; /*p 为

22、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 的左子树*/-25-二叉排序树的实现 else f-rchild=s-lchild; /*重接 f 的右子树*/ p-data=s-data; free (s); return t;void main() node T=NULL; int num; int

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

24、se(&T); /*1中序遍历*/ break; case 2: printf( 输入元素 x,查找二叉排序树 T,若存在含 x 的结点,则删除该结点,并作中序遍历，否则输出无 x :); scanf(%d,&num); /*3删除某个结点*/ if(searchBST(T,num,NULL,&p) T=Delete(T,num);-26-二叉排序树的实现 printf( 删除成功!中序遍历输出：n ); inorderTraverse(&T); else printf( 无%d,num); break; default: printf(无此结点n); brea

25、k; /*输入无效字符*/ -27-二叉排序树的实现二叉链表结构二叉链表结构 c+#include using namespace std;class nodepublic: node(int i):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(i

26、tem); else if(itemdata) insert(ptr-left,item); else insert(ptr-right,item); node *find(node *&ptr,int item) /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 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,in

27、t item) /在查找树中查找肯定存在的元素,并返回其引用 if(ptr-data=item) return ptr; else if(itemdata)-28-二叉排序树的实现 findy(ptr-left,item); else findy(ptr-right,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) p

28、tr=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=new 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)-29-二叉排序树的实现 node *&

29、;y=x-findy(x,j); x-dele(y); coutinorder(x); else cout无j; coutn 输入操作(当输入-1 时程序结束):j; return 0;-30-二叉排序树的实现顺序存储结构顺序存储结构 c#includestdio.h#includemalloc.h#includewindows.h#define endflag 999999#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

30、=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 位：%d,j,w);a0.data=w;a0.flag1=1;i=1;if(a0.dataai.data)loop:if(a2*i.flag1=0)-31-二叉排序树的实现 a2*i.data=a0.dat

31、a;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 loop1; void Sdel(Link aN)int i;int flag=0;int q;int number=1;int j=1;int bN;printf(nttt 请输入需要删