数据结构与算法课程设计：线索二叉树的基本操作

《数据结构与算法课程设计：线索二叉树的基本操作》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、线索二叉树的基本操作数学与计算机学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:6014389题目:线索二叉树的基本操作年级/专业/班:2012级软件工程4班学生姓名:吴海燕学号:开始时间:2013年12月18日完成时间:2013年12月28日课程设计成绩：学习态度及平时成绩（20）技术水平与实际能力（20）完成情况(20)创新（5）说明书（计算书、图纸、分析报告）撰写质量（35）总分（100）指导教师签名：年月日线索二叉树的基本操作目录1需求分析11.1任务与分析11.2测试数据22概

2、要设计32.1模块划分32.2模块中的层次图33　详细设计43.1结构体设计43.2创建二叉树43.3二叉树线索化53.4二叉树中插入结点63.5删除结点函数83.6查找前驱后继函数114调试分析125　用户使用说明126　测试结果126.1新建二叉树126.2中序遍历136.3查找前驱136.4查找后继146.5删除结点146.6插入左孩子156.7插入右孩子156.8退出16结论17致谢18参考文献19线索二叉树的基本操作摘要首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测

3、试数据。其次是概要设计，说明模块的划分以及模块间的层次关系，然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：线索化,中序遍历,插入，删除，查找线索二叉树的基本操作引言数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知

4、识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“线索二叉树的基本操作”，完成将二叉树转化成线索二叉树，采用中序线索二叉树的操作。本课程设计采用的编程环境为MicrosoftVisualStudio2008。1需求分析当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针

5、，将降低存储空间的效率。我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有2n个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、

6、中序线索二叉树和后序线索二叉树三种。1.1任务与分析任务：建立一棵二叉树（用户自行输入二叉树，用“#”表示空格，按回车键结束），将其线索化，并实现以下功能：1)遍历二叉树（本程序使用中序遍历方法）2)在二叉树中插入一个结点19线索二叉树的基本操作3)删除二叉树的某个结点4)查找某个结点的前驱5)查找某个结点的后继分析：该任务是关于线索二叉树的运算，其中的基本运算应基于二叉树，但又有所不同，首先应了解的问题有：1)线索二叉树是如何建立的，是通过二叉树来实现线索化，还是直接进行线索化的输入。若由二叉树建

7、立而来，该二叉树应如何输入，对于具体的二叉树应该使初使用者明白使用的格式。2)该程序重点内容是有关于二叉树的插入、删除和查找前驱后继，在进行具体的操作时，规则是什么，依照什么原则。3)对于插入、删除、查找前驱后继等，其结果是否符合预订的目标，须由自己判定。1.2测试数据测试数据：ABD#G###CE##F##图1-1测试数据19线索二叉树的基本操作2概要设计2.1模块划分二叉树的建立函数：Creat(ThrNode*bt)中序遍历函数：voidInOrder()中序线索化函数：voidThrB

8、iTree(ThrNode*bt)查找结点函数：ThrNode*locate(ThrNode*bt,Tx)插入结点函数：voidInsertLeft(ThrNode*s,Tx,Ty)voidInsertRight(ThrNode*s,Tx,Ty)删除函数：voidDelete(ThrNode*child,ThrNode*F)查找结点的前驱、后继函数：ThrNode*Former(ThrNode*p)ThrNode<