《基于二叉树遍历系统设计与实现课程设计论文.doc》由会员分享，可在线阅读，更多相关《基于二叉树遍历系统设计与实现课程设计论文.doc（23页珍藏版）》请在三一办公上搜索。
1、长春建筑学院数据结构课程设计（论文）基于二叉树遍历系统设计与实现Binary tree traversal System Design and Implementation年 级: 学 号: 姓 名: 专 业: 指导老师: 二零一三年十二月摘 要 针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任
2、务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方
3、法，比如在查找问题上，任何借助于比较法查找长度为的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让读者对二叉树的理解有更好的效果。关键词：二叉树； 左子树； 右子树AbstractIn many real world of complex data, such as the human society family, social organization, widespread game
4、 traffic complex thing or process and the objective world with a branch or level characteristics of the object. If the operating system file analysis, artificial intelligence and algorithm model representation and database information system the form of organization, with a linear structure to expre
5、ss the logic relationship among them, must depend on the number and the diagram of such nonlinear structure, so in order to simulate the objective world, solve problems as the main task of the computer field in the tree structure is an important organization form of information, the tree has a broad
6、 application. In the application of tree structure in which the two fork tree is the most commonly used.Two binary tree is a kind of very important nonlinear structure, hiberarchy description of the data, where each element is only a precursor, two fork tree is the most commonly used data structure,
7、 its application is very extensive, there are three kinds of two binary tree traversal, preorder traversal, in the traversal, postorder traversal, preorder traversal sequence: NLR to the root node, and then the left subtree, right subtree; in order traversal sequence; LNR before the left sub tree, t
8、hen the root node, the right subtree; after the traversal order: LRN first and then the left subtree, right subtree, root node. By preorder traversal and traversal, with the order and post order traversal sequence can be uniquely identified a two binary tree.For several data sorting or searching in
9、several data known, two fork tree can provide a very effective method, such as search problems, any by the comparison method to find the length of a sequential algorithm of Table IV, can be expressed as a two fork tree. Conversely, any two fork tree corresponds to an effective method to find the ord
10、ered list according to the mathematical theory of tree, for some algorithm analysis of the application of heuristic, is given for the number and different types of tree calculation formula.Various functions of two binary tree and binary tree in this paper two introduces and write some of the basic p
11、rocedures, to allow readers to understand the two fork tree has a better effect.Keywords:Two tree; the left subtree; right subtree目 录摘 要IABSTRACT 第1章 绪 论11.1 设计目的11.2 设计内容11.3 设计要求11.4 设计思想21.5 系统模块划分21.6 主要功能模块设计2第2章 系统总体设计32.1 基本理论32.2 概要设计3第3章 详细设计43.1 建立二叉树43.2 二叉树的层次遍历和中序遍历43.3 求二叉树的深度73.4 将二叉树
12、中所有结点的左右子树相互交换73.5 求二叉树中叶子结点的数目9第4章 流程分析图114.1 流程图114.2 主要功能模块设计114.3 模块设计124.4 函数主要调用关系图13第5章 系统测试145.1 调试分析145.2 实验结果15结 论17致 谢18参考文献18第1章 绪 论引言： 树型结构是一类重要的非线性数据结构，其中一树和二叉树最重要。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构够可以用树来形象表示。树在计算机领域中也得到了广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。二叉树是一种非线性数据结构，对它进行操作时总需要对每个数据逐一进行操作，这样就
13、存在一个操作顺序问题，由此提出了二叉树的遍历操作问题，所谓遍历二叉树就是按某种顺序访问二叉树中某个结点一次且仅一次的过程，这里的访问可以是输出.比较.更新.查看元素内容等各种操作。1.1 设计目的1. 掌握二叉树结点结构的建立。 2.掌握先序、中序和后序遍历的基本操作。1.2 设计内容 利用二叉树特点和功能实现先序、中序和后序遍历系统的实现，具体功能：输入、输出遍历结果、先序遍历、中序遍历和后序遍历，并能在屏幕上输出操作前后的结果。1.3 设计要求1.写出系统需求分析,并建模。 2.编程实现,界面友好。 3.输出操作前后的结果。4.提供测试报告。1.4 设计思想1. 建立二叉树采用一个一个输入
14、的方式。2.对二叉树进中序遍历采用递归函数和非递归函数分别实现多种遍历的方式。另外还有层次遍历，来充分实现本书对树的遍历。3.删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点则删除。1.5 系统模块划分 1.二叉树是一种动态树表。 2.开辟一个空间建立一个节点，逐个加入，逐个建立。 3.利用查找函数，对数进行插入删除。 4.利用书中所学知识进行各种遍历，包括将所有方法归并在一起，还要建立查看界面一边有系统的视觉效果。1.6 主要功能模块设计 程序主要设计了几个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了八个模块：树状输出二叉树，前序遍历
15、二叉树，中序遍历二叉树，后序遍历二叉树，输出叶子结点，输出叶子结点个数，输出二叉树的深度，退出。第2章 系统总体设计2.1 基本理论（1）建立二叉树的操作就是用递归算法以先序遍历的次序从根结点开始建立一棵二叉树。（2） 利用栈的非递归算法对二叉树进行遍历，从二叉树的根结点开始，自顶向下，同层自左往右访问树中的每个结点，此时，保存结点的顺序和访问的顺序刚好一致。（3） 用递归算法求出左右子树的深度。需求分析：（1）输入二叉树的特殊先序序列，建立二叉树。（2）实现二叉树的层次遍历和中序遍历。（3）求二叉树的深度。（4）将二叉树中所有结点的左右子树相互交换。（5）求二叉树中叶子结点的数目。2.2 概
16、要设计CreatBinTree(&T):建立一棵二叉树，Value(T,e)：查找值为e的二叉树结点，并返回该结点的地址。BinTreeDepth(T)：返回二叉树的深度，Parent(T,e)：查找二叉树T中的值为e的结点的双亲，若没有根结点，则操作失败。PreOrderTraverse(T)：先序遍历二叉树，并输出结点序列。InorderTraverse(T)：中序遍历二叉树，并输出结点序列。PostOrderTraverse(T)：后序遍历二叉树，并输出结点序列。 LevelOrderTraverse(T)：层次遍历二叉树，并输出结点序列。说明本程序中用到的所有抽象数据类型的定义、主程序
17、的流程以及各程序模块之间的层次(调用)关系。第3章 详细设计3.1建立二叉树VoidCreateBinTree(BinTree&T)/按先序次序输入二叉树中结点的值/构造二叉链表表示的二叉树TTelemTypech；Scanf(“%c”,&ch);If(i=)T=Null;ElseT=(BinTree)malloc(sizeof(BinTNode);/生成根结点Id(!=T)Exit(0);T-data=ch;CreateBinTree(T-lchild);/构造左子树CreateBinTree(T-rchild);/构造右子树Return;3.2 二叉树的层次遍历和中序遍历中序遍历模块（以中
18、序为例来说明）遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。二叉树共有三个部分组成，即根结点，根结点的左子树，根结点的右子树。限定以从左至右方式共有三种遍历方式，即前序遍历，中序遍历，后序遍历。中序遍历的原则：若被遍历的二叉树为非空，则依次执行如下操作：#include/malloc()等#include/标准输入输出头文件，包括EOF(=Z或F6)，NULL等#include/atoi()，exit()#include/数学函数头文件，包括floor()，ceil()，abs()等#defineClearBi
19、TreeDestroyBiTree/清空二叉树和销毁二叉树的操作一样typedefstructBiTNodeintdata;/结点的值 BiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;intNil=0;/设整型以0为空voidvisit(inte)printf(%d,e);/以整型格式输出voidInitBiTree(BiTree&T)/操作结果：构造空二叉树TT=NULL;voidCreateBiTree(BiTree&T)/算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，/构造二叉链表表示的二叉树T。变量Nil表示空
20、(子)树。修改intnumber;scanf(%d,&number);/输入结点的值if(number=Nil)/结点的值为空T=NULL;else/结点的值不为空T=(BiTree)malloc(sizeof(BiTNode);/生成根结点if(!T)exit(OVERFLOW);T-data=number;/将值赋给T所指结点CreateBiTree(T-lchild);/递归构造左子树CreateBiTree(T-rchild);/递归构造右子树voidDestroyBiTree(BiTree&T)/初始条件：二叉树T存在。操作结果：销毁二叉树Tif(T)/非空树DestroyBiTre
21、e(T-lchild);/递归销毁左子树，如无左子树，则不执行任何操作DestroyBiTree(T-rchild);/递归销毁右子树，如无右子树，则不执行任何操作free(T);/释放根结点T=NULL;/空指针赋0 voidPreOrderTraverse(BiTreeT,void(*Visit)(int)/初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算 法6.1/操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T)/T不空Visit(T-data);/先访问根结点PreOrderTraverse(T-lchild,Visit);/再先序遍历左子树
22、PreOrderTraverse(T-rchild,Visit);/最后先序遍历右子树voidInOrderTraverse(BiTreeT,void(*Visit)(int)/初始条件：二叉树T存在，Visit是对结点操作的应用函数/操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T) InOrderTraverse(T-lchild,Visit);/先中序遍历左子树Visit(T-data);/再访问根结点InOrderTraverse(T-rchild,Visit);/最后中序遍历右子树 voidPostOrderTraverse(BiTreeT,void(*Vi
23、sit)(int)/初始条件：二叉树T存在，Visit是对结点操作的应用函数/操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次if(T)/T不空PostOrderTraverse(T-lchild,Visit);/先后序遍历左子树 PostOrderTraverse(T-rchild,Visit);/再后序遍历右子树 Visit(T-data);/最后访问根结点voidmain()BiTreeT;InitBiTree(T);/初始化二叉树Tprintf(按先序次序输入二叉树中结点的值,输入0表示节点为空， 输入范例：1200300n);CreateBiTree(T);/建立二
24、叉树T printf(先序递归遍历二叉树：n);PreOrderTraverse(T,visit);/先序递归遍历二叉树T printf(n中序递归遍历二叉树：n);InOrderTraverse(T,visit);/中序递归遍历二叉树T printf(n后序递归遍历二叉树：n); PostOrderTraverse(T,visit);/后序递归遍历二叉树T3.3求二叉树的深度树的深度组成该树各结点的最大层次IntBinTreeDepth(BinTreeT)/初始条件：二叉树存在/操作结果：返回T的深度Inti,j;if(!T)return0;/i为左子树的深度i=BinTreeDepth(B
25、inTreeT-lchild);/j为右子树的深度J=BinTreeDepth(BinTreeT-rchild);Return(ij)?(i+1):(j+1)3.4 将二叉树中所有结点的左右子树相互交换#include#includetypedefstructbinodeintdata;structbinode*lchild,*rchild;binode,*bitree;typedefstructbitreeelem100;inttop;stack;bitreecreat_bt()/按扩展前序建二叉树bitreet;intx;scanf(%d,&x);if(x=0)t=NULL;elset=(
26、bitree)malloc(sizeof(binode);t-data=x;t-lchild=creat_bt(); t-rchild=creat_bt();returnt;voidexchange(bitreet)/左、右子树交换bitreep;if(t!=NULL)p=t-lchild;t-lchild=t-rchild;t-rchild=p;exchange(t-lchild);exchange(t-rchild);voidinorder(bitreebt)/递归的中序遍历if(bt) inorder(bt-lchild);printf(%d,bt-data);inorder(bt-rc
27、hild);main()bitreeroot;printf(n);printf(建二叉树，输入元素：);root=creat_bt();/*createtreeofuseingpreorder*/printf(交换前的中序序列是：);inorder(root);exchange(root);printf(n交换后的中序序列是：);inorder(root);printf(n);return;3.5 求二叉树中叶子结点的数目#includeusingnamespacestd;typedefstructTNode/二叉树结构charnodeValue;/结点的值TNode*left;/左子树TNo
28、de*right;/右子树*BiTree;voidCreateBiTree(BiTree&T)/中序遍历方式创建二叉树,输入#代表该结点空charnodeValue; cinnodeValue;if(nodeValue!=#)/结点非空T=newTNode;T-nodeValue=nodeValue; CreateBiTree(T-left);CreateBiTree(T-right);elseT=NULL; intCountLeaf(BiTreeT)staticintLeafNum=0;/叶子初始数目为0，使用静态变量 if(T)/树非空if(T-left=NULL&T-right=NULL
29、)/为叶子结点LeafNum+;/叶子数目加1else/不为叶子结点CountLeaf(T-left);/递归统计左子树叶子数目CountLeaf(T-right);/递归统计右子树叶子数目 returnLeafNum;该模块功能主要是给用户提供清晰的可操作界面，易于人机操作，并能很好的调用其他各模块，使程序更加优化，丝路更加清晰，结构更加明了，提高了程序的实用性。其算法如下：/用来测试的main函数，intmain()BiTreeT;intleafNum;cout请输入中序遍历的二叉树序列(#号代表该结点为空)：如(ABC#DE#G#F#)endl;CreateBiTree(T);leafN
30、um=CountLeaf(T);cout该二叉树中叶子结点数为：leafNumendl;return0;第四章 流程分析图4.1 二叉树的生成过程二叉树的生成，采用逐个建立的方式。如图所示：初始化数组插入头结点点空树添加左子输添加右孩数插入插入插入是是否否 图4-1 二叉树建立4.2 主要功能模块设计 程序主要设计了几个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了八个模块：树状输出二叉树，前序遍历二叉树，中序遍历二叉树，后序遍历二叉树，输出叶子结点，输出叶子结点个数，输出二叉树的深度，退出。主函数流程如下：否否否否否是创建二叉排序树Switch()递归遍历Switch(0)Ex
31、it(0)退出Switch()删除结点Switch()default提示出错非递归遍历是是是是是是是是 图4-2主函数流程图4.3模块设计本程序包含三个模块：主程序模块、建立二叉树模块和工作区模块。其调用关系如图4-3所示。 主程序模块建立二叉树模块工作区选择模块4-3模块调用示意图4.4 函数主要调用关系图本系统11个子程序之间的主要调用关系如图4-4所示。图中数字是各函数的编号。10 mainwork()98765423111 main()4-4系统函数调用关系图第5章 系统测试5.1 调试分析 1在调试过程中出现了很多次的程序错误，警告和不能运行。在很多次的调试和重新改写之后，才可以用。
32、 2VisualC+确实是一门需要极其细心和耐心的课程，尤其在程序设计的过程中不可有一丝的马虎大意，否则将会花很大力气去改正。3.调试过程中最常见的便是代码输入错误，如字母大小写、顺序颠倒、符号的半/全角使用等一些问题，都是在调试过程中逐一改正的。4.本程序是二叉树最基本的操作，没有深入。难免在执行程序时对输入的其他指令发生错误。所以只要根据本程序的说明操作即可。 5.我想以后还可以给此程序添加其他一些功能，例如创建的二叉树是空树还是满二叉树；对创建的二叉树进行查找，删除，插入，匹配；如何解决程序顺利执行而不会陷入死循环一些问题等等。5.2 实验结果先序、中序遍历：后序遍历、输出叶子结点：输出
33、叶子结点个数、二叉树深度：结果分析： 实验实现了二叉树的三种遍历算法，想要改进的话可以在扩充其功能上下手，例如实现更多遍历算法，建立的时候提示更人性化，对输入的数据进行有效性验证等等。花了不少心思在代码的复用上，尽管复用的技术还不算高超，不过对于这次的实验要求来说，已经有很大进步。实验结果的排序完全正确。程序可以实现用户自己构造二叉树，然后实现对二叉树的层次遍历。程序基本上满足了算法设计要求，但是仍有地方值得提高，仍需完善。结 论 对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为的一个序表的算法，都可以表示成一株二
34、叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。通过课程设计自己对数据结构这门课程有了更深一层的了解，意识到了数据结构的重要性，同时也对c语言的掌握更进一步，熟悉了对于指针，链表，队列等的操作，对程序设计的过程也有了自己的一些理解：首先，要对到手的问题要认真思考，如何实现，用何种方法实现，力求最简，在保证正确性的基础上提高程序效率；其次，确定了实现的方法之后就要用程序语言将想法表示出来；最后，进行调试和排错，一个有效的方法是在前面遇到问题时在旁边加上必要的注释，进行调试的时候可以尽快看清问题所在。致 谢 通过本次课程设计，使我对数据结构这门课的认识更进一步，数据结构作为计算机专业的一门必修课，对如何编写好的算法进行了比较深入的阐述，为我们写出正确的，强壮的代码奠定了基础。在做课程设计的过程中，从查阅的相关资料和问题的解决中学到了不少的知识，因此对课本上的知识也有了更深入的了解。 参考文献1 唐国民，王国钧. 数据结构. 第一版.清华大学出版社，2009年2 郑山红，李万龙，于秀霞. C语言程序设计. 第二版.人民邮电出版社，2012年.
