二叉树的遍历课程设计(C++)含源代码

数据结构课程设计0《数据结构》课程设计报告设计题目：二叉树的遍历姓名：陈雷学号：211001047专业：计算机科学与技术院系：计算机科学与技术班级：1002指导教师：吴克力2012年3月1日数据结构课程设计1摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC++，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键字：二叉树遍历非递归C++LCA数据结构课程设计2Abstract:Thispapermainlydescribeshowtoimplementbinarytreetraversal.Thebinarytreetraversalisbasedonbinarytreebinarystoragestructure.Traversalmethodincludes:preordertraversal,inordertraversal,postordertraversal,levelordertraversal.Theformerpreordertraversalandpostorderuseofnon-recursivealgorithm.ProgrammingenvironmentisVC++,inadditiontotraversaloperation,alsoincreasedforsolvingthebinarytreedepth、summarypointsandeachlayerofnodes,aswellasthemostrecentcommonancestor(LCA)algorithm.Keywords:binarytreetraversalnon-recursiveC++LCA数据结构课程设计3目录一、问题描述...............................................................................................................4问题描述：创建二叉树并遍历...............................................................................................4基本要求：...............................................................................................................................4二、需求分析...............................................................................................................4三、概要设计...............................................................................................................41．创建二叉树.........................................................................................................................42．二叉树的非递归前序遍历示意图.....................................................................................43．二叉树的后序非递归遍历示意图.....................................................................................5四、数据结构设计.......................................................................................................51．二叉树结点数据类型定义为：...................................................................................52．二叉树数据类型定义为：...........................................................................................5五、算法设计...............................................................................................................61、创建二叉树.........................................................................................................................62、非递归前序遍历.................................................................................................................73、非递归后序遍历.................................................................................................................74、求二叉树的高度.................................................................................................................85、求二叉树每一层的结点数...........................................................................................96、求两节点最近共同祖先.....................................................................................................96、算法流程图.......................................................................................................................10六、程序测试与实现.................................................................................................111、函数之间的调用关系.......................................................................................................112、主程序...............................................................................................................................113、测试数据...........................................................................................................................134、测试结果...........................................................................................................................13七、调试分析.............................................................................................................14八、遇到的问题及解决办法.....................................................................................15九、心得体会.............................................................................................................15十、参考文献.............................................................................................................15数据结构课程设计4一、问题描述问题描述：创建二叉树并遍历基本要求：1、分别运用非递归的方式完成对二叉树的先序和后序遍历2、输出二叉树的高度3、输出每一层的结点数4、查找结点P和结点Q的最近共同祖先二、需求分析1．本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2．程序运行后显现提示信息，等候用户输入0—6以进入相应的操作功能。3．用户输入数据完毕，程序将输出运行结果。4．测试数据应为字符型数据。三、概要设计1．创建二叉树输入数据不低于15个，用递归方法建立二叉树。2．二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图数据结构课程设计53．二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图四、数据结构设计1．二叉树结点数据类型定义为：templatetypenameTstructBiNode{BiNodeT*rchild,*lchild;//指向左右孩子的指针Tdata;//结点数据信息};2．二叉树数据类型定义为：templatetypenameTclassBiTree{templatetypenameTfriendostream&operator(ostream&os,BiTreeT&bt);public:BiTree();//无参构造函数BiTree(intm){};//有参空构造函数BiTree(Tary[],intnum,Tnone);//有参构造函数~BiTree();//析构函数voidpreorder();//递归前序遍历voidinorder();//递归中序遍历voidpostorder();//递归后续遍历voidlevelorder();//层序遍历intcount();//计算二叉树的结点数intdepth();//计算二叉树的深度数据结构课程设计6voiddisplay(ostream&os);//打印二叉树，有层次voidLevelNum();//计算每一层结点数voidPreOrder();//非递归前序遍历vo