数据结构与算法课程设计-线索二叉树的应用

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

1、线索二叉树的运用数学与计算机学院课程设计说明书课程名称:数据结构与算法课程设计课程代码:题目:线索二叉树的应用年级/专业/班:2010级软件1班学生姓名:学　　号:1127开始时间:2011年12月9日完成时间:2011年12月23日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总分（100）指导教师签名：年月日线索二叉树的运用摘要首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然

2、后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。关键词：线索化；先序遍历；中序遍历；后续遍历线索二叉树的运用引言数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“线索二叉树的应用”，完成将二叉树转化成线索二叉树，采用前序、中

3、序或后序线索二叉树的操作。本课程设计采用的编程环境为MicrosoftVisualStdio2008。线索二叉树的运用目录1需求分析32开发及运行平台43概要设计54详细设计75调试分析126测试结果137结论18致谢19参考文献20附录21线索二叉树的运用-23-线索二叉树的运用1、需求分析为了能更熟练精准的掌握二叉树的各种算法和操作，同时也为了开拓视野，综合运用所学的知识。为此，需要将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树，以实现线索树建立、插入、删除、恢复线索等。1.1任务与分析中次系统要实现对二叉树的建立，以及线索化该二叉树，同时实现对其先序、中序、后序线索话的并

4、输出结果。1.2测试数据表1：入的二叉树结点序号和数据结点序号数据111222333444555666777888999-23-线索二叉树的运用2开发及运行平台开发平台：MicrosoftVisualStudio2008运行平台：WindowsXP/2003/7-23-线索二叉树的运用3概要设计3.1ADT描述ADTBiTree{数据对象：D={“树节点”}；数据关系：R＝{H}若D=∮为空，则R=∮,Tree为空树；若D仅有一个数据元素，则R=∮；否则R={H}详细描述如下：D中存在唯一的称之为根的节点root，它在关系H下无前驱；1.若D-{root}≠∮，则存在对根以外剩余元素的一

5、个划分D1、D2......，Dm（m>0），并对任意j≠k（1≦j≦m，1≦k≦m）有Dj∩Dk=∮；且对任意i（1≦i≦m）唯一存在数据元素xi∈Di，有二元关系∈H。这里描述的是从总节点到各个子树根节点xi的边。2.对应于D-{root}的划分，关系集H-{，，......}也有唯一的划分H1、H2......Hm(m>0)，并且对任意的j≠k（1≦j≦m，1≦k≦m）有Hj∩Hk=∮，对任意的i（1≦i≦m），Hi是Di上的二元关系，则（Di，{H}）是一颗树，且是root的子树。基本操作：voidcreat

6、();//创建一个二叉树。voidinorder();//中序便利。voidThTree::threpreorder();//先序遍历二叉树。voidThTree::threinorder();//中序遍历二叉树。voidThTree::threpostorder();//后序遍历二叉树。voidThTree::destroy();//删除线索二叉树。intmain();//主函数。}-23-线索二叉树的运用3.2程序模块结构图2程序模块结构3.2.1结构体定义书的结构体定义如下：structThreNode//定义结点结构体{ElemTypedata;ThreNode*lch;Thre

7、Node*rch;intltag,rtag;};3.3　各功能模块新建模块:voidThTree::creat()新建二叉树并储存。树类模块:voidThTree()定义书的结点，孩子以及各成员函数。先序遍历模块:voidThTree::threpreorder()对树进行先序线索遍历。中序遍历模块:voidThTree::threinorder()对树进行中序线索遍历。后序遍历模块:voidThTree::threpostorde