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

《大数据结构课程设计二叉树地遍历》由会员分享，可在线阅读，更多相关《大数据结构课程设计二叉树地遍历（25页珍藏版）》请在装配图网上搜索。

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

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

3、于计算各 种类型中不同树的数目的公式有关的。本文对二叉树以与二叉树的各种功能做介绍以与写出一些根本的程序，让我 们对二叉树的理解有更好的效果关键词：二叉树的遍历；左子树；右子树；递归目录1问题概述3问题描述3需求分析3设计内容和要求4流程图与结构图42. 概要设计8数据结构设计：8源程序代码103. 调试分析19调试中的问题194. 测试结果19总结23参考文献24II / 24word1. 问题概述问题描述创建二叉树并遍历根本要求:该程序集成了如下功能：1二叉树的建立2递归和非递归先序，中序和后序遍历二叉树3按层次遍历二叉树4交换二叉树的左右子树5输出叶子结点6递归和非递归计算叶子结点的数目

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

5、的 先序、中序、后序三种周游，输出三种周游的结果。流程图与结构图13 / 24开始NOi=0NO完毕Multiplex图1.1流程图bc图二叉链表存储结构模拟图2. 概要设计数据结构设计：1. 二叉树结点数据类型定义为：template vtypename T struct BiNodeBiNode*rchild,*lchild;指向左孩子的指针T data;/结点数据信息;2. 二叉树数据类型定义为：template class BiTree templatepubfriend ostream & operator (ostream &os ,BiTree &bt);lic:BiTree()

6、;无参构造函数BiTree(i ntm);/有参空构造函数BiTree(T ary,int num,T none); 有参构造函数BiTree();析构函数voidpreorder();递归前序遍历void in order(); 递归中序遍历voidpostorder(); 递归后续遍历voidlevelorder();层序遍历intcou nt();计算二叉树的结点数voiddisplay(ostream&os); 打印二叉树，有层次voidLevelNum();计算每一层结点数voidPreOrder(); 非递归前序遍历voidPostOrder();非递归后序遍历voidcreat(

7、);/创建二叉树protected:/以下函数供上面函数调用/对应一样功能Voidcreat(BiNode*&root);创建voidrelease(BiNode*& root);/ 删除BiNode * Build(T ary,int num,T none,intidx);/ 用数组创建二叉树voidPreOrder(BiNode* root);/ 前序遍历voidPostOrder(BiNode* root);/ 后续遍历voidLevelNum(BiNode* root);/ 层序遍历voidpreorder(BiNode* root);/ 递归前序遍历voidin order(BiNo

8、de*root);/递归中序遍历voidpostorder(BiNode*root);/递归后续遍历voidlevelorder(BiNode*root);/层序遍历intcou nt(BiNode* root);/计算结点数voiddisplay(ostream&os,BiNode* root,intdep);/ 打印static bool leastmanAncestor(BiNode *root, T va, T vb, BiN odeprivate:BiNode *rootptr;源程序代码#i nclude using n amespace std;*二叉树结点类的定义templat

9、estruct BTNodeT data;BTNode * Lchild,*Rchild;BTNode(T no deValue = T(),BTNode* leftNode = NULL,BTNode* rightNode = NULL ):data( nodeValue),Lchild(leftNode),Rchild(rightNode)/ 可选择参数的默认构造函数；*/二叉树的建立template vclass Tvoid createBi nTree(BTNode * &root ) BTNode* p = root;BTNode* k;T no deValue ;cinno deV

10、alue;if(no deValue=-1)root=NULL;elseroot=new BTNode(); root-data = no deValue;createB in Tree(root-Lchild);createB in Tree(root-Rchild);*二叉树的先序遍历template vclass Tvoid preOrder( BTNode * & p)if(p)coutdataLchild);preOrder(p-Rchild);*二叉树的中序遍历template void in Order(BTNode * & p)if(p)in Order(p-Lchild);

11、coutdataRchild);*二叉树的后序遍历template void levelOrder(BTNode *& p) if(p)levelOrder(p-Lchild); levelOrder(p-Rchild); coutdata in t cou ntNode(BTNode * & p)if(p = NULL) return 0;retur n 1+co un tNode(p-Lchild)+co un tNode(p-Rchild);*II求二叉树的深度templatevclass Tint depth(BTNode *& p)if(p = NULL)return -1;int

12、hl = depth(p-Lchild);int h2 = depth(p-Rchild);if(h1h2)return (h1+1);return h2+1;*二叉树的消毁操作II*14 I 24wordtemplatevclass T消毁函数，用BTNode* destroy(BTNode* p)来消毁二叉树中的各个结点if(p)return destroy(p-Lchild);return destroy(p-Rchild); delete p;19 / 24*/主函数的设计int mai n ()BTNode * rootNode = NULL;int choiced = 0;whil

13、e(true)system(cls);coutnnn-主界面-nnn;coutvv1、创建二叉树2、先序遍历二叉树ncoutvv3、中序遍历二叉树4、后序遍历二叉树ncoutvv5、统计结点总数&查看树深度ncoutvv7、消毁二叉树0、退出 nn;coutvv请选择操作：；cin choiced;if(choiced = 0)return 0;else if(choiced = 1)system(cls);coutvv请输入每个结点，回车确认，并以-1完毕：n;createB in Tree(rootNode );else if(choiced = 2)system(cls);coutvv先

14、序遍历二叉树结果：n;preOrder(rootNode);coutvve ndl;system(pause);else if(choiced = 3)system(cls);cout中序遍历二叉树结果：n;inO rder(rootNode);coute ndl;system(pause);else if(choiced = 4)system(cls);cout后序遍历二叉树结果：n;levelOrder(rootNode);coute ndl;system(pause);else if(choiced = 5)system(cls);int count = coun tNode(rootN

15、ode);cout二叉树中结点总数为ents and SettingYAdBimst EatorJW机康软件Debugiangyu, eier主界面遍历二刃 遍反二冥叉数树二总捌叉历点X:二遍结二l4t毀创B-S消* 弔13 5 7图初始界面图2运行结果：进展操作 1输入每个结点，显示结果如下图创建二叉树20 / 24word25 / 24进展操作2,执行结果如下:图二叉树先序遍历进展操作3,执行结果如下:图二叉树中序遍历进展操作4,执行结果如下:图二叉树后序遍历进展操作5,执行结果如下:图统计二叉树节点进展操作6,执行结果如下:图查看树深度总结要能很好的掌握编程，仅仅通过几个简单的程序的编写

16、时无法达成的 ，更需 要大量积累和深入才可能通过本次课程设计。 有关一个课题的所有知识不仅仅是 在课本上，多查阅一些资料能够更好的完成课题， 这就需要一种能力，即自学能 力。本次课程设计还让我认识到自己的缺点。 本次选的课题是二叉树的遍历，因 为本学期所学的就是二叉树等数据结构， 所以认为比拟适合。刚开始认为会很简 单，但到后来就出现一些难以解决的问题，就像教师请教，并查阅相关资料。经 过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我 的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力， 拓展了我的知识面，让我对数据 结构更加了解。参考文献1 严蔚敏吴伟民数据结构（C语言版）清华大学，2009年9月2 谭浩强C程序设计（第三版）清华大学2009年1月