线索二叉树课程设计说明书-模板.docVIP

数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 6014389 题 目: 线索二叉树的应用 年级/专业/班: 2010级软件1班 学 生 姓 名: 学　　 号: 312010080611127 开 始 时 间: 2011 年 12 月 9 日 完 成 时 间: 2011 年 12 月 23 日 课程设计成绩： 学习态度及平时成绩（30） 技术水平与实际能力（20） 创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45） 总 分（100） 指导教师签名： 年 月 日 摘 要 首先是对需求分析的简要阐述，说明系统要完成的任务和相应的分析，并给出测试数据。其次是概要设计，说明所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次关系，以及ADT描述。然后是详细设计，描述实现概要设计中定义的基本功操作和所有数据类型，以及函数的功能及代码实现。再次是对系统的调试分析说明，以及遇到的问题和解决问题的方法。然后是用户使用说明书的阐述，然后是测试的数据和结果的分析，最后是对本次课程设计的结论。 关键词：线索化；先序遍历；中序遍历；后续遍历  引 言 数据结构是计算机专业重要的专业基础课程与核心课程之一，在计算机领域应用广泛，计算机离不开数据结构。数据结构课程设计为了能使我们掌握所学习的知识并有应用到实际的设计中的能力，对于掌握这门课程的学习方法有极大的意义。本课程设计的题目为“线索二叉树的应用”，完成将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树的操作。本课程设计采用的编程环境为Microsoft Visual Stdio 2008。 目 录 1需求分析 3 2开发及运行平台 4 3 概要设计 5 4 详细设计 7 5 调试分析 12 6 测试结果 13 7 结论 18 致 谢 19 参考文献 20 附 录 21  1、需求分析 为了能更熟练精准的掌握二叉树的各种算法和操作，同时也为了开拓视野，综合运用所学的知识。为此，需要将二叉树转化成线索二叉树，采用前序、中序或后序线索二叉树，以实现线索树建立、插入、删除、恢复线索等。 1.1任务与分析 中次系统要实现对二叉树的建立，以及线索化该二叉树，同时实现对其先序、中序、后序线索话的并输出结果。 1.2测试数据 表1：入的二叉树结点序号和数据 结点序号 数据 1 11 2 22 3 33 4 44 5 55 6 66 7 77 8 88 9 99 2开发及运行平台 开发平台：Microsoft Visual Studio 2008 运行平台：Windows XP/2003/7 3 概要设计 3.1 ADT描述 ADT BiTree{ 数据对象：D={“树节点”}； 数据关系：R＝{H} 若D=∮为空，则R=∮,Tree为空树； 若D仅有一个数据元素，则R=∮； 否则R={H}详细描述如下： D中存在唯一的称之为根的节点root，它在关系H下无前驱； 若D-{root}≠∮，则存在对根以外剩余元素的一个划分D1、 D2......，Dm（m0），并对任意j≠k（1≦j≦m，1≦k≦m）有Dj∩Dk=∮；且对任意i（1≦i≦m）唯一存在数据元素xi∈Di，有二元关系root,xi∈H。这里描述的是从总节点到各个子树根节点xi的边。 对应于D-{root}的划分，关系集H-{root,x1， root,x2，......root,xm}也有唯一的划分H1、H2......Hm(m0)，并且对任意的j≠k（1≦j≦m，1≦k≦m）有Hj∩Hk=∮，对任意的i（1≦i≦m），Hi是Di上的二元关系，则（Di，{H}）是一颗树，且是root的子树。 基本操作： void creat ();//创建一个二叉树。 void inorder ();//中序便利。 void ThTree::threpreorder ();//先序遍历二叉树。 void ThTree::threinorder ();//中序遍历二叉树。 void ThTree::threpostorder ();//后序遍历二叉树。 void ThTree::destroy ();//删除线索二叉树。 int main();//主函数。 } 3.2程序模块结构