二叉树的遍历

1、 数据结构 课程设计说明书题目： 二叉树的遍历 学生姓名： 学 号： 院 （系）： 专 业： 指导教师： 目 录1 选题背景12 概念设计12.1 问题提出 12.2 遍历方法22.3 算法框架23 详细设计24 调试分析74.1 结果显示74.2 算法分析105 总结10参考文献附录1 选题背景数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业基础课程，掌握好数据结构的知识将直接关系到后续专业课程的学习。数据结构只要研究四个方面的问题：(1)数据的逻辑结构，即数据之间的逻辑关系；(2)数据的物理结构，即数据在计算机内的存储方式；(3)对数据的加工，即基于某种存储方式的操作算

2、法；(4)算法的分析；即评价算法的优劣。本实验是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。本程序用VC+6.0编写，可以实现各种二叉树的遍历1。包括先序遍历、中序遍历、后序遍历的递归算法，先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。根据题目知，程序主要是根据给定二叉树的先序遍历结果，构造出二叉树并输出按中，后序遍历的结果，(1)先创建二叉树：按先序次序输入，构造二叉链表表示的二叉树。(2)设计算法：先序遍历,中序遍历,后序遍历.在做到层序遍历时，应注意算法如下：根结点入队，队头元素出队，左孩子不为空入队右孩子不为空入

3、队的顺序进行。(3)设计main()函数调用以上步骤实现相关功能。2 概念设计 1.1 问题提出 二叉树的遍历2本质上其实就是入栈出栈的问题，递归算法简单且容易理解，但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节，但是乍一看不想递归算法那么好理解，各有各的好处吧。接下来根据下图进行二叉树的遍历实现。图1-1，基本二叉树 1.2 遍历方法 （1）先序遍历：先序遍历是先输出根节点，再输出左子树，最后输出右子树。 （2）中序遍历：中序遍历是先输出左子树，再输出根节点，最后输出右子树。 （3）后序遍历：后序遍历是先输出左子树，再输出右子树，最后输出根节点。 1.3 算法框架 如下图所示：

4、图2-1，二叉树遍历算法框架3 过程设计 （1）创建树3,以先序序列建立树void CreateTree(Tree&t) char ch; scanf(%c,&ch); if ( ch = # ) t = NULL; else t = (Tree)malloc(sizeof(TreeNode); if ( !t ) printf(分配内存出错！); return ; t-data = ch; CreateTree(t-lchild); CreateTree(t-rchild); （2）递归先序遍历void PreOrder(Tree t) if ( t ) printf(%c,t-data);

5、 PreOrder(t-lchild); PreOrder(t-rchild); （3） 非递归先序遍历void PreOrder1(Tree t) Tree p = t; Sqstack s; InitStack(s); while ( p | !StackEmpty(s) ) if ( p ) printf(%c,p-data); Push(s,p); p = p-lchild; else Pop(s,p); p = p-rchild; （4） 递归中序遍历void InOrder(Tree t) if ( t ) InOrder(t-lchild); printf(%c,t-data);

6、 InOrder(t-rchild); （5） 非递归中序遍历void InOrder1(Tree t) Tree p = t; Sqstack s; InitStack(s); while ( p | !StackEmpty(s) ) if ( p ) Push(s,p); p = p-lchild; else Pop(s,p); printf(%c,p-data); p = p-rchild; （6） 递归后序遍历void PostOrder(Tree t) if ( t ) PostOrder(t-lchild); PostOrder(t-rchild); printf(%c,t-dat

7、a); （7） 非递归后序遍历void PostOrder1(Tree t) t-isOut = 0; Tree p = t; Sqstack s; InitStack(s); while ( p | !StackEmpty(s) ) if ( p ) if ( p-isOut ) /左右子树都已输出，则该节点也输出 Pop(s,p); printf(%c,p-data); if (!StackEmpty(s) GetTop(s,p); /得到弹出节点元素的父节点 else p = NULL; else if ( (p-lchild) & (p-lchild-isOut = 1) ) p-is

8、Out = 1; p = p-rchild; else Push(s,p); p = p-lchild; else if (!StackEmpty(s) GetTop(s,p); else p = NULL; if ( p-rchild ) p = p-rchild; else Pop(s,p); printf(%c,p-data); p-isOut = 1; if (!StackEmpty(s) GetTop(s,p); if ( p-lchild = NULL ) p-isOut = 1; /右子树已输出，将父节点isOut置 else p = NULL; 4 调试分析 4.1 结果显示

9、（1） 系统界面图4-1，系统开始页面 （2）创建二叉树图4-2，创建二叉树 （3）非递归先序遍历算法图4-3，非递归中序遍历算法结果 （4）递归先序遍历算法图4-4，递归先序遍历算法结果 （5）递归中序遍历算法图4-5，非递归中序遍历算法结果 （6）非递归中序遍历算法图4-6，递归中序遍历算法结果 （7）递归后序遍历算法图4-7，非递归后序遍历算法结果 （8）非递归后序遍历算法图4-8，非递归后序遍历算法结果 4.2 算法分析 本程序按递归遍历所耗费的时间复杂度为O（n），其所耗费的空间复杂度也为（n）。5 总结 虽然都说“程序数据结构算法”，但我在学习运用数据结构编程之前，并没能深刻体会到

10、这一点，直到这次课设实践。在这次实验中我终于克服了编程的障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了！同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！ 在这次实验中，我对参数的调用也进行了很多种尝试，已差不多经能够选择合适的参数形式来实现函数之间的数据传输交互了。这次实验中我也出现过一些比较严重的错误。在用链表结构编写程序时我错误的把一个定义的一级指针用二级指针来做，结果出现了一些难以想象的后果。这是我对基本概念理解的模糊不清造成的。后来在同学的指点下我意识到自己的错误。不过收获也很不少，至少我又掌握了指针的应用。 总之，我会继续我

11、的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。参 考 文 献1秦锋.数据结构(C语言版).合肥:中国科学技术大学出版社,20072温秀梅.VisualC语言面象对象程序设计教程与实验.北京：清华大学出版社20063何钦铭.C语言程序设计.北京:高等教育出版社，2008附录#include#include#define STACKINITSIZE 100#define STACKINCREASESIZE 20typedef char ElemType;/树结构typedef struct treeElemType data;struct tree*lchild;struc

12、t tree*rchild;unsigned int isOut;/专为后序遍历设置的，为不需要被输出，为需要被输出TreeNode,*Tree;/栈结构typedef struct stackTree*base;Tree*top;int stacksize;Sqstack;/*栈的操作声明*/初始化栈void InitStack(Sqstack&s);/元素入栈void Push(Sqstack&s,Tree e);/获得栈顶元素void GetTop(Sqstack s,Tree&e);/弹出栈顶元素void Pop(Sqstack&s,Tree&e);/判断栈是否为空，为空返回，否则返回

13、int StackEmpty(Sqstack s);/*栈的操作声明*/*树的操作声明*/创建树,以先序序列建立树void CreateTree(Tree&t);/递归先序遍历void PreOrder(Tree t);/非递归先序遍历void PreOrder1(Tree t);/递归中序遍历void InOrder(Tree t);/非递归中序遍历void InOrder1(Tree t);/递归后序遍历void PostOrder(Tree t);/非递归后序遍历void PostOrder1(Tree t);/*树的操作声明*/int main()Tree T;T=NULL;int n

14、=8;while(n!=0)printf(n);printf(二叉树的遍历n);printf(1.递归-创建二叉链表n);printf(2.非递归先序遍历二叉树n);printf(3.递归先序遍历二叉树n);printf(4.非递归中序遍历二叉树n);printf(5.递归中序遍历二叉树n);printf(6.非递归后序遍历二叉树n);printf(7.递归后序遍历二叉树n);printf(0.退出系统n);printf(请选择:n);scanf(%d,&n);getchar();switch(n)case 1:printf(请输入结点的先序序列创建二叉树:#表示空:n);CreateTree

15、(T);printf(n);break;case 2:printf(非递归先序遍历二叉树:n);PreOrder1(T);printf(n);break;case 3:printf(递归先序遍历二叉树：n);PreOrder(T);printf(n);break;case 4:printf(非递归中序遍历二叉树:n);InOrder1(T);printf(n);break;case 5:printf(递归中序遍历二叉树:n);InOrder(T);printf(n);break;case 6:printf(非递归后序遍历二叉树：n);PostOrder1(T);printf(n);break;

16、case 7:printf(递归后序遍历二叉树:);PostOrder(T);break;case 0:break;default:printf(输入错误！);break;/*栈的操作定义*/初始化栈void InitStack(Sqstack&s)s.base=(Tree*)malloc(STACKINITSIZE*sizeof(Tree);if(!s.base)printf(InitStack内存分配出错n);s.top=s.base;s.stacksize=STACKINITSIZE;/元素入栈void Push(Sqstack&s,Tree e)if(s.top-s.base=s.st

17、acksize)s.base=(Tree*)realloc(s.base,(s.stacksize+STACKINCREASESIZE)*sizeof(Tree);if(!s.base)printf(Push内存分配出错n);return;s.top=s.base+s.stacksize;s.stacksize+=STACKINCREASESIZE;e-isOut=0;*s.top+=e;/获得栈顶元素void GetTop(Sqstack s,Tree&e)e=*(s.top-1);/弹出栈顶元素void Pop(Sqstack&s,Tree&e)if(s.top=s.base)printf

18、(栈为空n);return;e=*(-s.top);/判断栈是否为空，为空返回，否则返回int StackEmpty(Sqstack s)if(s.top=s.base)return 1;return 0;/*栈的操作定义*/*树的操作定义*/创建树,以先序序列建立树void CreateTree(Tree&t)char ch;scanf(%c,&ch);if(ch=#)t=NULL;elset=(Tree)malloc(sizeof(TreeNode);if(!t)printf(分配内存出错！);return;t-data=ch;CreateTree(t-lchild);CreateTree

19、(t-rchild);/递归先序遍历void PreOrder(Tree t)if(t)printf(%c,t-data);PreOrder(t-lchild);PreOrder(t-rchild);/非递归先序遍历void PreOrder1(Tree t)Tree p=t;Sqstack s;InitStack(s);while(p|!StackEmpty(s)if(p)printf(%c,p-data);Push(s,p);p=p-lchild;elsePop(s,p);p=p-rchild;/递归中序遍历void InOrder(Tree t)if(t)InOrder(t-lchild);printf(%c,t-data);InOrder(t-rchild);/非递归中序遍历void InOrder1(Tree t)Tree p=t;Sqstack s;InitStack(s);while(p|!StackEmpty(s)if(p)Push(s,p);p=p-lchild;elsePop(s,p)