数据结构课程设计报告——二叉排序树(用顺序表结构存储).doc

1、摘要：数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“树形结构”作为其数据结构。而二叉搜索树又是一种特殊的二叉树。本课程设中的二叉排序树是基于二叉链表作存储结构的，一共要实现五项基本的功能。它们分别是二叉搜索树的创建、中序遍历、查找结点、删除结点和计算二叉排序树搜索成功时的平均查找长度。关键词：二叉排序树；中序遍历；搜索结点；删除结点；平均查找长度目录1需求分析11.1课程设计题目、任务及要求11.2课程

2、设计思想12概要设计22.1 二叉排序树的定义22.2二叉链表的存储结构22.3建立二叉排序树22.4二叉排序树的生成过程32.5中序遍历二叉树32.6二叉排序树的查找32.7二叉排序树的插入42.8平均查找长度43详细设计和实现43.1主要功能模块设计43.2主程序设计54调试与操作说明124.1程序调试124.2程序操作说明13总 结16致 谢17参 考 文 献181需求分析1.1课程设计题目、任务及要求二叉排序树。用二叉链表作存储结构 (1)以(0)为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作中序遍历,输出结果；(3)计算二叉排序树T查找成功的平均查找长度,输

3、出结果；(4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；1.2课程设计思想建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。对二叉排序树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。由于二叉排序树自身的性质，左子树小于根结点，而根结点小于右子树，所以中序遍历的结果是递增的。计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录

4、每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。 2概要设计2.1 二叉排序树的定义二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：（1）每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同；（2） 若它的左子树非空，则左子树上所有结

5、点的值均小于根结点的值；（3） 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；（4） 左、右子树本身又各是一棵二叉排序树。2.2二叉链表的存储结构建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点。2.3建立二叉排序树从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点

6、指针，b为当前待插入元素，其过程可以描述为：（1） 若为空树（p=nil），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。（2） 若非空树，比较b与根结点数据data（p）如果bdata和树根关键字subtree-data进行比较， 若s-data= subtree- data,则无须插入，若s- data data,则插入到根的左子树中， 若s- data subtree- data,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。2.8

7、平均查找长度计算二叉排序树的平均查找长度时，采用类似先序遍历的递归方式，用count记录所有结点的总深度，deep记录每个结点的深度，count置初值为0，采用累加的方式最终得到所有结点总深度count。平均查找长度就等于count/i(i为树中结点的总个数)。3详细设计和实现3.1主要功能模块设计程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：退出，中序遍历，搜索，删除结点和计算平均查找长度，另外还有一个附加功能计算所有结点的个数，用来计算平均查找长度。主函数流程如下：否否否否否是创建二叉排序树Switch(1)中序遍历Switch(0)Exit(0)

8、退出Switch(3)删除结点Switch(2)Switch(4)平均搜索长度搜索结点是是是是是是是是图3.1.1主函数流程图3.2主程序设计void main () int deep;cout输入一组数据建立二叉搜索树，以0结束endl;BinaryTreebr(0);BinTreeNode*subtree=br.GetRoot ();int choicenumber;char flag; /判断是否还要继续进行 int number; int number2;while(1)show(); /显示主要功能cout请选择你要进行的操作：15choicenumber;switch(choice

9、number)case 0: exit(0);break;case 1:cout显示树的结点：endl;br.print ();break;case 2:cout结点个数为：; cout br.Size ()endl;break;case 3:coutnumber;if(br.search (number)=NULL)cout没有找到numberendl;else cout找到numberendl;break;case 4:cout输入你要删除的结点:number2;if(br.search (number2)!=NULL)br.remove (number2);cout删除结点后的二叉搜索树

10、为：endl;br.print ();elsecout你要删除的结点不存在!endl;break;case 5: deep=0;double asl;asl=br.Height(subtree,deep)/(br.Size ()*1.0);cout二叉排序树查找成功的平均查找长度:aslendl;br.GetCount(); /在每次计算平均长度之后都将count置零break;default: break;cout你是否要继续(Y/N)?flag;if(flag=N|flag=n)break;template struct BinTreeNode /二叉树结点类定义E data; /数据域B

11、inTreeNode *leftChild,*rightChild; /左子女、右子女链域BinTreeNode(E x,BinTreeNode*l=NULL,BinTreeNode*r=NULL)data=x;leftChild=l;rightChild=r;/二叉排序树类定义templateclass BinaryTreeprivate:int count; / 用来表示所有结点的深度之和BinTreeNode*root; /二叉树根结点指针K Refvalue; /输入停止标志int Size(BinTreeNode*subtree); /结点的个数bool insert(E &t,Bi

12、nTreeNode*&subtree);/插入结点void print (BinTreeNode*subtree); /显示二叉搜索树的结点BinTreeNode*search(K key,BinTreeNode*subtree); /递归：搜索bool remove(K key,BinTreeNode*&subtree);/在树中删除一个含k的结点public:BinaryTree()root=NULL; BinaryTree(K value); / 构造函数BinaryTree(); / 析构函数BinTreeNode*GetRoot()return root; /返回头指针int Get

13、Count() count=0;return count; / 将count置零bool search(K key)return search(key,root)!=NULL?true:false; /递归：搜索bool insert(E &t)return insert(t,root); /插入结点int Size()return Size(root); /返回二叉树的结点数void print()print(root); /显示二叉搜索树的结点 bool remove(K k)return remove(k,root);/在树中删除一个值int Height( BinTreeNode*su

14、btree ,int deep ); /高度;/ *建立二叉搜索树的算法*template BinaryTree:BinaryTree(K value) /输入一个元素序列，建立一颗二叉搜索树K x; count=0;root=NULL;Refvalue=value;cout输入数据：x;while(x!=Refvalue) /Refvalue是一个输入结束标志insert(x,root); /插入，再输入数据 cinx;/ * 计算所有结点的深度之和即所在的层次之和 *template int BinaryTree :Height (BinTreeNode*subtree ,int deep

15、 )if(subtree)deep+; /记录当前结点的在当前树中的深度count=count+deep; /记录已遍历过的点的深度之和Height(subtree-leftChild,deep );Height(subtree-rightChild,deep );return count;/ * 显示二叉搜索树的结点 *templatevoid BinaryTree:print(BinTreeNode*subtree) /利用的是中序输出，输出后的数是按照从小到大的顺序排列的 if(subtree!=NULL)print(subtree-leftChild);cout datarightCh

16、ild);/ * 插入结点t *template bool BinaryTree:insert(E &t,BinTreeNode*&subtree)if(subtree=NULL)subtree=new BinTreeNode(t);return true;else if(tdata)insert(t,subtree-leftChild);return true;else if(tsubtree-data)insert(t,subtree-rightChild);return true;else return false;return false;/ * 删除节点k *template boo

17、l BinaryTree:remove(K k,BinTreeNode*&subtree)BinTreeNode* temp;if (subtree!=NULL)if(kdata)remove(k,subtree-leftChild);else if(ksubtree-data)remove(k,subtree-rightChild);else if(subtree-leftChild!=NULL&subtree-rightChild!=NULL) /subtree指示关键码为k的结点，它有两个结点，在右子树树上找中序第一个子女填补temp=subtree-rightChild; /到右子树树

18、上找中序第一个子女填补while(temp-leftChild!=NULL)temp=temp-leftChild;subtree-data=temp-data; /用该结点数据代替删除结点数据 remove(subtree-data,subtree-rightChild); /继续向右子树查找，将树连接好else /subtree指示关键码为k的结点，它只有一个孩子子树或零个子树temp=subtree;if(subtree-leftChild=NULL)subtree=subtree-rightChild;elsesubtree=subtree-leftChild;delete temp;

19、return true;return false;/ * 查找关键字为k*templateBinTreeNode*BinaryTree:search(K key,BinTreeNode*subtree)if(subtree=NULL)return NULL;if(key=subtree-data)return subtree;else if(keydata)return search(key,subtree-leftChild); /若比该结点小，那就向它的左子树继续搜索else if(keysubtree-data)return search(key,subtree-rightChild);

20、 /若比该结点大，那就向它的右子树继续搜索 else return subtree;/ * 输出二叉树结点数 *template int BinaryTree:Size (BinTreeNode*subtree) /计算以*subtree为根的二叉树的结点数if(subtree=NULL)return 0;elsereturn 1+Size(subtree-leftChild)+Size(subtree-rightChild); /左子树的;#endif 4调试与操作说明4.1程序调试图4.1.1 调试界面4.2程序操作说明1）输入一组数列，以结0结束：图4.2.1运行界面一2）中序遍历：图4

21、.2.2运行界面二3）计算搜索成功时的平均查找长度：图4.2.3运行界面三4）查找结点： 图4.2.4运行界面四5）查找不存在的结点图4.2.5运行界面五6）删除已有结点：图4.2.6运行界面六7）删除结点后的平均搜索长度：图4.2.7运行界面七总结这次课程设计使我对数据结构认识深刻了许多，其中最深刻的是我理解了用二叉链表结构存储实现二叉排序树，同时也加深了对二叉树的理解。本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点,。在进行搜索时，还可以采用更好的搜索结构即动态搜索结构。当没有找到时，可以将其插入，而不是仅仅提示未找到。在进计算查找成功时

22、的平均查找长度，使用递归的方法虽然短小，但很难理解，可以采用层次遍历来统计所有结点的深度之和，这样就更容易理解。在此课题中，我遇到最大的一个问题就是如何求搜索成功时平均搜索长度？最后通过加上deep来记录每一结点的深度给解决啦，可是又出现了另外一个新的问题，当删除结点后再求平均搜索长度却又错啦？最后通过单步调试发现，当进行完一次计算平均搜索长度后，count(用来记录所有结点深度和)会随着下一次计算时同步增长。那就必须要在每进行完一次计算后，给count做清零处理！于是我就在类中加了一个对count 清零处理的函数，int GetCount() count=0；return count； 。从

23、而解决了这个最大的难题。通过一周的课程设计，我已经会用二叉链表存储结构实现对二叉排序树的的创建，中序遍历，并计算其平均查找长度，查找和某个删除结点等基本操作。但我同时也发现了自己许多不足之处 。首先，对数据结构的掌握还不够。虽然完成了程序，但是只用到了基本的结点以及链表，在数据结构的选择上避重就轻，覆盖面较小，不能很好的体现各种数据结构的掌握度，同时也缺少了适当的锻炼，在这方面还需要自己主动去提高。其次，在程序整体的设计上还不够完善，各模块可以适当增加内容，界面还可以更加的人性化些，这样整个程序才具有更强的美观性与实用性。总而言之，这次课程设计给了我很大启发，我明白了，不管遇到什么问题，只要抓

24、住根源，不气馁，从不同方面去攻破它，终究会成功，生活也是如此。 致谢本次课程设计中，除了通过自己的努力，同时得到了很多来自他方的帮助，在这里我要谢谢所有帮助过我的老师同学。首先，我要谢谢淮阴工学院计算机工程系给我提供了这次难得的实践机会，以及实验室人员提供的方便舒适的实验环境！其次，我要谢谢这次课程设计的辅导老师给予我的帮助和辛勤指导，以及和我一起分析问题的同学。刚开始时，遇到了一些难题，自己实在做不下去了，指导老师悉心地给我指导，让我慢慢的有了头绪。在设计过程中，困难与麻烦是很多的，如果没有他们的悉心指导与共同研讨，我也不能这么顺利的完成本次的课程设计，在这里衷心得对他们表示深深的谢意。最后

25、，我要谢谢我的同学宋可、马良、陆国建等，多谢他们给我所提的建议以及他们给予我的帮助。当然，在本次课程设计的完成过程中，我也参考了很多资料参考书，以及浏览了很多网站。所以我也要谢谢这些书籍的著作者，及各网站提供信息的作者们。在这里还要特别谢谢网站给我的帮助。 同时谢谢淮阴工学院图书馆，给我提供了丰富的书籍资料！参 考 文 献1.魏雪萍.新编Word2003入门与提高.北京:人民邮电出版社,20052.王宏生.数据结构.北京:国防出版社,2006.13.潭浩强.程序设计.北京：清华大学出版社，20004.严蔚敏，吴伟民.数据结构.北京：清华大学出版,20015.殷人昆.数据结构.北京：清华大学出版

26、社，20046.王晓东.数据结构与算法设计电子工业出版社 20027.陈慧南数据结构与算法 C+ 语言描述高等教育出版社 20058.窦延平等.数据结构与算法 C+上海交通大学出版社 2005指导教师评语学号1091301108姓名黄磊班级计算机1091选题名称二叉排序树(用二叉链表作结构存储)序号评价内容权重（%）得分1考勤记录、学习态度、工作作风与表现。52自学情况：上网检索机时数、文献阅读情况（笔记）。103论文选题是否先进，是否具有前沿性或前瞻性。54成果验收：是否完成设计任务；能否运行、可操作性如何等。205报告的格式规范程度、是否图文并茂、语言规范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。306文献引用是否合理、充分、真实。57答辩情况： 自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。25合计指导教师（签章）： 2010 年 12 月 31 日 .20