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

《数据结构课程设计--二叉树的遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、摘要针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一

2、个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效

3、方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让我们对二叉树的理解有更好的效果。关键词：二叉树的遍历；左子树；右子树；递归I目录1.问题概述31.1问题描述31.2需求分析31.3设计内容和要求31.4流程图及结构图32.概要设计32.1数据结构设计：32.2源程序代码33.调试分析33.1调试中的问题34.测试结果3总结3参考文献3181.问题概述1.1问题描述创建二叉树并遍历 基本要求： 该程序集成了如下功能：（

4、1）二叉树的建立（2）递归和非递归先序，中序和后序遍历二叉树（3）按层次遍历二叉树（4）交换二叉树的左右子树（5）输出叶子结点（6）递归和非递归计算叶子结点的数目1.2需求分析分先序遍历，中序遍历和后序遍历三种情况考虑。1.先序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：①　访问根结点；②　按先序遍历规则遍历左子树；③　按先序遍历规则遍历右子树；2.中序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：①　按中序遍历规则遍历左子树；②　访问根结点；③　按中序遍历规3遍历右子树。3.后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：

5、①　按后序遍历规则遍历左子树；②　按后序遍历规则遍历右子树；③　访问根结点。181.3设计内容和要求对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种周游，输出三种周游的结果。1.4流程图及结构图YESYESNONO开始i=0i

6、 二叉树结点数据类型定义为： template  struct BiNode { BiNode*rchild,*lchild;//指向左孩子的指针T data;//结点数据信息 }; 2． 二叉树数据类型定义为： template  class BiTree { template  friend ostream & operator <<(ostream &os ,BiTree &bt); public: BiTree();//无参构造函数 BiTree(i

7、nt m){};//有参空构造函数 BiTree(T ary[],int num,T none);//有参构造函数  18BiTree();//析构函数 void preorder();//递归前序遍历  void inorder();//递归中序遍历  void postorder();//递归后续遍历 void levelorder();//层序遍历 int  count();//计算二叉树的结点数  void display(ostream &os);//打印二叉树，有层次  void LevelNum();//计算每一层结点数  v

8、oid PreOrder();//非递归前序遍历  void PostOrder();//非递归后序遍历  void creat();//创建二叉树 protected: //以