实用文库汇编之数据结构课程设计二叉树的遍历

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

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

3、，是与给出用于计算各种类型中不同树的数日的公式有关的。本文对二义树以及二叉树的各种功能做介绍以及写出一些基本的程序，让 我们对二义树的理解有更好的效果。关键词：二义树的遍历；左子树：右子树：递归目录1 问题概述31.1问题描述31.2需求分析31.3设计内容和要求41.4流程图及结构图42. 概要设计42. 1数据结构设计：42. 2源程序代码63. 调试分析123. 1调试中的问题124. 测试结果13总结16参考文献171 问题概述1.1问题描述创建二义树并遍历基本要求：该程序集成了如下功能：（1）二叉树的建立（2）递归和非递归先序，中序和后序遍历二义树（3）按层次遍历二义树（4）交换二义

4、树的左右子树（5）输出叶子结点（6）递归和非递归计算叶子结点的数LI1.2需求分析分先序遍历，中序遍历和后序遍历三种情况考虑。1. 先序遍历，当二义树非空时按以下顺序遍历，否则结束操作: 访问根结点； 按先序遍历规则遍历左子树； 按先序遍历规则遍历右子树；2. 中序遍历，当二义树非空时按以下顺序遍历，否则结束操作: 按中序遍历规则遍历左子树； 访问根结点； 按中序遍历规3遍历右子树。3. 后序遍历，当二义树非空时按以下顺序遍历，否则结束操作: 按后序遍历规则遍历左子树； 按后序遍历规则遍历右子树； 访问根结点。仁3设计内容和要求对任意给定的二义树（顶点数自定）建立它的二义链表存贮结构，并利用

5、栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二义 树的先序、中序、后序三种周游，输出三种周游的结果。1 4流程图及结构图1.1流程图NOYES图1.2二叉链表存储结构模拟图NO2. 概要设计YES2. 1数据结构设计：1. 二义树结点数据类型定义为：template <typename T> struct BiNodeBiNode<T>*rchild, *lchild;/指向左孩子的指针T data;/结点数据信息;2. 二义树数据类型定义为：template <typename T> class BiTree template <

6、typename T>friend ostream & operator «(ostream &os ,BiTree<T> &bt): pub lie:BiTree ();/无参构造函数BiTree(int m) ;/有参空构造函数BiTree (T ary, int num, T none) ; /有参构造函数BiTree (); 析构函数void preorder () ;/递归前序遍历void inorder() ;/递归中序遍历void postorder () ;/递归后续遍历void levelorder () ;/层序遍历int

7、count () ;/计算二义树的结点数void display(ostream &os) :/打印二义树，有层次void LevelNumO ;/计算每一层结点数void PreOrder () ;/非递归前疗;遍历void PostOrder () ;/非递归后序遍历void creat () ;/创建_.义树protected： 以下函数供上面函数调用/对应相同功能Voider eat (BiNode<T>*&root) ;/创建void release(BiNode<T>* &root) ;/删除BiNode<T> * Bui

8、 Id (T ary, int num, T none, int idx): 用数 组创建 二叉树void PreOrder(BiNode<T>* root) ;/前序遍历 void PostOrder (BiNode<T>* root) ;/后续遍历 void LevelNum(BiNode<T>* root) ;/层序遍历 void preorder (BiNode<T>* root) ;/递归前序遍历 void inorder (BiNode<T>* root) ;/递归中序遍历 void postorder (BiNode&l

9、t;T>* root) ;/递归后续遍历 void levelorder (BiNode<T>*root) ;/层序遍历 int count (BiNode<T>* root) ;/计算结点数 void display (ostreamA os, BiNode<T>* root, int dep) ;/扌印 static bool leastCommanAncestor(BiNode<T> *root, T va, T vb,BiNode<T> private:BiNode<T> *rootptr;2. 2源程序代码

10、#include <iostream> using namespace std;二义树结点类的定义template<class T>struct BTNodeT data;BTNode <T> * Lchild,*Rchild;BTNode(T node Value = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL):data(nodeValue),Lchild(leftNode),Rchild(rightNode)可选择参数的默认构造函数二义树的建立templa

11、te <class T>void createBinTree(BTNode<T> * &root) BTNode<T>* p = root;BTNode<T>* k;T node Value ;cin»node Value;if(nodeValue=-1)root=NULL;elseroot=new BTNode<T>(); root->data = node Value;createBinTree(root->Lchild); createBinTree(root->Rchild);)二义树的先序

12、遍历template <class T>void preOrder( BTNode<T> * & p) if(P)cou t «p - >d at a« *1 H; preOrder(p->Lxhild); preOrder(p->Rchild);)二义树的中序遍历template <class T>void inOrder(BTNode<T> * & p)if(P)inOrder(p->Lchild); cout«p->data«H H;inOrder(p-&

13、gt;Rchild);)二义树的后序遍历template <class T>void levelOrder(BTNode<T> 水& p) if(P)levelOrder(p->Lchild); levelOrder(p->Rchild); cout«p->data«M *'15C5C5C5C5C5C统计二义树中结点的个数template<class T>int countNode(BTNode<T> 水 & p)if(p = NULL) return 0;return 1 +coun

14、tNode(p->Lchild)+countNode(p->Rchild);)5C求二义树的深度template<class T>int depth(BTNode<T> *& p) if(p = NULL)return 1;int hl = depth(p->Lchild); int h2 = depth(p->Rchild); if(h l>h2)return (h 1 + 1);return h2+l;二义树的消毁操作template<class T>消毁函数,BTNode<T>* destroy(BTN

15、ode<T>* p)用来消毁二叉树中的各个结点if(P)return destroy(p->Lchild);return destroy(p->Rchild);delete p;)5C5C5C5C5C5C5C* 5C* * 木 * 木 * 主函数的设计int main ()BTNode<int> * rootNode = NULL; int choiced = 0;while(tnje)system(HclsH);cout«Hnnncout«H主界面nnnH;1、创建二义树2、先序遍历二叉树n”；cout«H3、中序遍历二叉树4

16、、后序遍历二义树n”；cout«H5、统讣结点总数6、查看树探Jxn”；cout«H7、消毁二叉树0、退出 nn”；cout«H请选择操作："；cin»choiced;if(choiced = 0)return 0;else if(choiced = 1)system(HclsH);cout«"请输入每个结点，回车确认，并以-1结束：n”; createBinTree(rootNode );else if(choiced = 2)system(HclsH);cout«"先序遍历二义树结果：n“；preOr

17、der(rootNode);cout«endl;system(npauseH);else if(choiced = 3)system(HclsH);cout«"中序遍历二义树结果：n”；inOrder(rootNode);cout«endl;system(npausen);else if(choiced = 4)system(HclsH);cout«"后序遍历二义树结果：n”；levelOrder(rootNode);cout«endl;system(npausen);else if(choiced = 5)system(H

18、clsH);int count = countNode(rootNode);cout«"义树中结点总数为"«count«endl; system(npauseH);else if(choiced = 6)system(HclsH);int dep = depth(rootNode);cout«"此二叉树的深度为"«dep«endl;system(MpauseH);else if(choiced = 7)system(HclsH);coutvv“二义树已被消毁！ n”；destroy(rootNo

19、de);cout«endl; system(MpauseH);elsesystem("cls");cout«"nnnnnt 错误选择！ n"3. 调试分析3.1调试中的问题创建二义树：依次输入二义树前序遍历序列，构建相应的二义树。二义树遍历：递归算法、非递归算法测试，调用相应函数进行测试，结果正 确。 求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正 确。计算每层结点数：调用1 evelNum()函数，测试结果正确。调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时， 容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各 个难题。4. 测试结果(1)初始界面:主界面所包含的内容cR CsXDociments and SettingsAdninistratorJffi软件Debugwangyuexe°X