二叉排序树的实现数据结构课程设计.doc

1、题 目 二叉排序树的实现一、开发背景数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。本课程设计中的二叉排序树，可以用顺序存储和链式存储两种算法计算。本课程设计中的二叉排序树，一共要实现四项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。语言的表现能力和处理能力极强。它不仅具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。它还可以直接访问内存的物理地址，进行位(bit)一级的操作。由于语言实现了对硬件的编程操作，因此语言集高级语言和低级语言的功能

2、于一体。既可用于系统软件的开发，也适合于应用软件的开发。C是C+的基础，C+语言和语言在很多方面是兼容的，C+程序员可以利用C+与C的兼容性而直接并有效的使用大量现成的程序库，从而开发出更简洁更高效的系统。需求分析：建立排序二叉树，主要是建立节点来存储输入的数据，需要建立函数来创造排序二叉树。该题目包括三方面的内容：一个是二叉排序树的建立，而是二叉树的中序遍历，三是二叉树元素的查找并删除。了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统

3、的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。关键词：二叉排序树；中序遍历；搜索结点；删除结点；CC+二、课程设计题目1、二叉排序树的实现问题描述：用顺序和二叉链表作存储结构实现二叉排序树：（1）以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。2、课程设计要求在处理题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤

4、完成题目，最终写出完整的分析报告。对于稍复杂的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。给出主要模块的算法描述，用流程图或伪代码表示。说明：在设计的过程中，步骤1-步骤4往往是反复进行，在后续步骤中发现问题，往往需要从头重新分析、设计。在写算法之前，应对数据结构进行设计。本题主要会用到指针变量，插入节点函数和建立二叉树，以及中序遍历函数，还有一些输入输出语句。三、算法思想1、二叉排序树的定义二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：（1）每个结点都有一个作

5、为搜索依据的关键码（key），所有结点的关键码互不相同；（2）若它的左子树非空，则左子树上所有结点的值均小于根结点的值；（3）若它的右子树非空，则右子树上所有结点的值均大于根结点的值；（4） 左、右子树本身又各是一棵二叉排序树2、二叉排序树的实现1）建立二叉排序树建立二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按

6、照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。若非空树，比较b与根结点数据data（p）如果bdata(p), 将b插入左子树中；如果bdata(p)，将b插入右子树中；左、右子树的插入方式与二叉排序树的插入方式相同。不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。2）二叉排序树的中序遍历中序遍历二叉树算法的框架是：若二叉树

7、为空，则空操作；否则中序遍历左子树（L）；访问根结点（V）；中序遍历右子树（R）。中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕3）二叉排序树中元素的查找在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定值小于根结点的关键码，则继续递归查找

8、根结点的左子树；否则，递归搜索根结点的右子树。4）二叉排序树中元素的删除对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p（指向结点的指针是p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，若*p结点为叶子结点，即p和l均为空，只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树，只要令左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空，令*p的直接前驱替代*p，然后从二叉排序树中删除它的直接前驱，即可。四、算法实现1、任务描述对二叉排序树T作

9、中序遍历,并输出结果二叉链表作存储结构和顺序表作存储结构输入数列L， 以回车(n)为输入结束标志生成二叉排序树T；输入元素x，查找二叉排序树T找到该节点x 无结点x 存在含x的结点，则删除该结点，并作中序遍历二叉排序树T是否为平衡二叉树NO!OK!2、功能描述：(1)以回车(n)为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历，输出结果；(3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。3、功能模块详细设计详细设计思想建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找

10、到相等的则插入其左子树。否则返回当前结点的上一个结点，然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右边的节点。程序主要设计了四个功能：首先是创建二叉排序树，完成后出现任务菜单，以数字代码确定，二叉排序树的中序遍历和查找，删除步骤，最后完成，结束。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。删除结点函数，

11、采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。4、程序模块#include 主函数int main()int t,i=0,j;cout 10信息安全王转红（201181250122）endl;cout1.二叉排序树T的输入:endl;coutt;cout输入tj;node *x=new node(j);for(;ij;x-insert(x,j);coutinorder(x); /作中序遍历coutn;cout2.二叉排序树T的元素查找和

12、删除:endl;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;5、程序编码1）用顺序实现;#include stdafx.h#include using namespace std;class nodepublic:node(int i):data(i),left(NULL),right(NULL)void ino

13、rder(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) /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。if(ptr=NULL)return

14、 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-right,item);node* rl()return left;node* rr()return right;void dele

15、(node *&ptr) /删除值为item所在结点if(ptr-rl()=NULL&ptr-rr()=NULL)ptr=NULL;else if(ptr-rr()=NULL)ptr=ptr-rl();elseptr=ptr-rr();private:int data;node *left; /左孩子结点node *right; /右孩子结点;int main()int t,i=0,j;cout 2011信息安全王转红（201181250122）endl;cout1.二叉排序树T的输入:endl;coutt;cout输入tj;node *x=new node(j);for(;ij;x-inse

16、rt(x,j);coutinorder(x); /作中序遍历coutn;cout2.二叉排序树T的元素查找和删除:endl;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;2)用二叉链表实现：#include stdafx.h#include using namespace std;class nodepublic:

17、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(item);else if(itemdata)insert(ptr-left,item);else insert(ptr-right,item);node *find(node *&ptr,int item)

18、 /在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。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-right,item);node

19、* 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();elseptr=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

20、);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;6、流程图初始化输入数据无X查找函数中序遍历遍历结果插入节点X1 2删除节点存在含x的结点不存在输出遍历结果7、测试结果顺序表测试1)初次调试结果2）输入结点个数后的截图3）中序遍历结果截图4）删除结点4后的截图删除结点4

21、后中序遍历结果二叉链表测试1)输入结点个数2）中序遍历结果截图3）删除结点2后结果五、测试结果分析输入一串数据，进行中序遍历，输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。验证结果正确，说明其符合算法设计的要求：(1)正确性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度（它表示随问题的规模n的增大，算法执行时间的增长率和f（n）的增长率相同）和空间复杂度。遍历二叉树的算法中的基本操作是访问结点，则不论按那一次次序进行遍历，对含n个结点的二叉树，其时间复杂度为O（n）。所需辅助空间为遍历过程中栈的

22、最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O（n）。六、总结这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、删除二叉排序树中某个结点,。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。通过一周的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，查找和某个删除结点等基本操作。但我同时也发现了自己许多不足之处 。首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了基本的结点以及链表，

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

24、如何去把握一件事情，如何去做一件事情，课程设计是我们专业课程知识综合应用的实践训练是我们迈向社会，从事职业工作前一个必不可少的过程。我们这次设计的科目是数据结构，数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。作为一门独立的课程在国外是从1968年才开始的。这次通过对二叉排序树的深入研究，我又一次的温习了c和数据结构的有关知识，也为我今后对c+的学习奠定了基础，尽管这中间经历好多困难，但我们齐心协力，查找多种资料，利用网络优势，完成了任务。我这次课程设计代码中主要使用了链表的循

25、环和遍历这两种操作。循环链表是单链表的另一种形式。遍历是指沿着某条收索路线，依次对树中每个节点均作一次且仅作一次访问。通过这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这是一笔很大的资源。在以后的学习中，我们应该利用更多的时间去上机实验，加强自学的能力、多编写程序，相信不久以后我们的编程能力都会有很大的提高，能设计更多的更有创新的作品。这次数据结构的课程设计作业在第14周作业布置下来的，但紧接着是我们的英语四级考试，数字逻辑、离散数学等一系列考试，既要做这次的课程设计，也要认真准备考试，因此时间非常紧。但基于我对编程的极大兴趣，我对这次的课程设计非常重视

26、。通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。 虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。我感受最深的一点是：以前用C、C+编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，

27、挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！在这次实验中，我对参数的调

28、用也进行了很多种尝试，已经能够相对准确的选择合适的参数形式来实现函数之间的数据传输交互了。这次实验中我也出现过一些比较严重的错误。这是我对基本概念理解的模糊不清造成的。后来在同学的指点下我意识到自己的错误。不过收获也很不少。通过此次的课程设计，我更加体验到了编程的乐趣，我将在以后的学习中进一步运用数据结构这门课程所学来处理更多的问题。7、参考文献1 余明兴、吴明哲.Borland c+ builder 5实例精解M.清华大学出版社，2003.7.2 严仕伟.c+ builder程序员学习数据结构M.人民邮电出版社，2003.3 王小华.c+ builder编程技巧、经验与实例M.人民邮电出版社，2004.1.