树与二叉树的转换及二叉树的遍历 设计报告.docx

树与二叉树的转换及二叉树的遍历 设计报告 信息与电气工程学院 软件算法综合设计说明书（20 /20 学年第学期） 题目_树与二叉树的转换及二叉树的遍历_ 专业班级_计算机科学与技术09级1班_ 姓名学号_ 指导教师_ 设计周数_1周_ 设计成绩_ 2022 年07 月日 树的应用 1课程设计题目 实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。 要求：遍历的内容应是千姿百态的。 2.课程设计目的及基本要求 数据结构课程设计是计算机科学与技术专业集中实践性环节之一，是学习完数据结构课程后进行的一次全面的综合练习。其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。 3. 课程设计教材及主要参考资料： （1）严慰敏编数据结构习题集清华大学出版社 （2）胡学军编数据结构高等教育出版社 教学参考书 （1）严慰敏编数据结构习题集清华大学出版社 （2）胡学军编数据结构高等教育出版社 目录 一、设计目的 二、问题描述 三、需求分析 四、概要设计 五、详细设计 六、调试分析 七、用户使用说明 八、测试结果 九、总结及分析 数据结构课程设计-树与二叉树的转换及二叉树的遍历 1.设计目的 通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。根 据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻 辑结构，合理地选择相映的存储结构，并能设计出解决问题的有效算法。 2.问题描述 要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次 序的非递归算法的实现，应包含建树的实现。 3.需求分析 本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、 和后序遍历，还有对树的层序遍历以及树与二叉树的转换。 本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。 本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍 历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。 4.概要设计 4.1.二叉树创建 用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。 图 1、二叉树的创建 4.2.树与二叉树的转换算法 转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。void exchange()，class Tree 4.3.先序遍历二叉树的递归算法 若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void PreOrder(BiNode root)。 图2、前序递归遍历 4.4.中序遍历二叉树的递归算法 若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。void InOrder(BiNode root)。 图3、中序递归遍历 4.5.后序遍历二叉树的递归算法 若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)。 图4、后序递归遍历 4.6.先序非递归算法 BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。 问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取 BiNode 的右子树的根指针？void F_PreOrder(BiNode root) 图5、前序非递归遍历 4.7.中序非递归算法 BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取BiNode 指针？void F_inOrder(BiNode root)。 图6、中序非递归遍历 4.8.后序非递归算法 BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)。 图7、后序非递归遍历 4.9.层次序遍历算法 按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。 图8、层序遍历 5.详细设计 源程序：