二叉排序树.docx

1、二叉排序树淮阴工学院数据结构课程设计报告选题名称: 二叉排序树：用顺序表结构存储 系（院）: 计 算 机 工 程 系 专 业: 网 络 工 程 班 级: 网 络 107 姓 名: 周俊 学 号: 107*5 指导教师: 张亚红 张勇军 学年学期: 2008 2009 学年 第 2 学期 2009 年 6 月 20 日设计任务书课题名称二叉排序树：用顺序表结构存储设计目的通过一周的课程设计，用顺序表存储结构实现对二叉排序树的的创建，中序遍历，并计算其平均查找长度，查找和某个删除结点等基本操作，达到巩固和运用理论知识、锻炼实践能力、构件合理知识结构和提高程序设计能力的目的。实验环境Windows2

2、000 以上操作系统Visual C+6.0以上编译环境任务要求1、搜集二叉排序树方面的资料；2、编写代码，实现二叉排序树的创建，中序遍历，计算其平均查找长度，查找和删除某个结点；3、撰写课程设计报告；4、参加答辩。工作进度计划序号起止日期工 作 内 容12009.06.08搜集二叉排序树方面的资料22009.06.082009.06.10编写代码，上机调试32009.06.11撰写课程设计报告42009.06.11答辩指导教师（签章）： 2008 年 6 月 25 日 课题名称二叉排序树：用顺序表结构存储设计目的通过一周的课程设计，实现背包问题的回溯法求解，进一步加强对 数据结构中栈以及C+

3、编程算法中经典回溯法的理解与运用，达到巩固理论知识、锻炼实践能力、构建合理知识的目的。实验环境Windows2000以上操作系统Visual C+6.0以上编译环境任务要求1搜集背包问题相关的资料和回溯法的基本原理与算法分析；2编写代码，实现背包问题的回溯求解；3撰写PPT文件与课程设计报告；4参加答辩。工作进度计划序号起止日期工 作 内 容12009.06.08理论辅导，搜集资料22009.06.082009.06.10编写代码，上机调试32009.06.11撰写课程设计报告42009.06.11答辩指导教师： 2009 年 6 月 10 日 摘要：数据结构是研究与数据之间的关系，我们称这一

4、关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课程设计，程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点。关键词：二叉排序树；中序遍历；平均查找长度；删除结点1需求分析1.1课程设计题目、任务及要求二叉排序树。用顺序表

5、(一维数组)作存储结构 (1)以回车(-1)为输入结束标志,输入数列L，生成一棵二叉排序树T；(2)对二叉排序树T作排序,输出结果；(3)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,否则输出信息“无x”；1.2课程设计思想建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录

6、每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：1、该结点左右子树均为空；2、该结点仅左子树为空；3、该结点仅右子树为空；4、该结点左右子树均不为空。1.3软硬件运行环境及开发工具Windows2000以上操作系统、Microsoft Visual C+ 6.02概要设计2.1 二叉排序树的定义二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树： 若它的左子

7、树非空，则左子树上所有结点的值均小于根结点的值； 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树。2.2一维数组的存储结构建立二插排序树，首先用一个一维数组记录下读入的数据，然后再用边查找边插入的方式将数据一一对应放在完全二叉树相应的位置，为空的树结点用“0” 补齐。2.3建立二叉排序树从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：（1）若为

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

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

10、果给定值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。2.7二叉排序树的插入在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。所以在插入之前，先使用查找算法在树中检查要插入的元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。 插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中； 当非空时，将待插结点关键字S-key和树根关键字t-key进行比较， 若s-

11、key = t-key,则无须插入，若s-keykey,则插入到根的左子树中， 若s-key t-key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。3详细设计和实现3.1主要功能模块设计程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：退出，排序，插入节点和删除结点。主函数流程如下：3.2主程序设计/*以下是用c+ 实现的二叉排序树的源代码*/#includetypedef struct TreeNodeint key;struct

12、 TreeNode *left;struct TreeNode *right;treeNode;class BiSortTreepublic: BiSortTree(void);void desplayTree(void);/显示这个树void insertTree(int key);/在树中插入一个值 deleteTree(int key);/在树中删除一个值 treeNode* searchTree(int key);/在树中查找一个值BiSortTree();private:treeNode* buildTree(treeNode* head,int number);/建立一个树tree

13、Node* search(treeNode* head ,int key);/查找treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p);/查找出p的父亲节点的指针treeNode* BiSortTree:searchMinRight(treeNode* head);/找到右子树中最小的节点void showTree(treeNode* head);/显示 void destroyTree(treeNode* head);/删除treeNode *Head;/*以下是建立一个二叉排序树*/BiSortTree:BiSortTr

14、ee() cout建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): number; while(number!=-1) Head=buildTree(Head,number); cinnumber; treeNode* BiSortTree:buildTree(treeNode* head,int number)treeNode *p; p=new treeNode; p-key=number;p-left =p-right=NULL;if(head=NULL) return p;else if(p-key key)head-left=buildTree(head-lef

15、t,number); else head-right=buildTree(head-right,number); return head;/*以下是在一棵二叉排序树插入一个数*/void BiSortTree:insertTree(int key)Head=buildTree(Head,key);/*以下是在一个二叉排序树查找一个数是否存在*/treeNode* BiSortTree:searchTree(int key)return search(Head,key);treeNode* BiSortTree:search(treeNode* head ,int key) if(head=NU

16、LL)return NULL;if(head-key=key)return head;elseif(keykey )return search( head-left,key); elsereturn search(head-right,key);/*以下是在一个二叉排序树删除一个给定的值*/BiSortTree:deleteTree(int key)treeNode *p;p=NULL; p=search(Head,key);if(p=NULL)coutleft=NULL&p-right=NULL)/叶子节点 if(parent-left=p)parent-left=NULL; elsepar

17、ent-right=NULL; else/非叶子节点 if(p-right=NULL)/该节点没有右孩子 if(parent-left=p) parent-left=p-left ; else parent-right=p-left; else/该点有左右孩子 treeNode * rightMinSon,* secondParent;/secondParent为右子树中的最小节点的父亲 rightMinSon=searchMinRight(p-right); secondParent=searchParent(p-right ,rightMinSon); secondParent-left=

18、rightMinSon-right; if(p-right=rightMinSon)/右子树中的最小节点的父亲为p p-right=rightMinSon-right ; p-key=rightMinSon-key ; treeNode* BiSortTree:searchParent(treeNode* head,treeNode* p)if(head-left=p|head-right=p|head=p|head=NULL)return head; elseif(p-keykey)return searchParent(head-left ,p);elsereturn searchPare

19、nt(head-right ,p);treeNode* BiSortTree:searchMinRight(treeNode* head)/找到右子树中最小的节点if(head-left =NULL|head=NULL)return head;elsereturn searchMinRight(head-left);/*以下是显示一个二叉排序树*/void BiSortTree:desplayTree(void)showTree(Head);coutleft ) ; coutkeyright) ;/*以下是删除一棵整二叉排序树*/BiSortTree:BiSortTree()cout已经消除了

20、一棵树left );destroyTree(head-right );delete head;/*主函数*/void print() coutendlendl以下是对二叉排序树的基本操作:endl1.显示树endl 2.插入一个节点endl3.寻找一个节点endl4.删除一个节点endl;void main()BiSortTree tree; int number;int choiceNumber; char flag;while(1) print() ; cout请选择你要进行的操作(14)choiceNumber; switch(choiceNumber) case 1: tree.des

21、playTree();break; case 2: cout请插入一个数: number; tree.insertTree(number); tree.desplayTree(); break; case 3: cout请插入你要找数: number; if(tree.searchTree(number)=NULL) cout没有发现endl; else cout发现endl; break; case 4: cout请输入你要删除的数: number; tree.deleteTree(number); tree.desplayTree(); break; default: break; cou

22、t你是否要继续(Y/N)?flag; if(flag=N|flag=n)break; 4调试与操作说明4.1程序调试图4.1.1 调试界面在程序调试过程当中，编译时并没有报错，但是运行时总是出错，在查阅资料和老师的帮助下，发现程序未对数组初始化。添加数组初始化代码：T.data=(int *)malloc(N*sizeof(int);4.2程序操作说明输入一组数列，以结-1结束：图4.2.1运行界面一显示数：图4.2.2运行界面二插入一个数：图4.2.3运行界面三删除一个结点：图4.2.4运行界面四总 结这次课程设计使我对做系统的认识深刻了许多。我真正体会到了在整个过程给我带来的无奈与快乐。综

23、合起来，主要体现在以下几个方面：首先，我对数据结构掌握的还不错，在设计二叉树时候没有费多少功夫。但是由于在宿主语言上的不足给我很大的打击。眉毛胡子一把抓，没有实质性的进展。我终于认识到问题的根源所在。然后我只好再次认真细致地对开发过程进行了规划和分析，才逐渐弄清了整个系统的流程。其次，在编程语言的熟悉程度也让我对整个开发过程受到了一定的阻碍。编程知识的不足使我沮丧过，但是认识到我的不足，我于是就向精通c+的同学进行探讨，终于解决了一些难题。总的来说，这次课程设计给了我很大启发，不管什么问题，只要抓住根源，从不同方面去攻破它，终究会成功，生活也如此。致 谢历经一个星期的课程设计结束了，我也松了一

24、口气。应该说这个星期是个收获不少的星期，我在这个星期中学到了很多的东西，特别是团结的精神。 一开始对这个课程设计不是很有兴趣，因为有很多的东西我无法弄懂，就连里面最基本的东西我都要费很大的精力才能略知皮毛，就别谈做完整个课题了，有时候真的想放弃，一走了之，但是想想，这也是锻炼自己的好机会，就硬着头皮做下去，但是越是到最后就越做不下去，不懂得东西逐渐增多，这使我对本来最基本的框架都模糊了，找不到头绪，但是在这个时候，我的同学帮助了我，他不但更我讲了如何设计基本的框架，还教会了我怎么利用书籍库查询，我受益匪浅，与此同时我也上网查询了很多的资料，发现基本上框架是相似的，就是实现的方法不同，也就是说，

25、不同是因为她们用了不同德语言，我用的是access结合vb做出来的，vb的功能很强大，其实在试验过程中，我最要感谢的就是我们的实验老师，他给了我很大的帮助以及动力，当在我想放弃的时候，总是他给我我莫大的帮助，让我信心百倍，让我重拾信心，最终我调试出了结果，我很高心很开心。这对我以后的学习计算机的知识有了很大的鼓舞。我相信只要坚持不懈，总会有结果的。参 考 文 献1.魏雪萍.新编Word2003入门与提高.北京:人民邮电出版社,20052.王宏生.数据结构.北京:国防出版社,2006.13.潭浩强.程序设计.北京：清华大学出版社，20004.严蔚敏，吴伟民.数据结构.北京：清华大学出版,2001

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