文档详情

二叉树的遍历课程设计.doc

发布:2017-10-29约8.92千字共16页下载文档
文本预览下载声明
《数据结构》课程设计报告 设计题目: 二叉树的遍历 姓 名: 陈 雷 学 号: 211001047 专 业: 计算机科学与技术 院 系: 计算机科学与技术 班 级: 1002 指导教师: 吴克力 2012年 3 月 1日 摘要:本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括:前序遍历,中序遍历,后续遍历,层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC++,除了遍历操作外,还增加了求二叉树的深度,总结点数,每层结点数,以及最近共同祖先(LCA)问题的算法。 关键字:二叉树 遍历 非递归 C++ LCA Abstract: 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 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 traversal non-recursive C++ LCA 目 录 一、问题描述 4 问题描述:创建二叉树并遍历 4 基本要求: 4 二、需求分析 4 三、概要设计 4 1.创建二叉树 4 2.二叉树的非递归前序遍历示意图 4 3.二叉树的后序非递归遍历示意图 5 四、数据结构设计 5 1. 二叉树结点数据类型定义为: 5 2. 二叉树数据类型定义为: 5 五、算法设计 6 1、创建二叉树 6 2、非递归前序遍历 7 3、非递归后序遍历 7 4、求二叉树的高度 8 5、 求二叉树每一层的结点数 9 6、求两节点最近共同祖先 9 6、算法流程图 10 六、程序测试与实现 11 1、函数之间的调用关系 11 2、主程序 11 3、测试数据 13 4、测试结果 13 七、调试分析 14 八、遇到的问题及解决办法 15 九、心得体会 15 十、参考文献 15 一、问题描述 问题描述:创建二叉树并遍历 基本要求: 分别运用非递归的方式完成对二叉树的先序和后序遍历 输出二叉树的高度 输出每一层的结点数 查找结点P 和结点Q的最近共同祖先 二、需求分析 本程序的功能包括二叉树的建立,二叉树的递归遍历,二叉树的非递归遍历,查询二叉树的深度,查询每层的结点数,查找两个结点的最近共同祖先,二叉树的打印。 程序运行后显现提示信息,等候用户输入0—6以进入相应的操作功能。 用户输入数据完毕,程序将输出运行结果。 测试数据应为字符型数据。 三、概要设计 1.创建二叉树 输入数据不低于15个,用递归方法建立二叉树。 2.二叉树的非递归前序遍历示意图 图3.2二叉树前序遍历示意图 3.二叉树的后序非递归遍历示意图 图3.4二叉树后序遍历示意图 四、数据结构设计 二叉树结点数据类型定义为: template typename T struct BiNode { BiNodeT *rchild,*lchild;//指向左右孩子的指针 T data; //结点数据信息 }; 二叉树数据类型定义为: template typename T class BiTree { template typename T friend ostream operator (ostream os ,BiTreeT bt); public: BiTree();//无参构造函数 BiTree(int m){};//有参空
显示全部
相似文档