二叉树的遍历.doc

数据结构课程设计数据结构课程设计报告设计题目：_姓名：_学号：_专业：_院系：_班级：_指导教师：_年 月 日 摘要针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象。如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：先根结点，然后左子树，右子树；中序遍历顺序为；先左子树，然后根结点，右子树；后序遍历顺序为：先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为的一个序表的算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC+，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。，让我们对二叉树的理解有更好的效果。关键字：二叉树 遍历 非递归 C+ LCA 英文摘要For many complicated data in the real world, such as the Genealogy of human society, various social organization, game traffic and other complex things or processes as well as the objective world, there are a wide range of branches or hierarchical characteristics of the object. such as the file structure of operating system, the model representation of artificial intelligence and algorithm analysis and the information organization of the database system, it is difficult to express the logical relation in the linear structure, so it is necessary to use non-linear structure such as numbers and graphs, so as to simulate the objective world problem, The tree structure is an important form of information in the computer domain, which solves the objective world problem, and the tree is widely used. In the application of tree structure, two-fork tree is the most common.Binary tree is a very important nonlinear structure, the data described have a clear hierarchical relationship, each of these elements only a precursor, binary tree is the most commonly used data structure, its practical application is very extensive, binary tree traversal way there are three kinds, the first sequence traversal, in the sequence traversal, sequential traversal, the order of the first sequence of traversal: First root node, then left subtree, right subtree, sequence traversal order, first left subtree, then root node, right subtree, followed by order: first left subtree, then right subtree, root node. A binary tree can be uniquely determined by the sequence of sequences and the sequential traversal. The binary tree can provide a very effective method for sorting several data or finding it in several known data, for example, in the search problem, any algorithm that uses the comparison method to find a sequence table with length can be represented as a binary tree. Conversely, any binary tree corresponds to an effective method for finding ordered tables according to the mathematical theory of trees, some of the most illuminating applications of algorithmic analysis are related to formulas for calculating the number of different trees in various types.This article mainly explains how to implement two-fork tree traversal. The binary tree traversal based on the binary tree of the two-fork linked list storage structure. The sequential traversal and subsequent traversal are implemented by a non recursive algorithm. The programming environment for VC + +, in addition to the traversal operation, but also increased the depth of the binary tree, summed up points, each layer node points, and the recent common ancestor (LCA) problem algorithm. , let us have a better understanding of the two-fork tree.Keywords: two-fork tree traversal non-recursive C + + LCA目 录一、问题描述61.1题目内容61.2基本要求6二、需求分析6三、概要设计63.1二叉树的抽象数据类型定义63.2二叉树的非递归前序遍历示意图73.3二叉树的非递归后序遍历示意图7四、数据结构设计74.1二叉树结点数据类型74.2二叉树数据类型8五、算法设计85.1算法分析85.2算法实现85.2.1 创建二叉树95.2.2 非递归前序遍历95.2.3 非递归后序遍历 105.2.4 求二叉树的高度 105.2.5 求二叉树的每一层结点数 115.2.6 求两结点最近共同祖先 125.3算法流程图 13六、程序测试与实现 136.1函数之间的调用关系 136.2主程序 146.3测试数据 156.4测试结果 15七、调试分析 17八、遇到的问题及解决办法 18九、心得体会 18十、参考文献 18一、问题描述1 题目内容：运用二叉树的操作来实现二叉树的遍历。2 基本要求：系统含有多个菜单项的主控菜单程序，功能包括二叉树的遍历、查询二叉树的深度、查询每层的结点数、查找两节点P和Q的最近共同祖先等等。3 要求显示查询结果。二、需求分析1 本程序的功能包括二叉树的建立、二叉树的删除、二叉树的遍历、查询二叉树的深度、查询每层的结点数、查找两节点P和Q的最近共同祖先等等。2 程序运行后显现提示信息，等候用户输入16以进入相应的操作功能。3 用户输入数据完毕，程序将输出运行结束。4 测试数据应为字符串类型。三、概要设计1 二叉树的抽象数据类型定义为：ADT BiTree 数据集合K：K=k1,k2,kn，K中的元素是T类型；数据关系R：R=r R中的元素为结点数据操作集合：(1) BiTree( ); 构造函数，初始化一棵二叉树，其前序序列由键盘输入(2) BiNode *Creat( ); 构造函数调用(3) BiTree(void); 析构函数，释放二叉链表中各结点的存储空间(4) void Release(BiNode *root); 析构函数调用(5) void NrecursionPreOrder(BiNode *root); 非递归前序遍历二叉树(6) void NrecursionPostOrder(BiNode *root); 非递归后序遍历二叉树(7) int depth(BiNode *root); 二叉树的深度(8) void LevelNum(BiNode * root); 计算每一层的结点数(9) T leastCommanAncestor(BiNode * root, T n1, T n2); 求最近共同祖先ADT BiTree；2 二叉树的非递归前序遍历示意图 先序序列：A B C D E F G H K图3.1 二叉树前序遍历示意图3 二叉树的非递归后序遍历示意图 后序序列：D C B H K G F E A图3.2 二叉树后序遍历图四、数据结构设计1.二叉树结点数据类型定义为： template struct BiNode /二叉树的结点结构 T data; 结点数据信息 BiNode *lchild, *rchild; 指向左右孩子的指针 int flag; 2.二叉树数据类型定义为：template class BiTreepublic: BiTree( ); /构造函数，初始化一棵二叉树，其前序序列由键盘输入 BiTree(void); /析构函数，释放二叉链表中各结点的存储空间BiNode* Getroot(); /获得指向根结点的指针 void PreOrder(BiNode *root); /前序遍历二叉树 void InOrder(BiNode *root); /中序遍历二叉树 void PostOrder(BiNode *root); /后序遍历二叉树void NrecursionPreOrder(BiNode *root);/非递归前序遍历二叉树void NrecursionInOrder(BiNode *root);/非递归中序遍历二叉树void NrecursionPostOrder(BiNode *root);/非递归后序遍历二叉树void countNode(BiNode *root,int& count);/二叉树结点个数int depth(BiNode *root);/二叉树的深度void countleaf(BiNode *root,int& count);/叶子结点的个数void seek(BiNode *root,T num);/查找某一结点左右孩子的算法void LevelNum(); /计算每一层的结点数void LevelNum(BiNode * root);T leastCommanAncestor(T n1 ,T n2);/求最近共同祖先T leastCommanAncestor(BiNode * root, T n1, T n2);private: BiNode *root; /指向根结点的头指针 BiNode *Creat( ); /构造函数调用 void Release(BiNode *root); /析构函数调用 ;五、算法设计1、算法分析 （1）非递归前序遍历 首先把根节点入栈，并且在根节点出栈的时候访问根节点；同时判断根节点的右子树是否为空，若不为空，则右孩子入栈；判断根节点的左孩子是否为空，若不为空，则左孩子入栈。当栈不为空时，重复以上操作。 （2）非递归后序遍历首先根节点入栈，然后判断左孩子是否为空，若不为空，则左孩子入栈，并移动root到左孩子，直到左孩子为空。然后判断栈顶元素，如果栈顶元素没有右孩子或者右孩子已经被访问过，那么就访问该栈顶元素，并出栈；如果栈顶元素有右孩子并且右孩子没有被访问过，那么把右孩子入栈，把root指针指向右孩子。 （3）求二叉树的高度 先遍历二叉树的左子树的深度，然后再遍历二叉树右子树的深度。最后判断左子树和右子树的深度，如果左子树比右子树深则返回左子树深度+1,否则返回右子树深度+1。 （4）求二叉树的每一层结点数 利用两个队列完成计算二叉树的每一层结点数。首先将根结点进队列1，如果队列1不空，则出队列，如果出队列的该结点存在左右孩子，则将左右孩子进队列1，如果队列1的front等于队列2的last，则输出第i层有last-first个结点，level加1，令last等于rear,first等于front. （5）求两结点共同祖先给出任意两个结点P和Q后，先从P开始向上遍历父结点，并进行标记，直至指针指向NULL。接着，从Q开始遍历其父结点，当指针遇到标记时退出循环。输出最近共同祖先，否则无共同结点。2、算法实现(1) 创建二叉树 /实现外部递归调用 templateBiTree:BiTree( )this-root = Creat( );/创建二叉树template BiNode* BiTree:Creat( )BiNode* root;T ch;cinch; if (ch=#) root = NULL; else root = new BiNode; /生成一个结点 root-data=ch; root-lchild = Creat( ); /递归建立左子树 root-rchild = Creat( ); /递归建立右子树 return root;(2) 非递归前序遍历 templatevoid BiTree:NrecursionPreOrder(BiNode *root)SeqStackBiNode* S; /定义一个树结点指针类型的栈SBiNode*p;p=root;while(p!=NULL | S.Empty()!=1) /指针p指向的结点不空，同时栈不为空while(p!=NULL) /p指向的结点不空coutdatalchild; /p指向p的左孩子if(S.Empty()!=1) /如果栈不空p=S.Pop(); /将栈中结点p的元素出栈p=p-rchild; /p指向p的右孩子(3) 非递归后序遍历templatevoid BiTree:NrecursionPostOrder(BiNode *root)SeqStackBiNode* S;BiNode*p;p=root;while(p!=NULL|S.Empty()!=1) /指针p指向的结点不空，同时栈不为空while(p!=NULL) /p指向的结点不空p-flag=1; S.Push(p);p=p-lchild;while(S.Empty()!=1 & S.GetTop()-flag=2)coutdataflag=2;p=S.GetTop()-rchild;(4) 求二叉树的高度 templateint BiTree:depth(BiNode *root)int l,r; /l左子树 ，r右子树if(root=NULL) /根结点为空return 0; /返回0l=depth(root-lchild); /左子树的深度r=depth(root-rchild); /右子树的深度return lr ?l+1:r+1; /选择左右子树中深度大的数目，最后加上根结点(5) 求二叉树的每一层结点数template void BiTree:LevelNum()LevelNum(Getroot();template void BiTree:LevelNum(BiNode * root)queue BiNode * q;int front, rear, first, last, level;front = rear = first = 0;last = level = 1;if (root)q.push(root);rear+;while (frontlchild)q.push(root-lchild);rear+;if (root-rchild)q.push(root-rchild);rear+;if (front = last)cout 第 level 层有 last - first 个结点 endl;level+;last = rear;first = front;(6) 求两结点最近共同祖先template T BiTree:leastCommanAncestor(T n1,T n2)return leastCommanAncestor(root, n1, n2);template T BiTree:leastCommanAncestor(BiNode * root, T n1, T n2)if (root = NULL | root-data = n1 | root-data = n2)throw 错误;if (root-rchild != NULL) & (root-rchild-data = n1 | root-rchild-data = n2)return root-data;if (root-lchild != NULL) & (root-lchild-data = n1 | root-lchild-data = n2)return root-data;if (root-data n1 & root-data data;if (root-data n1 & root-data n2)return leastCommanAncestor(root-lchild, n1, n2);if (root-data data rchild, n1, n2);3、算法流程图 程序初始化 用户输入选择 用户交互创建二叉树 遍历二叉树 求深度 求每层结点 求共同祖先 处理并输出结果 结束图5.3 算法流程图六、程序测试与实现1、函数之间的调用关系Mainmenu_selectGreate Order depth LevelNum leastCommanAncestor2、主程序 void main()display();cout 请输入二叉树的前序遍历： endl;cout (以#作为分支结尾，例如：A B # # C # #) endl;BiTree bt; /创建一棵树BiNode* root = bt.Getroot(); /获取指向根结点的指针 while (1)cout x;switch (x)case 1:display();cout endl;break;case 2:cout endl;cout 前序遍历为：;bt.NrecursionPreOrder(root);cout endl;cout 中序遍历为：;bt.NrecursionInOrder(root);cout endl;cout 后序遍历为：;bt.NrecursionPostOrder(root);cout endl;cout endl;break;case 3:int count1=0, count2=0;cout 树的深度为： bt.depth(root) endl;cout endl;break;case 4:bt.LevelNum();cout endl;break;case 5:string ch1, ch2;cout c