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

《二叉树的遍历课程设计(C++)含源代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.南京理工大学课程设计报告作者:相蒙蒙学号：054913221001教学点:市职业大学专业:机电一体化题目:二叉树的遍历指导者：尚鲜莲评阅者：2014年4月..南京理工大学课程设计报告评语综合成绩：指导者评语：指导者(签字)：年月日..课程设计报告摘要摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC++，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA

2、）问题的算法。关键词：二叉树遍历二叉树遍历..目录1问题描述.....................................51.1问题描述：创建二叉树并遍历.......................52、需求分析.................................53、概要设计................................53.1．创建二叉树.............................53.2二叉树的非递归前序遍历示意图...........................

3、...53.3二叉树的后序非递归遍历示意图.....................64、数据结构设计..........................64.1二叉树结点数据类型定义...................64.2二叉树数据类型定义......................75、算法设计.........................85.1创建二叉树.....................85.2非递归前序遍历...................85.3非递归后序遍历.....................

4、95.4求二叉树的高度........................105.5求二叉树每一层的结点数...................105.6求两节点最近共同祖先......................115.7算法流程图.................................126、程序测试与调试............................126.1函数之间的调用关系.........................126.2主程序..................................

5、...136.3测试数据..................................146.4测试结果...............................147、调试分析.............................178、遇到的问题及解决办法..........................179、心得体会..............................1710、参考文献.............................18..1、问题描述1.1问题描述：创建二叉树并遍历基本要求：

6、1、分别运用非递归的方式完成对二叉树的先序和后序遍历2、输出二叉树的高度3、输出每一层的结点数4、查找结点P和结点Q的最近共同祖先2、需求分析1、本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2、程序运行后显现提示信息，等候用户输入0—6以进入相应的操作功能。3、用户输入数据完毕，程序将输出运行结果。4、测试数据应为字符型数据。3、概要设计3．1创建二叉树输入数据不低于15个，用递归方法建立二叉树。3.2二叉树的非递归前序遍历示意图..

7、图3.2二叉树前序遍历示意图3.3二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图4、数据结构设计4.1二叉树结点数据类型定义为：templatestructBiNode..{BiNode*rchild,*lchild;//指向左右孩子的指针Tdata;//结点数据信息};4.2二叉树数据类型定义为：templateclassBiTree{templatefriendostream&operator<<(ostream&os,BiTree&bt);p

8、ublic:BiTree();//无参构造函数BiTree(intm){};//有参空构造函数BiTree(Tary[],intnum,Tnone);//有参构造函数~BiTree();//析构函数voidpreorde