数据结构课程设计--二叉树的遍历

I摘要针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让我们对二叉树的理解有更好的效果。关键词：二叉树的遍历；左子树；右子树；递归II目录1.问题概述....................................................................................................................31.1问题描述..........................................................................................................31.2需求分析..........................................................................................................31.3设计内容和要求..............................................................................................41.4流程图及结构图..............................................................................................42.概要设计....................................................................................................................52.1数据结构设计：..............................................................................................52.2源程序代码......................................................................................................73.调试分析..................................................................................................................133.1调试中的问题................................................................................................134.测试结果..................................................................................................................14总结..............................................................................................................................17参考文献......................................................................................................................1831.问题概述1.1问题描述创建二叉树并遍历基本要求：该程序集成了如下功能：（1）二叉树的建立（2）递归和非递归先序，中序和后序遍历二叉树（3）按层次遍历二叉树（4）交换二叉树的左右子树（5）输出叶子结点（6）递归和非递归计算叶子结点的数目1.2需求分析分先序遍历，中序遍历和后序遍历三种情况考虑。1.先序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：①访问根结点；②按先序遍历规则遍历左子树；③按先序遍历规则遍历右子树；2.中序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：①按中序遍历规则遍历左子树；②访问根结点；③按中序遍历规3遍历右子树。3.后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：①按后序遍历规则遍历左子树；②按后序遍历规则遍历右子树；③访问根结点。41.3设计内容和要求对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种周游，输出三种周游的结果。1.4流程图及结构图图1.1流程图开始i=0inbtreetypenewNodeMultiplexroot=newNodei++结束是否为空returnrootYESYESNONO5图1.2二叉链表存储结构模拟图2.概要设计2.1数据结构设计：1．二叉树结点数据类型定义为：templatetypenameTstructBiNode{BiNodeT*rchild,*lchild;//指向左孩子的指针Tdata;//结点数据信息};2．二叉树数据类型定义为：templatetypenameTclassBiTree{templatetypenameTfriendostream&operator(ostream&os,BiTreeT&bt);public:BiTree();//无参构造函数BiTree(intm){};//有参空构造函数BiTree(Tary[],intnum,Tnone);//有参构造函数bcdefa6BiTree();//析构函数voidpreorder();//递归前序遍历voidinorder();//递归中序遍历voidpostorder();//递归后续遍历voidlevelorder();//层序遍历intcount();//计算二叉树的结点数voiddisplay(ostream&os);//打印二叉树，有层次voidLevelNum();//计算每一层结点数voidPreOrder();//非递归前序遍历voidPostOrder();//非递归后序遍历voidcreat();//创建二叉树protected://以下函数供上面函数调用//对应相同功能Voidcreat(BiNodeT*&root);//创建voidrelease(BiNodeT*&root);//删除BiNodeT*Build(Tary[],intnum,Tnone,intidx);//用数组创建二叉树voidPreOrder(BiNodeT*root);//前序遍历voidPostOrder(BiNodeT*root);//后续遍历voidLevelNum(BiNodeT*root);//层序遍历voidpreorder(BiNodeT*root);//递归前序遍历voidinorder(BiNodeT*root);//递归中序遍历voidpostorder(BiNodeT*root);//递归后续遍历voidlevelorder(BiNodeT*root);//层序遍历intcount(BiNodeT*root);//计算结点数voiddisplay(ostream&os,BiNodeT*root,intdep);//打印staticboolleastCommanAncestor(BiNodeT*root,Tva,Tvb,BiNodeTprivate:BiNodeT*rootptr;};72.2源程序代码#includeiostreamusingnamespacestd;//*************************************************************************************//二叉树结点类的定义templateclassTstructBTNode{Tdata;BTNodeT*Lchild,*Rchild;BTNode(TnodeValue=T(),BTNodeT*leftNode=NULL,BTNodeT*rightNode=NULL):data(nodeValue),Lchild(leftNode),Rchild(rightNode){}//可选择参数的默认构造函数};//**************************************************************************************//二叉树的建立templateclassTvoidcreateBinTree(BTNodeT*&root){BTNodeT*p=root;BTNodeT*k;TnodeValue;cinnodeValue;if(nodeValue==-1){root=NULL;8}else{root=newBTNodeT();root-data=nodeValue;createBinTree(root-Lchild);createBinTree(root-Rchild);}}//************************************************************************************//二叉树的先序遍历templateclassTvoidpreOrder(BTNodeT*&p){if(p){coutp-data;preOrder(p-Lchild);preOrder(p-Rchild);}}//**************************************************************************************//二叉树的中序遍历templateclassTvoidinOrder(BTNodeT*&p){if(p){9inOrder(p-Lchild);coutp-data;inOrder(p-Rchild);}}//*******************************