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

河南工程学院《数据结构与算法》课程设计成果报告树与二叉树的转换学生学号:学生姓名:学院:计算机学院专业班级:软件工程1342班专业课程:《数据结构与算法》指导教师:2014年12月29日题目树与二叉树的转换考核项目考核内容得分平时考核(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计(20分)分析系统的功能模块编程调试(20分)实现系统的各个功能模块,并完成调试回答问题(15分)回答老师针对课程设计提出的问题课程设计报告撰写(10分)严格按照规范要求完成课程设计报告源代码(5分)按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:年月日目录1课程设计目标与任务 12分析与设计 73程序清单 84测试 145总结 16参考文献 ,在数据结构的选择和应用、算法的设计与实现方面得到训练,加深对数据结构基本内容的理解和灵活应用,同时,在程序设计方法及上机操作方面受到比较系统严格的训练,培养软件工作所需要的动手能力。,通过数据结构课程设计各方面得到锻炼:(1)能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法;(2)通过上机实****验证自己设计的算法的正确性,学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改;(3)培养算法分析能力,分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平;(4)尽可能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来,获得算法的直观感受。,以便在程序设计中调用,要求:(1)实现树与二叉树的转换;(2)最好能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来;(3)给出若干例程,演示通过调用自己所缩写程序来实现相关问题的求解。,其中包含树的结构体的建立,树队列的结构体的建立,以及对树和二叉树的遍历,包含递归算法的使用,还有树队列和二叉树队列的初始化、判空、入队和出队等操作,队列能为二叉树遍历提供先进先出的访问条件。,即每个数据结点至多只有一个前驱,但可以有多个后继。它可采用顺序存储结构和链式存储结构。,就是用一组连续的存储单元存放二叉树中的结点。如图所示:,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。如图所示::(1)加线:在兄弟之间加一连线;(2)抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系;(3)旋转:以树的根结点为轴心,将整树顺时针转45°。::(1)加线:若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子……沿分支找到的所有右孩子,都与p的双亲用线连起来;(2)抹线:抹掉原二叉树中双亲与右孩子之间的连线;(3)调整:将结点按层次排列,形成树结构。::typedefstructst1//树结点的类型{chardata;//数据域,采用char星structst1*children[DEGREE];//指向孩子结点的指针域}CTreeNode;typedefstructst2{chardata;//数据域structst2*lchild,*rchild;//左右孩子结点的指针}BTreeNode;:{CTreeNode*CTreeArray[MAX_NODE_NUM];//结构体指针数组,存放结点的地址//structnodeCTree*next;intCTreeFront,CTreeRear;}QueueCTree;{BTreeNode*BTreeA