数据结构优秀课程设计二叉树的遍历.docx

摘要针对现实世界中很多关系复杂数据，如人类社会家谱，多种社会组织机构,博弈交通等复杂事物或过程和客观世界中广泛存在含有分支关系或层次特征对象如操作系统文件组成、人工智能和算法分析模型表示和数据库系统信息组织形式等，用线性结构难以把其中逻辑关系表示出来，必需借助于数和图这么非线性结构，所以在以模拟客观世界问题，处理客观世界问题为关键任务计算机领域中树型结构是信息一个关键组织形式，树有着广泛应用。在树型结构应用中又以二叉树最为常见。二叉树是一个很关键非线性结构，所描述数据有显著层次关系，其中每个元素只有一个前驱，二叉树是最为常见数据结构，它实际应用很广泛，二叉树遍历方法有三种，前序遍历，中序遍历，后序遍历，先序遍历次序为：NLR先根结点，然后左子树，右子树；中序遍历次序为；LNR先左子树，然后根结点，右子树；后序遍历次序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列能够唯一确定一棵二叉树。对于给多个数据排序或在已知多个数据中进行查找，二叉树均能提供一个十分有效方法，比如在查找问题上，任何借助于比较法查找长度为一个序表算法，全部能够表示成一株二叉树。反之，任何二叉树全部对应一个查找有序表有效方法依据树数学理论，对于算法分析一些最有启发性应用，是和给出用于计算多种类型中不一样树数目标公式相关。本文对二叉树和二叉树多种功效做介绍和写出部分基础程序，让我们对二叉树了解有愈加好效果。关键词：二叉树遍历；左子树；右子树；递归目录1.问题概述31.1问题描述31.2需求分析31.3设计内容和要求31.4步骤图及结构图32.概要设计32.1数据结构设计：32.2源程序代码33.调试分析33.1调试中问题34.测试结果3总结3参考文件31.问题概述1.1问题描述创建二叉树并遍历基础要求：该程序集成了以下功效：（1）二叉树建立（2）递归和非递归先序，中序和后序遍历二叉树（3）按层次遍历二叉树（4）交换二叉树左右子树（5）输出叶子结点（6）递归和非递归计算叶子结点数目1.2需求分析分先序遍历，中序遍历和后序遍历三种情况考虑。1. 先序遍历，当二叉树非空时按以下次序遍历，不然结束操作： 访问根结点； 按先序遍历规则遍历左子树； 按先序遍历规则遍历右子树；2. 中序遍历，当二叉树非空时按以下次序遍历，不然结束操作： 按中序遍历规则遍历左子树； 访问根结点； 按中序遍历规3遍历右子树。3. 后序遍历，当二叉树非空时按以下次序遍历，不然结束操作： 按后序遍历规则遍历左子树； 按后序遍历规则遍历右子树； 访问根结点。1.3设计内容和要求对任意给定二叉树（顶点数自定）建立它二叉链表存贮结构，并利用栈五种基础运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树先序、中序、后序三种周游，输出三种周游结果。1.4步骤图及结构图YESYESNONO开始i=0inbtreetypenewNodeMultiplexroot=newNodei+结束是否为空returnroot图1.1 步骤图 b c d e f a图1.2二叉链表存放结构模拟图2.概要设计2.1数据结构设计：1二叉树结点数据类型定义为：templatestructBiNodeBiNode*rchild,*lchild;/指向左孩子指针Tdata;/结点数据信息;2二叉树数据类型定义为：templateclassBiTreetemplatefriendostream&operator(ostream&os,BiTree&bt);public:BiTree();/无参结构函数BiTree(intm);/有参空结构函数BiTree(Tary,intnum,Tnone);/有参结构函数BiTree();/析构函数voidpreorder();/递归前序遍历voidinorder();/递归中序遍历voidpostorder();/递归后续遍历voidlevelorder();/层序遍历intcount();/计算二叉树结点数voiddisplay(ostream&os);/打印二叉树，有层次voidLevelNum();/计算每一层结点数voidPreOrder();/非递归前序遍历voidPostOrder();/非递归后序遍历voidcreat();/创建二叉树protected:/以下函数供上面函数调用/对应相同功效Voidcreat(BiNode*&root);/创建voidrelease(BiNode*&root);/删除BiNode*Build(Tary,intnum,Tnone,intidx);/用数组创建二叉树voidPreOrder(BiNode*root);/前序遍历voidPostOrder(BiNode*root);/后续遍历voidLevelNum(BiNode*root);/层序遍历voidpreorder(BiNode*root);/递归前序遍历voidinorder(BiNode*root);/递归中序遍历voidpostorder(BiNode*root);/递归后续遍历voidlevelorder(BiNode*root);/层序遍历intcount(BiNode*root);/计算结点数voiddisplay(ostream&os,BiNode*root,intdep);/打印staticboolleastCommanAncestor(BiNode*root,Tva,Tvb,BiNodeprivate:BiNode*rootptr;2.2源程序代码#include using namespace std;/*/二叉树结点类定义templatestruct BTNodeT data; BTNode * Lchild,*Rchild; BTNode(T nodeValue = T(),BTNode* leftNode = NULL,BTNode* rightNode = NULL ) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) /可选择参数默认结构函数;/*/二叉树建立template void createBinTree(BTNode * &root ) BTNode* p = root; BTNode* k; T nodeValue ; cinnodeValue; if(nodeValue=-1) root=NULL; else root=new BTNode(); root-data = nodeValue; createBinTree(root-Lchild); createBinTree(root-Rchild); /*/二叉树先序遍历template void preOrder( BTNode * & p) if(p) coutdataLchild); preOrder(p-Rchild); /*/二叉树中序遍历template void inOrder(BTNode * & p) if(p) inOrder(p-Lchild); coutdataRchild); /*/二叉树后序遍历template void levelOrder(BTNode *& p) if(p) levelOrder(p-Lchild); levelOrder(p-Rchild); coutdata ; /*/统计二叉树中结点个数templateint countNode(BTNode * & p) if(p = NULL) return 0; return 1+countNode(p-Lchild)+countNode(p-Rchild);/*/求二叉树深度templateint depth(BTNode *& p) if(p = NULL) return -1; int h1 = depth(p-Lchild); int h2 = depth(p-Rchild); if(h1h2)return (h1+1); return h2+1;/*/二叉树消毁操作templateBTNode* destroy(BTNode* p) /消毁函数，用来消毁二叉树中各个结点 if(p) return destroy(p-Lchild); return destroy(p-Rchild); delete p; /*/主函数设计 int main () BTNode * rootNode = NULL; int choiced = 0; while(true) system(cls); coutnnn -主界面-nnn; cout 1、创建二叉树 2、先序遍历二叉树n; cout 3、中序遍历二叉树 4、后序遍历二叉树n; cout 5、统计结点总数 6、查看树深度 n; cout 7、消毁二叉树 0、退出nn; coutchoiced; if(choiced = 0) return 0; else if(choiced = 1) system(cls); cout请输入每个结点，回车确定，并以-1结束：n; createBinTree(rootNode ); else if(choiced = 2) system(cls); cout先序遍历二叉树结果：n; preOrder(rootNode); coutendl; system(pause); else if(choiced = 3) system(cls); cout中序遍历二叉树结果：n; inOrder(rootNode); coutendl; system(pause); else if(choiced = 4) system(cls); cout后序遍历二叉树结果：n; levelOrder(rootNode); coutendl; system(pause); else if(choiced = 5) system(cls); int count = countNode(rootNode); cout二叉树中结点总数为countendl; system(pause); else if(choiced = 6) system(cls); int dep = depth(rootNode); cout此二叉树深度为dependl; system(pause); else if(choiced = 7) system(cls); cout二叉树已被消毁！n; destroy(rootNode); coutendl; system(pause); else system(cls); coutnnnnnt错误选择！n; 3.调试分析3.1调试中问题创建二叉树：依次输入二叉树前序遍历序列，构建对应二叉树。二叉树遍历：递归算法、非递归算法测试，调用对应函数进行测试，结果正确。求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正确。计算每层结点数：调用levelNum()函数，测试结果正确。调试时碰到很多问题，其中最关键问题是死循环问题，在非递归遍历时，轻易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利处理各个难题。4.测试结果（1）初始界面:主界面所包含内容图4.1初始界面图（2）运行结果：进行操作1，输入每个结点，显示结果以下图4.2创建二叉树进行操作2，实施结果以下：图4.3二叉树先序遍历进行操作3，实施结果以下：图4.4二叉树中序遍历进行操作4，实施结果以下：图4.5二叉树后序遍历:进行操作5，实施结果以下：图4.6统计二叉树节点进行操作6，实施结果以下：图4.7查看树深度总结要能很好掌握编程,仅仅经过多个简单程序编写时无法达成,更需要大量积累和深入才可能经过此次课程设计。相关一个课题全部知识不仅仅是在书本上，多查阅部分资料能够愈加好完成课题，这就需要一个能力，即自学能力。此次课程设计还让我认识到自己缺点。此次选课题是二叉树遍历，因为本学期所学就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简单，但到以后就出现部分难以处理问题，就像老师请教，并查阅相关资料。经过慢慢调试，最终测试成功。这次课程设计让我所学到数据结构知识发挥淋漓尽致，而且还拓展了我知识面，使我愈加熟练掌握多种方法。总而言之，这次课程设计增强了我自学能力，拓展了我知识面，让我对数据结构愈加了解。参考文件1 严蔚敏 吴伟民 数据结构(C语言版)清华大学出版社， 9月2 谭浩强C程序设计(第三版)清华大学出版社 1月