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

摘要针对现实世界中许多关系复杂的数据， 如人类社会的家谱， 各种社会组织机构 , 博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象 如操作系统的文件构成、 人工智能和算法分析的模型表示以及数据库系统的信息组织形式等， 用线性结构难以把其中的逻辑关系表达出来， 必须借助于数和图这样的非线性结构， 因此在以模拟客观世界问题， 解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式， 树有着广泛应用。在树型结构的应用中又以二叉树最为常用。二叉树是一种非常重要的非线性结构， 所描述的数据有明显的层次关系， 其中的每个元素只有一个前驱， 二叉树是最为常用的数据结构， 它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为： NLR先根结点，然后左子树，右子树；中序遍历顺序为； LNR先左子树，然后根结点，右子树；后序遍历顺序为： LRN先左子树，然后右子树，根结点。由前序和中序遍历， 有中序和后序遍历序列可以唯一确定一棵二叉树。 对于给几个数据的排序或在已知的几个数据中进行查找， 二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为的一个序表的算法，都可以表示成一株二叉树。 反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论， 对于算法分析的某些最有启发性的应用， 是与给出用于计算各种类型中不同树的数目的公式有关的。本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序， 让我们对二叉树的理解有更好的效果。关键词：二叉树的遍历；左子树；右子树；递归I目录1. 问题概述31.1 问题描述31.2 需求分析31.3 设计内容和要求41.4 流程图及结构图42. 概要设计52.1 数据结构设计：52.2 源程序代码73. 调试分析133.1 调试中的问题134. 测试结果14总结17参考文献18II1. 问题概述1.1 问题描述创建二叉树并遍历基本要求：该程序集成了如下功能：（ 1）二叉树的建立（ 2）递归和非递归先序，中序和后序遍历二叉树（ 3）按层次遍历二叉树（ 4）交换二叉树的左右子树（ 5）输出叶子结点（ 6）递归和非递归计算叶子结点的数目1.2 需求分析分先序遍历，中序遍历和后序遍历三种情况考虑。1. 先序遍历，当二叉树非空时按以下顺序遍历，否则结束操作： 访问根结点；按先序遍历规则遍历左子树；按先序遍历规则遍历右子树；2. 中序遍历，当二叉树非空时按以下顺序遍历，否则结束操作： 按中序遍历规则遍历左子树；访问根结点；按中序遍历规 3 遍历右子树。3. 后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作： 按后序遍历规则遍历左子树；按后序遍历规则遍历右子树；访问根结点。31.3 设计内容和要求对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种周游，输出三种周游的结果。1.4 流程图及结构图开始i=0NOYESi<nbtreetypenewNodeNO是否为空YESroot=newNodeMultiplexi+returnroot结束图 1.1 流程图4abcdef图 1.2 二叉链表存储结构模拟图2. 概要设计2.1 数据结构设计：1 二叉树结点数据类型定义为：template<typenameT>structBiNodeBiNode<T>*rchild,*lchild;/指向左孩子的指针Tdata;/结点数据信息 ;2 二叉树数据类型定义为：template<typenameT>classBiTreetemplate<typenameT>friendostream&operator<<(ostream&os,BiTree<T>&bt);public:BiTree();/无参构造函数BiTree(intm);/有参空构造函数BiTree(Tary,intnum,Tnone);/有参构造函数5BiTree();/析构函数voidpreorder();/递归前序遍历voidinorder();/递归中序遍历voidpostorder();/递归后续遍历voidlevelorder();/层序遍历intcount();/ 计算二叉树的结点数voiddisplay(ostream&os);/ 打印二叉树，有层次voidLevelNum();/计算每一层结点数voidPreOrder();/非递归前序遍历voidPostOrder();/非递归后序遍历voidcreat();/创建二叉树protected:/ 以下函数供上面函数调用 / 对应相同功能Voidcreat(BiNode<T>*&root);/创建voidrelease(BiNode<T>*&root);/删除BiNode<T>*Build(Tary,intnum,T none,intidx);/用数 组创建二叉树voidPreOrder(BiNode<T>*root);/前序遍历voidPostOrder(BiNode<T>*root);/后续遍历voidLevelNum(BiNode<T>*root);/层序遍历voidpreorder(BiNode<T>*root);/递归前序遍历voidinorder(BiNode<T>*root);/递归中序遍历voidpostorder(BiNode<T>*root);/递归后续遍历voidlevelorder(BiNode<T>*root);/层序遍历intcount(BiNode<T>*root);/ 计算结点数voiddisplay(ostream&os,BiNode<T>* root,intdep);/打印staticboolleastCommanAncestor(BiNode<T>*root,Tva, T vb,BiNode<T>private:BiNode<T>*rootptr;62.2 源程序代码#include <iostream>using namespace std;/*/二叉树结点类的定义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 createBinTree(BTNode<T> * &root )BTNode<T>* p = root;BTNode<T>* k;T nodeValue ;cin>>nodeValue;if(nodeValue=-1)root=NULL;7elseroot=new BTNode<T>();root->data = nodeValue;createBinTree(root->Lchild);createBinTree(root->Rchild);/*/二叉树的先序遍历template <class 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)8inOrder(p->Lchild);cout<<p->data<<" "inOrder(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;return 1+countNode(p->Lchild)+countNode(p->Rchild);/*/求二叉树的深度template<class T>9int 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>* destroy(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)10system("cls");cout<<"nnn-主界面 -nnn"cout<<"1、创建二叉树2、先序遍历二叉树 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<<"请输入每个结点，回车确认，并以 -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<<endl;11system("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<<"二叉树中结点总数为 "<<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");12elsesystem("cls");cout<<"nnnnnt 错误选择！ n"3. 调试分析3.1 调试中的问题创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。二叉树遍历：递归算法、非递归算法测试，调用相应函数进行测试，结果正确。求二叉树深度和结点数： 创建一个二叉树， 调用相关函数， 测试结果正确。 计算每层结点数：调用levelNum() 函数，测试结果正确。调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题。134. 测试结果（ 1）初始界面 : 主界面所包含的内容图 4.1 初始界面图（2）运行结果：进行操作1，输入每个结点，显示结果如下图 4.2 创建二叉树14进行操作 2，执行结果如下：图 4.3 二叉树先序遍历进行操作 3，执行结果如下：图 4.4 二叉树中序遍历进行操作 4，执行结果如下：15图 4.5 二叉树后序遍历:进行操作 5，执行结果如下：图 4.6 统计二叉树节点进行操作 6，执行结果如下：图 4.7 查看树深度16总结要能很好的掌握编程 , 仅仅通过几个简单的程序的编写时无法达成的 , 更需要大量积累和深入才可能通过本次课程设计。 有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好的完成课题， 这就需要一种能力， 即自学能力。本次课程设计还让我认识到自己的缺点。 本次选的课题是二叉树的遍历， 因为本学期所学的就是二叉树等数据结构， 所以认为比较适合。 刚开始认为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。经过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致， 而且还拓展了我的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力， 拓展了我的知识面， 让我对数据结构更加了解。17参考文献1 严蔚敏 吴伟民 数据结构 (C 语言版 ) 清华大学出版社，2009 年9月2谭浩强 C程序设计 ( 第三版 ) 清华大学出版社2009 年 1 月18