《二叉树的遍历课程设计》由会员分享，可在线阅读，更多相关《二叉树的遍历课程设计（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计0数据结构课程设计报告设计题目： 二叉树的遍历 姓 名： 陈 雷 学 号： 211001047 专 业： 计算机科学与技术 院 系： 计算机科学与技术 班 级： 1002 指导教师： 吴克力 2012 年 3 月 1 日 数据结构课程设计1摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为 VC+，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键字：二叉树 遍历 非递归 C+ LCA
2、数据结构课程设计2Abstract: This paper mainly describes how to implement binary tree traversal. The binary tree traversal is based on binary tree binary storage structure. Traversal method includes: preorder traversal,inorder traversal, postorder traversal, levelorder traversal. The former preorder traversal
3、 and postorder use of non - recursive algorithm. Programming environment is VC + +, in addition to traversal operation, also increased for solving the binary tree depth 、 summary points and each layer of nodes, as well as the most recent common ancestor ( LCA ) algorithm.Keywords: binary tree traver
4、sal non-recursive C+ LCA数据结构课程设计3目 录一、问题描述 .4问题描述：创建二叉树并遍历 .4基本要求： .4二、需求分析 .4三、概要设计 .41创建二叉树 .42二叉树的非递归前序遍历示意图 .43二叉树的后序非递归遍历示意图 .5四、数据结构设计 .51 二叉树结点数据类型定义为： .52 二叉树数据类型定义为： .5五、算法设计 .61、创建二叉树 .62、非递归前序遍历 .73、非递归后序遍历 .74、求二叉树的高度 .85、 求二叉树每一层的结点数 .96、求两节点最近共同祖先 .96、算法流程图 .10六、程序测试与实现 .111、函数之间的调用关系
5、.112、主程序 .113、测试数据 .134、测试结果 .13七、调试分析 .14八、遇到的问题及解决办法 .15九、心得体会 .15十、参考文献 .15数据结构课程设计4一、问题描述问题描述：创建二叉树并遍历基本要求：1、 分别运用非递归的方式完成对二叉树的先序和后序遍历2、 输出二叉树的高度3、 输出每一层的结点数4、 查找结点 P 和结点 Q 的最近共同祖先二、需求分析1 本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2 程序运行后显现提示信息，等候用户输入 06 以进入相应的操作功能。
6、3 用户输入数据完毕，程序将输出运行结果。4 测试数据应为字符型数据。三、概要设计1创建二叉树输入数据不低于 15 个，用递归方法建立二叉树。2二叉树的非递归前序遍历示意图图 3.2 二叉树前序遍历示意图数据结构课程设计53二叉树的后序非递归遍历示意图图 3.4 二叉树后序遍历示意图四、数据结构设计1二叉树结点数据类型定义为：template struct BiNodeBiNode *rchild,*lchild;/指向左右孩子的指针T data; /结点数据信息;2二叉树数据类型定义为：template class BiTreetemplate friend ostream public:BiTree();/无参构造函数BiTree(int m);/有参空构造函数BiT
