数据结构与算法》课程设计-树与二叉树的转换.doc

河南工程学院《数据结构与算法》课程设计成果报告树与二叉树的转换学生学号:学生姓名:学院:计算机学院专业班级:软件工程1342专业课程:《数据结构与算法》指导教师:2014年12月29日题目树与二叉树的转换考核项目考核内容得分平时考核(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计(20分)分析系统的功能模块编程调试(20分)实现系统的各个功能模块,并完成调试回答问题(15分)回答老师针对课程设计提出的问题课程设计报告撰写(10分)严格按照规范要求完成课程设计报告源代码(5分)按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:年月日目录目录 31课程设计目标与任务 42分析与设计 103程序清单 104测试 18参考文献 (1)了解和掌握树的相关概念、遍历和存储表达方法。(2)了解和掌握二叉树的概念及性质、遍历和算法的实现。(3)能够编码实现树与二叉树之间的转换,具备初步的独立分析和设计能力。(4)在实际应用中学会运用树,能够理解、设计、分析和应用程序。(5)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。(1)实现树与二叉树的转换;(2)能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来;(3)给出若干例程,演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计编辑算法,实现树与二叉树转换,利用双亲表示法和树的孩子链表来实现树的遍历算法,以及树的表示及其遍历操作,并建立树与二叉树的对应关系。,构造出该二叉树;按先序次序输入二叉树中结点的值(一个字符),空格字符表示空树。。用栈实现非递归前序、后序的遍历的。还有对树的层序遍历以及树与二叉树的转换。,若要实现终端结点,最后以回车键建入数据。,他的特点是每个结点至多有两棵子树,并且,二叉树的子树有左右之分,其次序不能颠倒。,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置,其形式说明如下:#defineMAX_TREE_SIZE100typedefstructPTNode{//结点结构TElemTypedata;Intparent;//双亲结构}PTNode;typedefstruct{//树结构PTNodenodes[MAX_TREE_SIZE];INTR,N;//根的位置和结点数}PTree;,看成是一个线性表,且以单链表作存储结构,则n个结点有n个孩子链表。而n个头指针又组成一个线性表,为了便于查找,可采用顺序存储结构,这种存储结构可形式地说明如下:typedefstructCTNode{//孩子结点intchild; structCTNode*next;}*ChildPtr;typedefstruct{ TElemTypedata; ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{ CTboxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置}CTree;,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素,二叉树的顺序存储表示说明如下:#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;。二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成,二叉链表的定义和部分基本操作的函数说明如下:typedefstructBiTNod