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

数学与计算?机学院 课程设计说?明书 课 程 名 称: 数据结构与?算法课程设?计 课 程 代 码: 60143?89 题 目: 线索二叉树?的应用 年级/专业/班: 2010级?软件1班 学 生 姓 名: 学　　 号: 31201?00806?11127? 开 始 时 间: 2011 年 12 月 9 日 完 成 时 间: 2011 年 12 月 23 日 课程设计成?绩： 学习态度及?平时成绩（30） 技术水平与?实际能力（20） 创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45） 总 分（100） 指导教师签?名： 年 月 日 摘 要 首先是对需?求分析的简?要阐述，说明系统要?完成的任务?和相应的分?析，并给出测试?数据。其次是概要?设计，说明所有抽?象数据类型?的定义、主程序的流?程以及各程?序模块之间?的层次关系?，以及ADT?描述。然后是详细?设计，描述实现概?要设计中定?义的基本功?操作和所有?数据类型，以及函数的?功能及代码?实现。再次是对系?统的调试分?析说明，以及遇到的?问题和解决?问题的方法?。然后是用户?使用说明书?的阐述，然后是测试?的数据和结?果的分析，最后是对本?次课程设计?的结论。 关键词：线索化；先序遍历；中序遍历；后续遍历  引 言 数据结构是?计算机专业?重要的专业?基础课程与?核心课程之?一，在计算机领?域应用广泛?，计算机离不?开数据结构?。数据结构课?程设计为了?能使我们掌?握所学习的?知识并有应?用到实际的?设计中的能?力，对于掌握这?门课程的学?习方法有极?大的意义。本课程设计?的题目为“线索二叉树?的应用”，完成将二叉?树转化成线?索二叉树，采用前序、中序或后序?线索二叉树?的操作。本课程设计?采用的编程?环境为Mi?croso?ft Visua?l 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开发及运?行平台 开发平台：Micro?soft Visua?l Studi?o 2008 运行平台：Windo?ws XP/2003/7 3 概要设计 3.1 ADT描述? ADT BiTre?e{ 数据对象：D={“树节点”}； 数据关系：R＝{H} 若D=∮为空，则R=∮,Tree为?空树； 若D仅有一?个数据元素?，则R=∮； 否则R={H}详细描述如?下： D中存在唯?一的称之为?根的节点r?oot，它在关系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}）是一颗树，且是roo?t的子树。 基本操作： void creat? ();//创建一个二?叉树。 void inord?er ();//中序便利。 void ThTre?e::threp?reord?er ();//先序遍历二?叉树。 void T