二叉树的遍历及树与二叉树的转换.doc

山东科技大学课程设计 专业班级： 07—1 学生姓名： 王泽铭 一、课程设计（论文）题目 ⒈ 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现； ⒉ 树与二叉树的转换的实现。 数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。 熟练掌握树与二叉树的基本操作和实现。输入数据：问题1：二叉树的相关数据；问题2：一般树的相关数据。 1. 创建二叉树存储结构； 2. 用户可选择二叉树的三种序的递归、非递归遍历及按层次序遍历(以菜单/命令按钮形式表示)； 3. 树与二叉树的转换的实现； 4. 显示遍历次序； 5. 优化界面设计。 1. 本年级使用的教材：数据结构与算法分析（C++版）（第二版）影印版 2005.7 2. 数据结构与算法，科学出版社，2005.08；赵文静 祁飞等编著 3. 数据结构-C++语言描述，西安交通大学出版社，1999.01，赵文静编著 4. 《Visual C++编程实例》(任意一本此类书籍) 一．设计目的二．问题描述三．需求分析四．概要设计五．详细设计六．测试分析………………………………………………七．使用说明……………………………………八．总结九．参考文献《数据结构》课程设计模板—二叉树的遍历及树与二叉树的转换一．设计目的 通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 二．问题描述要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序非递归算法的实现，应包含建树的实现。 三．需求分析 本程序的功能是对任意二叉树进行递归前序遍历、中序遍历和后序遍历，用栈实现递归的前序中序遍历，本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。 本程序的结果将依次打印出递归前序遍历、中序遍历和后序遍历，用栈实现递归的前序和中序遍历，和线索化。 演示程序以用户与计算机对话的方式进行,即在计算机终端上显示提示信息后,由用户在键盘上输入演示程序中规定的命令,相应的输入数据和运算结果显示在其 四．概要设计 1、二叉树创建 用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。 BiNode creat()，BiNode stree_creat(char *a,int k)。 2．先序遍历二叉树的递归算法 若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。void PreOrder(BiNode root)。 3中序遍历二叉树的递归算法 若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。void InOrder(BiNode root)。 4先序遍历二叉树的递归算法 若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)。 5．先序非递归算法 BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。 问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取 BiNode的右子树的根指针？void F_PreOrder(BiNode root) 6．中序非递归算法 BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取BiNode指针？void F_inOrder(BiNode root)。 7．后序非递归算法 BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder(BiNode root)。 8．层次序遍历算法 按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。void LevelOrder(BiNode root)。 9．树与二叉树的转换算法 转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的有孩子。void exchange()，class Tree. 五．详细设计 图 1、二叉树的创建