学位论文—基于二叉树遍历系统设计与实现课程设计

课程设计课程设计名称:数据结构课程设计专业班级：学生姓名：学号：指导教师:课程设计时间：数据结构专业课程设计任务书说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页一、需求分析1.1课程设计题目、任务及要求二叉树.用链表作存储结构（1）对二叉树作各种遍历，输出结果；（4）输入元素x,查找二叉树的左孩子，右孩子,如果找到则删除该结点,没有找到就退出,返回错误。

1.2课程设计思想建立二叉树采用一个一个输入的方式。

对二叉树进中序遍历采用递归函数和非递归函数分别实现多种遍历的方式。

另外还有层次遍历，来充分实现本书对树的遍历。

删除结点函数,采用边查找边删除的方式。

如果没有查找到，则不对树做任何的修改；如果查找到结点则删除.一、系统总体设计3。

1 系统模块划分二叉树是一种动态树表。

开辟一个空间建立一个节点，逐个加入，逐个建立。

利用查找函数，对数进行插入删除利用书中所学知识进行各种遍历，包括将所有方法归并在一起，还要建立查看界面一边有系统的视觉效果.3.2 二叉树的生成过程二叉树的生成，采用逐个建立的方式。

如图3。

3 主要功能模块设计程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块:退出，中序遍历，计算平均查找长度和删除结点。

主函数流程如下：图3。

1.1主函数流程图4 系统详细设计4.1 主函数菜单模块该模块功能主要是给用户提供清晰的可操作界面，易于人机操作，并能很好的调用其他各模块，使程序更加优化，丝路更加清晰,结构更加明了，提高了程序的实用性。

其算法如下:(完整word版)二叉树的遍历--课程设计void main(）{int n,m=1；BiTree t;while(m){menu();scanf("％d”，＆n）；switch（n）｛case 1：｛/＊初始化*/int flag；datatype x；printf(”请输入头结点x:\n");scanf（"％d”,&x）;flag=Initiate(&t,x）；if(flag==1）printf(”\n初始化成功！”）；elseprintf(”\n初始化失败！”）;break;}case 2：{printf(”\n请继续添加结点建立二叉树”）;/＊建树*/ break;｝case 3:{/*插入结点x作为a的左孩子＊/datatype a，x；/＊x作为a的左孩子*/BiTree parent=t；printf("请输入双亲a和左孩子x：\n")；scanf（”％d％d"，＆a,＆x）;parent=Find（parent,a）;parent=InsertL(t,x,parent）；if(parent！=NULL）t=parent;break;｝case 4：｛/*插入结点x作为a的右孩子＊/datatype a,x;/*x作为a的右孩子*/ BiTree parent=t;printf("请输入双亲a and右孩子x:\n”)；scanf(”％d％d"，&a,&x）;parent=Find(parent,a);parent=InsertR(t，x，parent);if（parent！=NULL）t=parent;break；｝case 5:｛/*删除结点a的左孩子*/ datatype a;BiTree parent=t；printf(”please input a：\n”);scanf（”%d”,&a)；parent=Find(parent,a）;parent=DeleteL（t，parent)；if（parent!=NULL）t=parent；break；｝case 6:｛/＊删除结点a的左孩子＊/ datatype a;BiTree parent=t;printf("please input a：\n"); scanf（"%d"，&a)；parent=Find(parent，a)；parent=DeleteR（t,parent);if（parent!=NULL）t=parent；break;｝case 7:｛/*递归先序遍历*/ PreOrder(t）;break；｝case 8：｛/＊递归中序遍历*/ InOrder(t);break;｝case 9:{/＊递归后序遍历＊/ PostOrder(t）;break；}case 10:｛/*层次遍历*/ LevelOrder（t）;break；}case 11:｛/＊先序遍历的非递归实现＊/ NRPreOrder（t);break;｝case 12:{/*中序遍历的非递归实现＊/ NRInOrder(t);break;}case 13:{/＊后序遍历的非递归实现*/NRPostOrder(t）；break;}case 0:m=0；｝｝}4。

二叉树遍历--教学设计所属学科：数据库专业：计算机(相关学科)课程：数据结构适用对象：大二上学期本课所讲解的内容为二叉树遍历的三种基本方法和一种新颖的方法，所属学科为数据结构与算法。

数据结构与算法是计算机专业的重要基础课，也是非计算机专业学生在大学生计算机等级考试中的课程之一，是一门集技术性、理论性和实践性于一体的课程。

故本微课结合该课程特点，合理分配知识结构及节奏，并融充分合多媒体技术，算法描述清晰，展现内容丰富，适合课堂教学，也便于自学，可作为高等院校计算机专业和其他相关专业的参考资料，也可供参加全国普通高校非计算机专业大学生计算机等级考试（CCT）的学生及计算机爱好者学习和参考。

教学思想：本课内容没有太过繁琐的语言，而是采用与多媒体充分融合的方式，并采用部分flash动画讲解遍历方法，生动、简洁、丰富地展现教学内容，教学思路清晰。

提高了教学效率和教学质量，使学生在单位时间内能够学到更多的知识，更大幅度地提高学生各方面的能力，从而使学生获得良好的发展。

课程设计思路：遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。

由于访问结点所做的操作依赖于具体的应用问题，所以我们对所讲解的问题分别举了一个容易和较难的例子，并配上一个难度适中的启发式的习题思考，在讲解过程中让学生充分理解，并学会运用不同的遍历方式解决问题，最后加上顺口溜式的总结，使学生对知识点更加融会贯通。

教学特色：1、教学思路清晰。

对于遍历的讲解是按照遍历概念、实例、动画演示、算法和总结的步骤进行的，效果较好。

2、在视频讲解中，语言生动而富于亲和力，表达多样，激发学生兴趣。

通过改变教学内容的展现形式，更具独到趣味，激发学生内外动力来实现。

3、在课件中，我们的幻灯片布局简洁，动画紧随讲解节奏的推进而随时跟进，生动形象，而又清晰明了地将所讲的知识点呈现出来，充分运用了现代多媒体教学方式的优点。

4、在PPT中我们插入了Flash动画，让遍历方法更加清晰明了，让学习者更容易理解与掌握。

长春建筑学院《数据结构》课程设计（论文）基于二叉树遍历系统设计与实现Binary tree traversal System Design and Implementation年级:学号:姓名:专业:指导老师:二零一三年十二月摘要针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。

在树型结构的应用中又以二叉树最为常用。

二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR 先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。

由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。

对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。

反之，任何二叉树都对应一个查找有序表的有效方法根据树的数学理论，对于算法分析的某些最有启发性的应用，是与给出用于计算各种类型中不同树的数目的公式有关的。

本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序，让读者对二叉树的理解有更好的效果。

关键词：二叉树；左子树；右子树AbstractIn many real world of complex data, such as the human society family, social organization, widespread game 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 express 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 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, 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, then 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 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 ordered 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 procedures, to allow readers to understand the two fork tree has a better effect.Keywords:Two tree; the left subtree; right subtree目录摘要 (I)ABSTRACT (Ⅱ)第1章绪论 ................................................................................................................ - 1 -1.1设计目的 (1)1.2设计内容 (1)1.3设计要求 (1)1.4设计思想 (2)1.5系统模块划分 (2)1.6主要功能模块设计 (2)第2章系统总体设计 (3)2.1基本理论 (3)2.2概要设计 (3)第3章详细设计 (4)3.1建立二叉树 (4)3.2二叉树的层次遍历和中序遍历 (4)3.3求二叉树的深度 (7)3.4将二叉树中所有结点的左右子树相互交换 (7)3.5求二叉树中叶子结点的数目 (9)第4章流程分析图 (11)4.1流程图 (11)4.2主要功能模块设计 (11)4.3模块设计 (12)4.4函数主要调用关系图 (13)第5章系统测试 (14)5.1调试分析 (14)5.2实验结果 (15)结论 (17)致谢 (18)参考文献 (18)第1章绪论引言：树型结构是一类重要的非线性数据结构，其中一树和二叉树最重要。

课程设计（数据结构）院、系专业姓名学号指导教师2010 年月日树的应用摘要：关键词：树；二叉树；转换；遍历；递归和非递归1．实验题目实现树与二叉树的转换的实现。

以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。

2．实验分析2．1总体分析2.1.1本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。

2.1.2本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。

2.1.3本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。

2.2具体分析2.2.1二叉树创建用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。

把下标为2*i+1 的值存入左孩子，为2*i+2的存入右孩子。

BiNode creat()，BiNode stree_creat(char *a,int k)。

2.2.2先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。

void PreOrder(BiNode root)。

2.2.3中序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。

void InOrder(BiNode root)。

2.2.4后序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。

（3）访问根结点；void PostOrder(BiNode root)。

2.2.5先序非递归算法BiNode根指针，若 BiNode!= NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。

问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取 BiNode的右子树的根指针？void F_PreOrder(BiNode root)2.2.6中序非递归算法BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。

目录1 问题描述 (1)2 需求分析 (1)3 概要设计 (1)3．1模块划分……………………………………………………….错误!未定义书签。

4 详细设计.................................................................................... (6)4．1主要模块流程图 (7)4．2 数据类型的定义 (8)4．3 主要模块的算法描述 (8)5 测试分析 (14)6 课程设计总结 (17)参考文献 (18)附录（源程序清单） (19)1 问题描述建立一棵二叉树；再以广义表表示法输出这棵二叉树；然后对该树进行先序、中序、后序遍历及层次遍历。

要求：（1）采用二叉链表存储二叉树；（2）先序、中序、后序遍历设计非递归算法。

2 需求分析二叉树一种数据结构，用于保存和处理树状的数据，比如家谱。

他的应用极为广泛，因为根据数据结构的理论，任何复杂的树够可以转换为二叉中并进行处理，二叉树在排序、查找、大规模数据索引方面有很多很多应用。

而且二叉树排序是简单算法排序中速度最快的。

在二叉树的一些应用中，常常要求在树中查找具有某种特征的节点，或者对树中全部节点逐一进行某种处理。

这就提出了遍历二叉树。

根据遍历的方向的选择，就有了前序遍历，中序遍历和后序遍历以及层次遍历二叉树。

因此掌握二叉树的各种遍历二叉树算法非常重要，而且高效的遍历算法能够节省很多成本。

3 概要设计3．1模块划分本程序包括七个模块：（1）主程序模块void main(){初始化；以广义表表示法输出；建立二叉树；非递归先序遍历二叉树并输出；非递归中序遍历二叉树并输出；非递归后序遍历二叉树并输出；层次遍历二叉树并输出；}（2）以广义表表示法输出——实现对二叉树的输出（3）二叉树建立模块——建立一个二叉树并对二叉树进行初始化（4）非递归先序遍历模块——实现对二叉树的递归先序遍历并输出（5）非递归中序遍历模块——实现对二叉树的递归中序遍历并输出（6）非递归后序遍历模块——实现对二叉树的递归后序遍历并输出（7）层次遍历模块——实现对二叉树的层次遍历并输出4 详细设计4．1主要模块流程图主流程图建立一棵二叉树以广义表表示法输出一棵二叉树非递归先序遍历非递归中序遍历非递归后序遍历层次遍历4．2数据类型的定义（1）二叉树的二叉链表存储类型typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;（2）栈类型的定义typedef struct SqStack/*定义一个顺序栈*/{BiTNode *base;BiTNode *top;int stacksize;}SqStack;void InitStack(SqStack *S)/*栈的初始化*/{S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));S->top=S->base;S->stacksize=STACK_INIT_SIZE;}void Push(SqStack *S,BiTNode e)/*入栈算法*/{if(S->top-S->base>=S->stacksize){S->base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*(S->top)=e;S->top++;}BiTNode Pop(SqStack *S)/*出栈算法*/{S->top --;return *S->top;}int StackEmpty(SqStack *S)/*判栈空*/{if(S->top == S->base )return 1;elsereturn 0;}4．3主要模块的算法描述（1）主函数void main(){BiTree Ta;int a=1;printf("请创建树\n");Ta=CreateBiTree();printf("广义表表示法输出二叉树\n");printfBTree(Ta);printf("\n");printf(" 请选择：\n");printf(" （1）先序遍历\n");printf(" （2）中序遍历\n");printf(" （3）后序遍历\n");printf(" （4）层次遍历\n");printf(" （0）结束程序\n");while(a){scanf("%d",&a);if(a==1){（2）建立二叉树BiTree CreateBiTree()/*以二叉链表的存储方式建立一棵二叉树*/ {char p;BiTree T;scanf("%c",&p);if(p=='#')T=NULL;else{T=(BiTNode *)malloc(sizeof(BiTNode));T->data=p;T->lchild=CreateBiTree();T->rchild=CreateBiTree();}return (T);}（3）用广义表表示法输出二叉树void printfbitree(t)/*用广义表表示法输出二叉树*/{if(t!=NULL){printf("%c",t->data);if(t->lchild!=NULL||t->rchild!=NULL){printf("(");printfbitree(t->lchild);if(t->rchild!=NULL)printf(",");printfbirree(t->rchild);printf(")");}}}（4）非递归先序遍历二叉树void PreOrder(BiTree T)/*非递归先序遍历二叉树*/ {SqStack S;BiTree p=T;InitStack(&S);if(p)Push(&S,*p);while(!StackEmpty(&S)){p=(BiTNode *)malloc(sizeof(BiTNode));*p=Pop(&S);printf("%c",p->data);if(p->rchild)Push(&S,*p->rchild);if(p->lchild)Push(&S,*p->lchild);}}（5）非递归中序遍历二叉树void InOrder(BiTree T)/* 非递归中序遍历二叉树*/ {SqStack S;BiTree p=T;InitStack(&S);while(p||!StackEmpty(&S)){if(p){Push(&S,*p);p=p->lchild;}else{p=(BiTNode *)malloc(sizeof(BiTNode));*p=Pop(&S);printf("%c",p->data);p=p->rchild;}}}（6）非递归后序遍历二叉树void PostOrder(BiTree T)/ *非递归后序遍历二叉树*/ SqStack S;BiTNode p, *l, *r;InitStack(&S);Push(&S, *T);while(!StackEmpty(&S)){p = Pop(&S);l = p.lchild;r = p.rchild;if (l == NULL && r == NULL){printf("%c", p.data);}else{p.lchild = NULL;p.rchild = NULL;Push(&S, p);if (r != NULL) Push(&S, *r);if (l != NULL) Push(&S, *l);}}}（7）层次遍历void LevelOrderTraverse(BiTree T) /*层序遍历*/ {BiTree Q[STACK_INIT_SIZE];int front=0,rear=0;BiTree p;if(T){ //根结点入队Q[rear]=T;rear=(rear+1)%STACK_INIT_SIZE;}while(front!=rear){p=Q[front]; //队头元素出队front=(front+1)%STACK_INIT_SIZE;printf("%c",p->data);if(p->lchild){ //左孩子不为空，入队Q[rear]=p->lchild;rear=(rear+1)%STACK_INIT_SIZE;}if(p->rchild){ //右孩子不为空，入队Q[rear]=p->rchild;rear=(rear+1)%STACK_INIT_SIZE;}}}5 测试分析6 课程设计总结通过这次课程设计使我充分的理解了从建立二叉树到输出二叉树再遍历二叉树的基本原理与算法，尤其是深刻的学习了二叉树遍历的非递归实现的算法。

实验报告课程：数据结构课程设计设计题目：二叉树遍历及应用学号:班级：软件11k1姓名: 南方小羊指导教师：刘军二叉树的遍历1、问题描述利用先序遍历建立一棵二叉树，并分别用前序、中序、后序遍历该二叉树2、节点形式Lchild data Rchild3、说明(1)输入数据：1，2，3，0，0，4，0，0，5，0，0其中“0”表示空子树。

(2)输出数据：先序：1，2，3，4，5中序：3，2，4，1，5后序：3，4，2，5，1二叉树的应用1、问题描述运用二叉树的遍历的算法，编写算法分别实现如下功能。

(1)求出二叉树中的结点的总数。

(2)求出二叉树中的叶子数目。

(3)求出二叉树的深度。

运用上题所建立的二叉树，求出其结点总数、叶子数目、深度，最后释放所有结点。

二叉树结点结构中包数据域（data），指针域（*lchild，*rchild）。

结点结构的代码如下：typedef struct tree{int data;struct tree *lchild,*rchild;}*bitree;本实例使用的是二叉树，首先建立头结点，并且保存数据，然后根据递归方法，分别建立其左右孩子结点，且左右孩子结点的指针域指向空。

先序递归遍历时，输出第一个根结点数据，然后分别遍历左子树再遍历右子树，中序遍历，先访问根结点的左子树输出数据，再输出根结点的数据，再访问右子树，后序遍历先访问根结点的右子树，再访问根结点，再访问左子树输出。

统计二叉树叶子的个数可以看成一个遍历问题，访问一个结点，判断该结点是否为叶子，如果是将叶子树加1，可以采用任何遍历实现，求二叉树的深度是假设根结点为第一层的结点，所有K层结点的左右孩子在K+1层，所以可以通过先序遍历计算二叉树中每个结点的层数，其中最大的就是二叉树的深度。

四、实验心得：树结构是数据结构课程的典型内容，而且综合使用了多种逻辑结构，具有代表性，可以锻炼个人编程能力。

在刚开始选题后，我感觉无从下手，一是因为没有实践经验，二是因为对数据结构课程的内容没有把握到位，然后在参考一些专业书籍并且学习了之前其他人的课程设计，才逐渐可以上手去自己做。

二叉树遍历数据结构课程设计以下是为大家整理的二叉树遍历数据结构课程设计的相关范文，本文关键词为二叉,遍历,数据结构,课程,设计,吉林,工程技术,师范学院,，您可以从右上方搜索框检索更多相关文章，如果您觉得有用，请继续关注我们并推荐给您的好友，您可以在综合文库中查看更多范文。

吉林工程技术师范学院《数据结构》课程设计报告书设计题目：二叉树遍历专业：软件班级：xxx学生姓名：xxx学号：xxx指导教师：xxx20XX年12月信息工程学院目录摘要................................................................................I第一章问题定义.........................................................1第二章设计思路.........................................................2第三章数据结构定义.................................................3第四章系统功能模块设计.........................................4第五章运行与调试.....................................................6总结..........................................................................10附录............................................................................I1程序清单...............................................................I2参考资料.. (x)摘要本课设主要实现对二叉树进行的三种次序遍历，输出三种遍历次序的遍历序列。

数据结构课程设计报告_遍历⼆叉树XXXX⼤学《数据结构》课程设计报告课题名称: 遍历⼆叉树系（院）:专业:班级:组员姓名:学号:指导教师:开课时间: 学年学期摘要树结构在客观世界中⼴泛存在, 如⼈类社会的族谱和各种社会组织机构都可⽤树形象表⽰. 树在计算机领域中也得到⼴泛应⽤,如在编译源程序时, 可⽤树表⽰源程序的语法结构. ⼜如在数据库系统中, 树型结构也是信息的重要组织形式之⼀. ⼀切具有层次关系的问题都可⽤树来描述.针对这样的问题, 我选择了⼆叉树的遍历作为我的课程设计主题, 编写程序, 实现对⼆叉树的遍历. 在本次课程设计中, ⼆叉树的建⽴使⽤了递归算法；在前序、中序和后续遍历的算法中则同时使⽤了递归与⾮递归的算法, 即在这些遍历算法的实现中使⽤了栈结构与队列结构, 提供了6种不同的遍历⽅式, 供使⽤者选择. 同时, 该程序具有输出层序遍历的功能, 层序遍历模块使⽤了⾮递归算法. 该程序基本实现了对⼆叉树的遍历, 对于递归与⾮递归算法, 我们应从实际应⽤中体验这些算法的优越性.关键词: 层次关系, ⼆叉树建⽴, 递归与⾮递归, 遍历, 栈, 队列⽬录⼀、问题描述 (1)⼆、需求分析 (1)2.1主功能模块 (1)2.2创建树模块 (1)2.3遍历树模块 (1)三、概要设计 (2)3.1主界⾯设计思想流程图 (2)3.2. 创建⼆叉树 (2)3.2.1⼆叉树创建的思想 (2)3.2.2⼆叉树创建的算法流程图 (2)3.3.先序递归遍历 (3)3.3.1先序递归遍历思想 (3)3.3.2先序递归遍历的算法流程图 (3)3.4.中序递归遍历 (3)3.4.1中序递归遍历思想 (3)3.4.2中序递归遍历的算法流程图 (4) 3.5.后序递归遍历 (4)3.5.1后序递归遍历思想 (4)3.5.2后序递归遍历的算法流程图 (5) 3.6.先序⾮递归遍历 (5)3.6.1先序⾮递归遍历思想 (5)3.6.2先序⾮递归遍历的算法流程图 (6) 3.7.中序⾮递归遍历 (6)3.7.1中序⾮递归遍历思想 (6)3.7.2中序⾮递归遍历的算法流程图 (7) 3.8.后序⾮递归遍历 (7)3.8.1后序⾮递归遍历思想 (7)3.8.2后序⾮递归遍历的算法流程图 (8) 3.9.层序⾮递归遍历 (8)3.9.1层序⾮递归遍历思想 (8)3.9.2层序⾮递归遍历的算法流程图 (9)四、详细设计 (10)4.1界⾯设计 (10)4.2.详细代码分析 (11)4.2.1主模块 (11)4.2.2创建树模块 (12)4.2.3遍历树模块 (13)五、调试分析 (13)5.1.调试结果 (13)5.1.1实验数据 (13)5.1.2创建树界⾯ (14)5.1.3输出结果界⾯ (14)5.2.算法分析 (16)5.2.1时间复杂度 (16)5.2.2空间复杂度 (16)5.3.程序的不⾜ (16)5.3.1程序不⾜之处 (16)六、⼼得体会 (17)七、参考⽂献 (17)⼀、问题描述建⽴⼆叉树, 层序、先序、中序、后序遍历.(⽤递归或⾮递归的⽅法都可以)要求能够输⼊树的各个结点, 并能够输出⽤不同⽅法遍历的遍历序列；分别建⽴⼆叉树存储结构的的输⼊函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数.⼆、需求分析在现实世界层次化的数据模型中, 数据与数据之间的关系纷繁复杂. 其中很多关系⽆法使⽤简单的线性结构表⽰清楚, ⽐如祖先与后代的关系、整体与部分的关系等. 于是⼈们借鉴⾃然界中树的形象创造了⼀种强⼤的⾮线性结构——树. 树形结构的具体形式有很多种, 其中最常⽤的就是⼆叉树. ⽽⼆叉树的多层次遍历遍历则是⼆叉树的重要内容.本程序⽤Microsoft Visual C++ 6.0编写, 可以实现对⼆叉树的创建、采⽤递归和⾮递归等两种⽅式先序、中序、后序进⾏遍历.2.1主功能模块通过合理的界⾯设计, 根据提⽰信息, 使⽤者可以⽅便快捷地运⾏本程序来完成创建、遍历⼆叉树等操作. 界⾯美观, ⼈性化, 程序智能, 安全性⾼.2.2创建树模块当进⼊程序运⾏界⾯后, 根据提⽰输⼊需要建⽴的⼆叉树, 按照先序次序输⼊各个结点的值, 完成⼆叉树的建⽴.2.3遍历树模块实现对该⼆叉树的先序递归遍历、先序⾮递归遍历、中序递归遍历、中序⾮递归遍历、后序递归遍历、后序⾮递归遍历、层序⾮递归遍历等⽅式的遍历操作, 并输出各遍历序列.三、概要设计3.1主界⾯设计思想流程图3.2. 创建⼆叉树3.2.1⼆叉树创建的思想(1)定义⼆叉树结点值的类型为字符型.(2)结点个数不超过10个.(3)按先序次序输⼊, 构造⼆叉链表表⽰的⼆叉树T, 空格表⽰空树. 相关函数如下:void CreateBiTree(BiTree &T)3.2.2⼆叉树创建的算法流程图3.3.先序递归遍历3.3.1先序递归遍历思想若⼆叉树为空, 则空操作；否则(1)访问根结点；(2)先序遍历左⼦树；(3)先序遍历右⼦树. 相关函数如下: void PreOrderTraverse(BiTree T) 3.3.2先序递归遍历的算法流程图3.4.中序递归遍历3.4.1中序递归遍历思想若⼆叉树为空, 则空操作；否则(1)中序遍历左⼦树；(2)访问根结点；(3)中序遍历右⼦树. 相关函数如下: void InOrderTraverse(BiTree T) 3.4.2中序递归遍历的算法流程图3.5.后序递归遍历3.5.1后序递归遍历思想若⼆叉树为空, 则空操作；否则(1)后序遍历左⼦树；(2)后序遍历右⼦树；(3)访问根结点. 相关函数如下: void PostOrderTraverse(BiTree T)3.6.先序⾮递归遍历3.6.1先序⾮递归遍历思想(1)访问结点的数据域；(2)指针指向p的左孩⼦结点；(3)从栈中弹出栈顶元素；(4)指针指向p的右孩⼦结点. 相关函数如下: void NRPreOrder(BiTree bt)3.7.中序⾮递归遍历3.7.1中序⾮递归遍历思想(1)指针指向p的左孩⼦结点；(2)从栈中弹出栈顶元素；(3)访问结点的数据域；(4)指针指向p的右孩⼦结点. 相关函数如下: void NRInOrder(BiTree bt)3.7.2中序⾮递归遍历的算法流程图3.8.后序⾮递归遍历3.8.1后序⾮递归遍历思想若⼆叉树为空, 则空操作；否则引⼊栈和标记模拟递归⼯作栈, 初始时栈为空. 相关函数如下: void NRPostOrder(BiTree bt);3.8.2后序⾮递归遍历的算法流程图3.9.层序⾮递归遍历3.9.1层序⾮递归遍历思想(1)访问该元素所指结点.(2)若该元素所指结点的左右孩⼦结点⾮空, 则该元素所指结点的左孩⼦指针和右孩⼦指针顺序⼊队. 相关函数如下: void LevelOrderTraverse(BiTree T)3.9.2层序⾮递归遍历的算法流程图四、详细设计4.1界⾯设计图4-1 系统运⾏主界⾯图4-2 创建⼆叉树界⾯图4-3 ⼆叉树递归遍历界⾯4.2.详细代码分析4.2.1主模块本模块定义了系统运⾏主界⾯的相关内容和相关操作函数, 源代码如下: void main(){BiTree T;T=NULL;int select;//cout<<"请按先序次序输⼊各结点的值, 以空格表⽰空树(输⼊时可连续输⼊):"< while(1){cout<<"\n\n请选择要执⾏的操作:\n";cout<<"1.创建⼆叉树\n";cout<<"2.⼆叉树的递归遍历算法（前、中、后）\n";cout<<"3.⼆叉树的层次遍历算法\n";cout<<"4.⼆叉树的⾮递归遍历算法（前、中、后）\n";cout<<"0.退出\n";cin>>select;switch(select){case 0:return;case 1:cout<<"请按先序次序输⼊各结点的值, 以空格表⽰空树(输⼊时可连续输⼊):"< CreateBiTree(T);break;case 2:if(!T) cout<<"未建⽴树, 请先建树！";else{cout<<"\n先序遍历:\n";PreOrderTraverse(T);cout<<"\n中序遍历:\n";InOrderTraverse(T);cout<<"\n后序遍历:\n";PostOrderTraverse(T);}break;case 3:cout<<"\n层序遍历:\n";LevelOrderTraverse(T);break;case 4:if(!T) cout<<"未建⽴树, 请先建树！";else{cout<<"\n先序遍历:\n";NRPreOrder(T);cout<<"\n中序遍历:\n";NRInOrder(T);cout<<"\n后序遍历:\n";NRPostOrder(T);}break;default:cout<<"请确认选择项:\n";}//end switch}//end while}4.2.2创建树模块源代码如下:void CreateBiTree(BiTree &T){//按先序次序输⼊, 构造⼆叉链表表⽰的⼆叉树T, 空格表⽰空树// if(T) return;char ch;ch=getchar(); //不能⽤cin来输⼊, 在cin中不能识别空格.if(ch==' ') T=NULL;else{if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}4.2.3遍历树模块本模块包括了各种遍历⼆叉树的函数, 源代码如下:void PreOrderTraverse(BiTree T) //⼆叉树的先序遍历(递归)成员函数声明void InOrderTraverse(BiTree T) //⼆叉树的中序遍历(递归)成员函数声明void PostOrderTraverse(BiTree T) //⼆叉树的后序遍历(递归)成员函数声明void LevelOrderTraverse(BiTree T) // ⼆叉树的层序遍历(⾮递归)成员函数声明void NRPreOrder(BiTree bt) // ⼆叉树的先序遍历(⾮递归)成员函数声明void NRInOrder(BiTree bt) //⼆叉树的中序遍历(⾮递归)成员函数声明void NRPostOrder(BiTree bt) //⼆叉树的后序遍历(⾮递归)成员函数声明五、调试分析5.1.调试结果5.1.1实验数据这棵树是随机画的, 由数据结构知识, 按照先序次序输⼊各个节点的值为: ABD###CEG###F#H##(此处#代表空格). 在程序中输⼊这些节点, 创建树, 如下图:5.1.2创建树界⾯图5-1 创建树界⾯5.1.3输出结果界⾯输⼊2, 输出该⼆叉树递归遍历算法的遍历结果, 结果如下:输⼊3, 输出该⼆叉树层序遍历算法的遍历结果, 结果如下:输⼊4, 输出该⼆叉树⾮递归遍历算法的遍历结果, 结果如下:。

##大学数据结构课程设计报告题目：二叉树和树的遍历院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 2011-6-21至2011-6-25指导教师:2010—2011年度第 2 学期一、需求分析1.问题描述：进行二叉树和树的各种遍历，包括递归和非递归。

2.基本功能二叉树前序递归遍历、二叉树中序递归遍历、二叉树后序递归遍历、二叉树前序非递归遍历、二叉树中序非递归遍历、二叉树后序非递归遍历、二叉树层次非递归遍历树先根递归遍历、树后根递归遍历、树先根非递归遍历、树后根非递归遍历、树层次非递归遍历，可循环执行直到按退出键。

3.输入输出字符串形式二、概要设计1.设计思路：在递归遍历二叉树时，主要看遍历的根的先后，可根据遍历根，遍历左子树和遍历右子树的顺序不同来实现二叉树的先序，中序，后序递归遍历，二叉树的先序和中序非递归则用到了栈，一般都是先根进栈然后左孩子进栈，二叉树的后序遍历则用到了队列，并用tag 数组值0、1来标记二叉树结点的左右，树的先根非递归和后序非递归则参考了二叉树的先序和中序非递归遍历，也用到了栈，它的层次遍历则用到了队列。

2.数据结构设计：//二叉树的结点结构typedef struct bitnode{char data;struct bitnode *lchild,*rchild;}bitnode,* bitree;//二叉树的栈的结构typedef struct{bitree *base;bitree *top;int stacksize;}sqstack;为二叉树的先序和中序非递归提供栈，保存已经访问过的结点信息。

//二叉树后序非递归的栈的结构typedef struct node1{bitree data[30]; //默认30个元素，这里需要一个辅助堆栈！！！int top;}stack;top能够保存结点是左还是右孩子，该栈为后序遍历提供保存结点信息。

//二叉树的队列结点结构typedef struct qnode{bitree data;struct qnode *next;}qnode,*queueptr;//二叉树的队列结构typedef struct{queueptr front;queueptr rear;}linkqueue;该队列能为二叉树层序遍历提供先进先出的数据访问条件//树的结点结构typedef struct csnode{char data;struct csnode *firstchild,*nextsibling;}csnode,*cstree;//树的栈的结构typedef struct{cstree *base;cstree *top;int stacksize;}sqstack1;为树的前根和后根非递归遍历提供保存已经访问过的数据信息//树的队列结点结构typedef struct qnode1{cstree data;struct qnode1 *next;}qnode1,*queueptr1;//树的队列结构typedef struct{queueptr1 front;queueptr1 rear;}linkqueue1;为树的层次遍历提供条件3.软件结构设计：cout<<"1:进行二叉树的操作2:进行树的操作3:退出"<<endl;这是初始界面。

目录1、需求分析 (1)2、概要设计 (2)2.1 功能设计 (2)2.2 算法流程图 (3)3、详细设计 (4)3.1 界面设计.......................... 错误!未定义书签。

3.2 详细代码分析 (4)3.3 调试分析 (11)3.3.1调试结果 (14)3.3.2算法分析 (14)4、总结 (14)参考文献 (15)1、需求分析数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。

数据结构只要研究四个方面的问题：(1)数据的逻辑结构，即数据之间的逻辑关系；(2)数据的物理结构，即数据在计算机内的存储方式；(3)对数据的加工，即基于某种存储方式的操作算法；(4)算法的分析；即评价算法的优劣。

本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。

本程序用VC++6.0编写，可以实现各种二叉树的遍历。

包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。

根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，以及求二叉树的叶子个数等。

其中二叉树的结点用字符表示。

(1) 先创建二叉树：构建一个字符二叉树实例，并横向打印该二叉树。

(2)设计算法:用递归算法和非递归算法中序遍历和后序遍历这个二叉树。

(3)加入求二叉树的深度和二叉树的叶子数二叉树的结点总数等一些简单的算法。

(4) 设计main()函数调用以上步骤实现相关功能。

2、概要设计2.1 功能设计（1）CreateBSTNode(char *s)此函数的功能是构建一个二叉树。

（2）DispBTree(BSTNode *b)此函数的功能是打印该二叉树。

（3）BSTNodeDepth(*b) 此函数的功能是求该二叉树高度。

二叉树的遍历教案教学设计教案教学设计：二叉树的遍历一、教学目标：1. 了解二叉树的遍历方式：前序遍历、中序遍历和后序遍历。

2. 能够使用递归和非递归两种方法实现二叉树的遍历。

3. 能够分析和比较不同遍历方式的时间复杂度和空间复杂度。

二、教学内容：1. 二叉树的遍历概念及分类。

2. 递归遍历算法的原理及实现。

3. 非递归遍历算法的原理及实现。

4. 比较不同遍历方式的时间复杂度和空间复杂度。

三、教学重点：1. 能够理解二叉树的遍历分类及其特点。

2. 能够使用递归和非递归两种方法实现二叉树的遍历。

四、教学难点：1. 非递归遍历算法的实现。

2. 比较不同遍历方式的时间复杂度和空间复杂度。

五、教学过程：1. 导入新知识，激发学生兴趣（5分钟）教师通过展示一棵二叉树的图片引入二叉树的遍历概念，并让学生猜测遍历的意义。

2. 介绍二叉树的遍历分类及特点（10分钟）教师介绍二叉树的遍历分类：前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根），并讲解每种遍历方式的特点。

3. 介绍递归遍历算法的原理及实现（15分钟）教师通过演示前序遍历的递归算法实现，介绍递归遍历的原理和递归函数的编写，让学生理解递归遍历的思路。

4. 演示递归遍历算法的应用（15分钟）教师在白板上画一棵二叉树，演示如何使用递归算法实现不同的遍历方式，并让学生跟随演示进行练习。

5. 介绍非递归遍历算法的原理及实现（15分钟）教师介绍非递归遍历算法的思路，包括使用栈数据结构进行遍历的原理及实现。

6. 演示非递归遍历算法的应用（15分钟）教师在白板上画一棵二叉树，演示如何使用非递归算法实现不同的遍历方式，并让学生跟随演示进行练习。

7. 比较不同遍历方式的时间复杂度和空间复杂度（10分钟）教师比较不同遍历方式的时间复杂度和空间复杂度，让学生了解不同的遍历方式在不同场景下的优劣。

8. 小结与作业布置（5分钟）教师对本节课进行小结，并布置作业：编写一个程序，实现二叉树的遍历，并分析所用遍历方式的时间复杂度和空间复杂度。

目录一．选题背景 (1)二．问题描述 (1)三．概要设计 (2)3.1.创建二叉树 (2)3.2.二叉树的非递归前序遍历示意图 (2)3.3.二叉树的非递归中序遍历示意图 (2)3.4.二叉树的后序非递归遍历示意图 (3)四．详细设计 (4)4.1创建二叉树 (4)4.2二叉树的非递归前序遍历算法 (4)4.3二叉树的非递归中序遍历算法 (5)4.4二叉树的非递归后序遍历算法 (5)五．测试数据与分析 (7)六．源代码 (7)总结 (11)参考文献: (12)一．选题背景二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。

二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。

因此每个结点为由二叉树的定义知可把其遍历设计成递归算法。

共有前序遍历、中序遍历、后序遍历。

可先用这三种遍历输出二叉树的结点。

然而所有递归算法都可以借助堆栈转换成为非递归算法。

以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。

特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。

因此可借助堆栈实现二叉树的非递归遍历。

将输出结果与递归结果比较来检验正确性。

二．问题描述对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。

画出搜索顺序示意图。

三．概要设计3.1.创建二叉树3.2.二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图图3.3二叉树中序遍历示意图3.4.二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图四．详细设计4.1创建二叉树(1)定义二叉树结点值的类型为字符型。

#define m 50typedef struct Node{char data;struct Node *Lchild;struct Node *Rchild;}bitnode,*bitree;typedef struct(2)结点个数不超过50个。

内蒙古科技大学本科生课程设计论文题目：数据结构课程设计——二叉树遍历及应用学生姓名：学号：专业：计算机科学与技术班级：指导教师：兰孝文2020年 1 月 3 日内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目二叉树的遍历和应用指导教师兰孝文时间2019.12.30——2020.1.3一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。

二叉树的遍历和应用以二叉链表表示二叉树，在此基础上实现对二叉树的遍历和应用。

要求设计类（或类模板）来描述二叉树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：❖创建二叉树❖输出二叉树❖二叉树的先序、中序、后序遍历❖二叉树的按层遍历❖统计二叉树的叶子结点、计算二叉树的深度并设计主函数测试该类（或类模板）。

三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（1天）系统的开发与测试（2天）编写课程设计说明书和验收（1天）五、评分标准1. 根据平时上机考勤、表现和进度，教师将每天点名和检查2. 根据课程设计完成情况，必须有可运行的软件。

3. 根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。

4. 根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社20132．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社 2010 3.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社 2012目录1. 功能设计 (1)（1）创建二叉树 (1)（2）先序递归遍历 (1)（3）中序递归遍历 (1)（4）后序递归遍历 (1)2. 算法流程图 (2)（1）创建二叉树 (2)（2）先序递归遍历 (3)（3）中序递归遍历 (4)（4）后序递归遍历 (5)3．问题描述 (6)4. 详细设计 (7)（1）设计思想 (7)（2）设计表示 (7)（3）函数接口说明: (8)（4）函数调用关系如图所示： (8)（5）实现注释 (9)5. 运行结果截图 (10)6. 总结 (12)附录 (13)1.功能设计（1）创建二叉树利用二叉树模板类，创建二叉树时产生类模板，调用类的构造函数来创建，修改二叉树的结构时，可以调用赋值语句直接把广义表转换成二叉树。

淮阴工学院实践报告数据结构课程设计设计题目：二叉树遍历系别：计算机工程学院专业：软件工程班级：软件1111学生姓名: 周淼学号: 1111315217起止日期: 2012年12月24日~2012年12月30日指导教师：寇海洲摘要：现代社会生活中，计算机扮演着重要角色，而随着计算机运行速度的不断加快，对数据的处理能力也日益增强，因此，程序所涉及的数据成爆发式增长。

随之而来的问题就是如何科学有效的对数据进行操作，使得计算机的时间和空间利用率最高。

针对这样的问题，我选择了二叉树对数据的各种操作作为我的课程设计主题，希望通过课程设计来提高对数据的处理能力，促进对数据结构课程的理解，在日后面向对象的程序设计中科学的规划数据结构。

在本次课程设计中，二叉树的建立使用了递归算法，遍历则同时使用了递归与非递归的算法，同时，在遍历算法的实现中使用了栈结构与队列结构，这大大方便了二叉树的遍历。

在前序、中序、后续遍历算法中，分别实现了递归与非递归算法，从实际应用中体验了递归这一算法的优越性。

关键词：二叉树建立，递归与非递归，遍历，栈，队列编号：47淮阴工学院软件工程专业数据结构课程设计答辩记录课题名称：二叉树的算法班级软件1111 学号1111315217 姓名周淼记录人：寇海洲2012 年12 月28日目录1需求分析 (6)1.1二叉树与树结构 (6)1.2面向对象的程序设计 (6)1.3二叉树遍历的应用 (6)1.4软件运行环境：Visual C++ 6.0版本 (6)2概要设计 (7)2.1 总体功能结构 (7)2.2数据结构部分设计 (7)2.2.1结点结构 (7)2.2.2 二叉树结构 (8)3详细设计 (13)3.1建立二叉树 (13)3.1.1功能描述 (13)3.1.2算法原理 (13)3.1.3 具体程序 (13)3.2 前序遍历 (14)3.2.1 功能原理 (14)3.2.2 算法原理 (14)3.2.3 具体程序 (14)3.3 中序遍历 (15)3.3.1 功能原理 (15)3.3.2 算法原理 (15)3.3.3 具体程序 (15)3.4 后序遍历 (16)3.4.1功能原理 (16)3.4.2 算法原理 (16)3.4.3 具体程序 (17)3.5层次序非递归遍历 (18)3.5.1 功能原理 (18)3.5.2 算法原理 (18)3.5.3 具体程序 (18)3.6 栈结构 (19)3.6.1 功能原理 (19)3.6.2算法原理 (19)3.6.3 具体程序 (19)3.7 队列结构 (20)3.7.1 功能原理 (20)3.7.2 算法原理 (20)3.7.3 具体程序 (20)4调试与操作说明 (21)致谢 (24)参考文献 (25)附录： (26)1需求分析1.1二叉树与树结构树结构的是建立在数据逻辑结构基础上的数据结构类型，二叉树则是树结构中最常见和使用最多的类型。

《数据结构》课程设计报告设计题目：二叉树的遍历姓名：陈雷学号： 7专业：运算机科学与技术院系：运算机科学与技术班级： 1002指导教师：吴克力2012年 3 月1日摘要：本文主要说明如何实现二叉树的遍历。

这次二叉树的遍历基于二叉树的二叉链表存储结构。

遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。

其中前序遍历和后续遍历采用非递归算法实现。

编程环境为VC++，除遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，和最近一路先人（LCA）问题的算法。

关键字：二叉树遍历非递归C++ LCAAbstract: This paper mainly describes how to implement binary tree traversal. The binary tree traversal is based on binary tree binary storage structure. Traversal method includes: preorder traversal,inorder traversal, postorder traversal, levelorder traversal. The former preorder traversal and postorder use of non - recursive algorithm. Programming environment is VC + +, in addition to traversal operation, also increased for solving the binary tree depth 、summary points and each layer of nodes, as well as the most recent common ancestor ( LCA ) algorithm.Keywords: binary tree traversal non-recursive C++ LCA目录一、问题描述 (4)问题描述：创建二叉树并遍历 (4)大体要求： (4)二、需求分析 (4)三、概要设计 (4)1．创建二叉树 (4)2．二叉树的非递归前序遍历示用意 (4)3．二叉树的后序非递归遍历示用意 (5)四、数据结构设计 (5)1．二叉树结点数据类型概念为： (5)2．二叉树数据类型概念为： (5)五、算法设计 (6)一、创建二叉树 (6)2、非递归前序遍历 (7)3、非递归后序遍历 (7)4、求二叉树的高度 (8)5、求二叉树每一层的结点数 (8)6、求两节点最近一路先人 (9)6、算法流程图 (10)六、程序测试与实现 (10)一、函数之间的挪用关系 (11)二、主程序 (11)3、测试数据 (12)4、测试结果 (12)七、调试分析 (14)八、碰到的问题及解决办法 (14)九、心得体会 (14)十、参考文献 (15)一、问题描述问题描述：创建二叉树并遍历大体要求：1、别离运用非递归的方式完成对二叉树的先序和后序遍历2、输出二叉树的高度3、输出每一层的结点数4、查找结点P 和结点Q的最近一路先人二、需求分析1．本程序的功能包括二叉树的成立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近一路先人，二叉树的打印。