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

摘要针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机 构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次 特性的对象如操作系统的文件构成、人工智能和算法分析的模型表示以及数据 库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借 助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题 为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应 用。在树型结构的应用中又以二叉树最为常用。二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其 中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常 广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的 顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树， 然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。 由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几 个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的 方法，比如在查找问题上，任何借助于比较法查找长度为W的一个序表的算法， 都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法 根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算 各种类型中不同树的数目的公式有关的。本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让我 们对二叉树的理解有更好的效果。关键词：二叉树的遍历；左子树；右子树；递归目录1. 问题概述31.1 问题描述31.2 需求分析 31.3 设计内容和要求41.4 流程图及结构图42. 概要设计52.1 数据结构设计：52.2 源程序代码73. 调试分析133.1 调试中的问题134. 测试结果 14总结17参考文献181. 问题概述1.1 问题描述创建二叉树并遍历 基本要求： 该程序集成了如下功能：（1）二叉树的建立（2）递归和非递归先序，中序和后序遍历二叉树（3）按层次遍历二叉树（4）交换二叉树的左右子树（5）输出叶子结点（6）递归和非递归计算叶子结点的数目1.2需求分析分先序遍历，中序遍历和后序遍历三种情况考虑。1. 先序遍历，当二叉树非空时按以下顺序遍历，否则结束操作 访问根结点； 按先序遍历规则遍历左子树； 按先序遍历规则遍历右子树；2. 中序遍历，当二叉树非空时按以下顺序遍历，否则结束操作 按中序遍历规则遍历左子树； 访问根结点； 按中序遍历规 3 遍历右子树。3. 后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作 按后序遍历规则遍历左子树； 按后序遍历规则遍历右子树； 访问根结点。1.3 设计内容和要求对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈 的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树的 先序、中序、后序三种周游，输出三种周游的结果。1.4 流程图及结构图开始结束图 1.1 流程图人def图 1.2 二叉链表存储结构模拟图2. 概要设计2.1数据结构设计：1 二叉树结点数据类型定义为：template <typename T> struct BiNodeBiNode<T>*rchild, *lchild;/指向左孩子的指针T data;/结点数据信息;2 二叉树数据类型定义为：template <typename T> class BiTree template <typename T>pubfriend ostream & operator <<(ostream &os ,BiTree<T> &bt); lic:BiTreeO;/无参构造函数BiTree(int m);/有参空构造函数BiTree(T ary ,in t num,T none);/有参构造函数BiTreeO;/析构函数void preorder();/递归前序遍历void inorder();/递归中序遍历void pos torder();/递归后续遍历void levelorder();/层序遍历intcoun t();/计算二叉树的结点数void display(os tream & os);/打印二叉树，有层次void LevelNum();/计算每一层结点数void PreOrder();/非递归前序遍历void Pos tOrder();/非递归后序遍历void crea t();/创建二叉树protected: /以下函数供上面函数调用 /对应相同功能Voidcrea t(BiNode<T> *&roo t);/创建 void release(BiNode<T>* &roo t);/删除BiNode<T> * Build(T ary,int num,T none,int idx);/用数组创建 二叉树 void PreOrder(BiNode<T> * roo t);/前序遍历 void Pos tOrder(BiNode<T>* roo t);/后续遍历 void LevelNum(BiNode<T> * roo t);/层序遍历 void preorder(BiNode<T >* roo t);/递归前序遍历 void inorder(BiNode<T>* roo t);/递归中序遍历 void pos torder(BiNode<T>* roo t);/递归后续遍历 void levelorder(BiNode<T> *roo t);/层序遍历 int coun t(BiNode<T >* roo t);/计算结点数 void display(os tream& os,BiNode<T >* root,int dep);/打印 static bool leastCommanAncestor(BiNode<T> *root, T va, T vb,BiNode<T> private:BiNode<T> *rootptr;2.2 源程序代码#include <iostream> using namespace std;/ / / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/二叉树结点类的定义 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) /可选择参 数的默认构造函数;/ / / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/二叉树的建立template <class T>void createBinTree(BTNode<T> * &root ) BTNode<T>* p = root;BTNode<T>* k;T nodeValue ;cin>>nodeValue;if(nodeValue=-1)root=NULL; elseroot=new BTNode<T>(); root->data = nodeValue; createBinTree(root->Lchild); createBinTree(root->Rchild);/ / / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/二叉树的先序遍历 template <class T> void preOrder( BTNode<T> * & p) if(p)cout<<p->data<<" " preOrder(p->Lchild); preOrder(p->Rchild);/ /V/ / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* V#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/二叉树的中序遍历 template <class T> void inOrder(BTNode<T> * & p) if(p) inOrder(p->Lchild); cout<<p->data<<" " inOrder(p->Rchild);/ / / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* T#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/二叉树的后序遍历 template <class T> void levelOrder(BTNode<T> *& p) if(p)levelOrder(p->Lchild); levelOrder(p->Rchild); cout<<p->data<<" "/ / / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #Jx #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/统计二叉树中结点的个数 template<class T> int countNode(BTNode<T> * & p) if(p = NULL) return 0;return 1+countNode(p->Lchild)+countNode(p->Rchild); / / 、/ / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* r#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/求二叉树的深度 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;/ / / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*#J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/二叉树的消毁操作template<class T>/消毁函数，用BTNode<T>* destroy(BTNode<T>* p)来消毁二叉树中的各个结点if(p)return destroy(p->Lchild);return destroy(p->Rchild);delete p;/ / / #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J* #J*/主函数的设计 int main ()BTNode<int> * rootNode = NULL; int choiced = 0;while(true)system("cls");coutvv"nnn-主界面-nnn"coutvv"1、创建二叉树2、先序遍历二叉树n"coutvv"3、中序遍历二叉树4、后序遍历二叉树n"coutvv"5、统计结点总数6、查看树深度n"coutvv"7、消毁二叉树0、退出 nn"coutvv"请选择操作： "cin>>choiced;if(choiced = 0)return 0;else if(choiced = 1) system("cls");coutvv"请输入每个结点，回车确认，并以-1结束：n"createBinTree(rootNode );else if(choiced = 2) system("cls");coutvv"先序遍历二叉树结果:n" preOrder(rootNode);coutvvendl;system("pause");else if(choiced = 3) system("cls");coutvv"中序遍历二叉树结果:n"inOrder(rootNode);coutvvendl;system("pause");else if(choiced = 4) system("cls");coutvv"后序遍历二叉树结果：n"levelOrder(rootNode);cout<<endl;system("pause");else if(choiced = 5) system("cls");int count = countNode(rootNode); coutvv"二叉树中结点总数为"vvcountvvendl; system("pause");else if(choiced = 6)system("cls");int dep = depth(rootNode);coutvv"此二叉树的深度为"vvdepvvendl; system("pause");else if(choiced = 7)system("cls"); coutvv"二叉树已被消毁！ n" destroy(rootNode);coutvvendl; system("pause"); elsesystem("cls");coutvv"nnnnnt 错误选择！ n"3. 调试分析3.1 调试中的问题创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。二叉树遍历：递归算法、非递归算法测试，调用相应函数进行测试，结果正 确。求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正确。计 算每层结点数：调用levelNum()函数，测试结果正确。调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时， 容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各 个难题。4. 测试结果(1)初始界面:主界面所包含的内容吠"C: PociiBents and Sett ings 1 Ad>inist rat oi面'机爲软件Debugwangyu. eie"主界面树x'ft科二恙科二遍结二创口统消* % * *13 5?2.先庄遍历二莎4.后序遍厅二厌树 氐查議探度0.退出请选舉乜1图4.1初始界面图(2)运行结果：进行操作1,输入每个结点，显示结果如下图4.2创建二叉树进行操作2,执行结果如下:点 fC:I)ocueiits and ScttinEsUdiiidstratorffi00J)ebuTangyu. eie* X进行操作3,执行结果如下:图4.4二叉树中序遍历进行操作4,执行结果如下:图4.5二叉树后序遍历:进行操作5,执行结果如下：图4.6统计二叉树节点进行操作6,执行结果如下:肚 C:Docu>ents and SeitincsVAdunistraqi臬面l机软件'Debu叭an首yu&工亡"16要能很好的掌握编程,仅仅通过几个简单的程序的编写时无法达成的 ,更需 要大量积累和深入才可能通过本次课程设计。有关一个课题的所有知识不仅仅是 在课本上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能 力。本次课程设计还让我认识到自己的缺点。本次选的课题是二叉树的遍历，因 为本学期所学的就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简 单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。经 过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我 的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据 结构更加了解。2009年9月参考文献1 严蔚敏 吴伟民数据结构（c语言版）清华大学出版社，2 谭浩强C程序设计（第三版）清华大学出版社2009年1月