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

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

2、，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。本

3、文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让我们对二叉树的理解有更好的效果。关键词：二叉树的遍历；左子树；右子树；递归目录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）递归和非递归计算叶子

4、结点的数目1.2需求分析分先序遍历，中序遍历和后序遍历三种情况考虑。1. 先序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：1 访问根结点；2 按先序遍历规则遍历左子树；3 按先序遍历规则遍历右子树；2. 中序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：1 按中序遍历规则遍历左子树；2 访问根结点；3 按中序遍历规3遍历右子树。3. 后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作：1 按后序遍历规则遍历左子树；2 按后序遍历规则遍历右子树；3 访问根结点。1.3设计内容和要求对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（清空堆栈、压栈、弹出、

5、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种周游，输出三种周游的结果。1.4流程图及结构图YESYESNONO开始i=0i<nbtreetypenewNodeMultiplexroot=newNodei+结束是否为空returnroot图1.1 流程图 b c d e f a图1.2二叉链表存储结构模拟图2.概要设计2.1数据结构设计：1 二叉树结点数据类型定义为： template <typename T> struct BiNode  BiNode<T>*rchild,*l

6、child;/指向左孩子的指针T data;/结点数据信息  2 二叉树数据类型定义为： template <typename T> class BiTree  template <typename T> friend ostream & operator <<(ostream &os ,BiTree<T> &bt)

7、; public: BiTree();/无参构造函数 BiTree(int m);/有参空构造函数 BiTree(T ary,int num,T none);/有参构造函数  BiTree();/析构函数 void preorder();/递归前序遍历  void inorder();/递归中序遍历  void postorder();/递归后续遍历 void levelorder();/层序遍历

8、 int  count();/计算二叉树的结点数  void display(ostream &os);/打印二叉树，有层次  void LevelNum();/计算每一层结点数  void PreOrder();/非递归前序遍历  void PostOrder();/非递归后序遍历  void creat();/创建二叉树 protected: /以下函数供上面函数调用

9、0; /对应相同功能 Voidcreat(BiNode<T>*&root);/创建  void release(BiNode<T>* &root);/删除 BiNode<T> * Build(T ary,int num,T none,int idx);/用数组创建二叉树  void PreOrder(BiNode<T>* root);/前序遍历 

10、0;void PostOrder(BiNode<T>* root);/后续遍历  void LevelNum(BiNode<T>* root);/层序遍历  void preorder(BiNode<T>* root);/递归前序遍历  void inorder(BiNode<T>* root);/递归中序遍历  void postorder(BiNode<T>*&#

11、160;root);/递归后续遍历  void levelorder(BiNode<T>*root);/层序遍历  int count(BiNode<T>* root);/计算结点数   void display(ostream& os,BiNode<T>* root,int dep);/打印 static bool leastCommanAncestor(BiNode<T&g

12、t; *root, T va, T vb, BiNode<T>                       private:BiNode<T> *rootptr; 2.2源程序代码#include <iostream>using namespace st

13、d;/*/二叉树结点类的定义template<class T>struct BTNodeT data; BTNode <T> * Lchild,*Rchild; BTNode(T nodeValue = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL ) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) /可选择参数的默认构造函数;/*/二叉树的建立template <class T>void createBin

14、Tree(BTNode<T> * &root ) BTNode<T>* p = root; BTNode<T>* k; T nodeValue ; cin>>nodeValue; if(nodeValue=-1) root=NULL; else root=new BTNode<T>(); root->data = nodeValue; createBinTree(root->Lchild); createBinTree(root->Rchild); /*/二叉树的先序遍历template <class

15、T>void preOrder( BTNode<T> * & p) if(p) cout<<p->data<<" " preOrder(p->Lchild); preOrder(p->Rchild); /*/二叉树的中序遍历template <class T>void inOrder(BTNode<T> * & p) if(p) inOrder(p->Lchild); cout<<p->data<<" " inOrder

16、(p->Rchild); /*/二叉树的后序遍历template <class T>void levelOrder(BTNode<T> *& p) if(p) levelOrder(p->Lchild); levelOrder(p->Rchild); cout<<p->data<<" " /*/统计二叉树中结点的个数template<class T>int countNode(BTNode<T> * & p) if(p = NULL) return 0; retu

17、rn 1+countNode(p->Lchild)+countNode(p->Rchild);/*/求二叉树的深度template<class T>int depth(BTNode<T> *& p) if(p = NULL) return -1; int h1 = depth(p->Lchild); int h2 = depth(p->Rchild); if(h1>h2)return (h1+1); return h2+1;/*/二叉树的消毁操作template<class T>BTNode<T>* dest

18、roy(BTNode<T>* p) /消毁函数，用来消毁二叉树中的各个结点 if(p) return destroy(p->Lchild); return destroy(p->Rchild); delete p; /*/主函数的设计 int main () BTNode<int> * rootNode = NULL; int choiced = 0; while(true) system("cls"); cout<<"nnn -主界面-nnn" cout<<" 1、创建二叉树 2、先

19、序遍历二叉树n" cout<<" 3、中序遍历二叉树 4、后序遍历二叉树n" cout<<" 5、统计结点总数 6、查看树深度 n" cout<<" 7、消毁二叉树 0、退出nn" cout<<" 请选择操作：" cin>>choiced; if(choiced = 0) return 0; else if(choiced = 1) system("cls"); cout<<"请输入每个结点，回车确认，并

20、以-1结束：n" createBinTree(rootNode ); else if(choiced = 2) system("cls"); cout<<"先序遍历二叉树结果：n" preOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 3) system("cls"); cout<<"中序遍历二叉树结果：n" inOrder(rootNode); cout<<

21、endl; system("pause"); else if(choiced = 4) system("cls"); cout<<"后序遍历二叉树结果：n" levelOrder(rootNode); cout<<endl; system("pause"); else if(choiced = 5) system("cls"); int count = countNode(rootNode); cout<<"二叉树中结点总数为"<&l

22、t;count<<endl; system("pause"); else if(choiced = 6) system("cls"); int dep = depth(rootNode); cout<<"此二叉树的深度为"<<dep<<endl; system("pause"); else if(choiced = 7) system("cls"); cout<<"二叉树已被消毁！n" destroy(rootNode); cout<<endl; system("pause"); else system("cls"); cout<<"nnnnnt错误选择！n" 3.调试分析3.1调试中的问题创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。 二叉树遍历：递归算法、非递归算法测试，调用相应函数