C语言实现二叉树的前序、中序、后续遍历(非递归法)

二叉树的前序遍历、中序遍历、后续遍历

（非递归法）

1、前序遍历（非递归）：

#include

#include

struct BiTNode *stack[100];

struct BiTNode//定义结构体

{

char data;

struct BiTNode *lchild,*rchild;

};

void later(struct BiTNode *&p) //前序创建树

{

char ch;

scanf("%c",&ch);

if(ch==' ')

p=NULL;

else

{

p=(struct BiTNode *)malloc(sizeof(struct BiTNode));

p->data=ch;

later(p->lchild);

later(p->rchild);

}

}

void print(struct BiTNode *p) //前序遍历（输出二叉树）

{

int i=-1;

while(1)

{

while(p!=NULL)

{

stack[++i]=p->rchild;/*printf("ok？\n");*/

printf("%c",p->data);

p=p->lchild;

}

if(i!=-1)

{

p=stack[i];

i--;

else

return;

}

}

void main()//主函数

{

struct BiTNode *p,*t;

later(p);

print(p);

}

2、中序遍历（非递归）

#include

#include

struct BiTNode *stack[100];

struct BiTNode//定义结构体

{

char data;

struct BiTNode *lchild,*rchild;

};

void later(struct BiTNode *&p) //前序创建树

{

char ch;

scanf("%c",&ch);

if(ch==' ')

p=NULL;

else

{

p=(struct BiTNode *)malloc(sizeof(struct BiTNode));

p->data=ch;

later(p->lchild);

later(p->rchild);

}

}

void print(struct BiTNode *p) //中序遍历（输出二叉树）{

int i=-1;

while(1)

{

while(p!=NULL)

i++;

stack[i]=p;

p=p->lchild;

}

if(i!=-1)

{

p=stack[i];

i--;

printf("%c",p->data);

p=p->rchild;

}

}

}

void main()//主函数

{

struct BiTNode *p;

later(p);

print(p);

}

3、后续遍历（非递归）：

#include

#include

struct BiTNode *stack[100];

struct BiTNode//定义结构体

{

char data;

struct BiTNode *lchild,*rchild;

};

void later(struct BiTNode *&p) //前序创建树

{

char ch;

scanf("%c",&ch);

if(ch==' ')

p=NULL;

else

{

p=(struct BiTNode *)malloc(sizeof(struct BiTNode));

p->data=ch;

later(p->lchild);

later(p->rchild);

}

}

void print(struct BiTNode *p) //后序遍历（输出二叉树）

{

int i=-1;

while(1)

{

while(p!=NULL)

{

stack[++i]=p;/*printf.0("ok？\n");*/

p=p->lchild;

}

if(i!=-1)

{

while(p==stack[i]->rchild||(p==stack[i]->lchild&&stack[i]->rchild==NULL)) {

p=stack[i--];

printf("%c",p->data);

if(i==-1)

return;

}

p=stack[i]->rchild;

}

else

return;

}

}

int main()//主函数

{

struct BiTNode *p,*t;

later(p);

print(p);

printf("\n");

system("pause");

return 0;

}

供测试使用的数据

树的遍历(递归和非递归)

二叉树的遍历 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为

空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 二、算法流程图

二叉树遍历C语言(递归,非递归)六种算法

数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号：

目录 一、设计思想 (01) 二、算法流程图 (02) 三、源代码 (04) 四、运行结果 (11) 五、遇到的问题及解决 (11) 六、心得体会 (12)

一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status 为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。

树转换成二叉树-树的前序、后序的递归、非递归和层次序的非递归

#include <> #include <> #include <> #define MAX_TREE_SIZE 100 typedef struct { int data; int parent; ata,[i].parent); printf("\n"); } } /*用双亲表示法创建树*/ PTree CreatTree(PTree T) { int i=1; int fa,ch; PTNode p; for(i=1;ch!=-1;i++) { printf("输入第%d结点:\n",i); scanf("%d,%d",&fa,&ch); printf("\n"); =ch; =fa; ++; [].data = ; [].parent = ; } printf("\n"); printf("创建的树具体情况如下:\n"); print_ptree(T); return T; } /*一般树转换成二叉树*/ BTNode *change(PTree T) { int i,j=0; BTNode p[MAX_TREE_SIZE]; BTNode *ip,*is,*ir,*Tree; ip=(BTNode *)malloc(sizeof(BTNode)); is=(BTNode *)malloc(sizeof(BTNode));

ir=(BTNode *)malloc(sizeof(BTNode)); Tree=(BTNode *)malloc(sizeof(BTNode)); for(i=0;i<;i++) { p[i]=GetTreeNode[i].data); } for(i=1;i<;i++) { ip=&p[i]; is=&p[j]; while[i].parent!=is->data) { j++; is=&p[j]; } if(!(is->firstchild)) { is->firstchild=ip; ir=ip; } else { ir->rightsib=ip; ir=ip; } } Tree=&p[0]; return Tree; } /*主菜单*/ void Menu() { printf("=================主菜单=======================\n"); printf("***输入-以双亲法创建一棵一般树***\n"); printf("***输入2-------------树的前序遍历(递归)*******\n"); printf("***输入3-------------树的后序遍历(递归)*******\n"); printf("***输入4-------------树的前序遍历(非递归)*****\n"); printf("***输入5-------------树的后序遍历(非递归)*****\n"); printf("***输入6-------------层次序的非递归遍历*******\n"); printf("***输入0-------------退出程序*****************\n"); printf("==============================================\n");

用递归非递归两种方法遍历二叉树

数据结构（双语） ——项目文档报告 用递归、非递归两种方法遍历二叉树 专业：计算机科学与技术 班级： 指导教师： 姓名：

学号： 目录 一、设计思想 (03) 二、算法流程图 (04) 三、源代码 (06) 四、运行结果 (12) 五、遇到的问题及解决 (14) 六、心得体会 (15)

一、设计思想 1．递归： （1）主函数main（）主程序要包括：定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。 （2）建树函数定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。 （3）先序遍历函数根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。 (4) 中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。 (5）后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。 2.非递归： （1）跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。 （2）然后是中序，先序，后序非递归遍历二叉树。 （3）中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。 (4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。 (5）后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。

二叉树的建立及几种简单的遍历方法

#include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //***************************************************

递归非递归两种算法遍历二叉树讲解

用递归、非递归两种方法遍历二叉树 一、设计思想 1. 用递归算法遍历 设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。 后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 2. 用非递归算法遍历 设计思想：主要是通过栈的存取，判空，从而实现树的遍历 前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。 后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。

先序遍历的非递归算法 C语言

先序遍历的非递归算法 #include #include #define MS 10 struct BTreeNode { char data; struct BTreeNode * left; struct BTreeNode * right; }; void InitBTree(struct BTreeNode * * BT) { * BT=NULL; } void CreatBTree(struct BTreeNode * * BT,char * a) { struct BTreeNode * p; struct BTreeNode * s[MS]; int top=-1; int k; int i=0; * BT=NULL; while(a[i]) { switch(a[i]) { case ' ':break; case '(': if(top==MS-1) { printf("栈空间太小，需增加MS的值!\n"); exit(1); } top++;s[top]=p;k=1; break; case ')': if(top==-1) {

printf("二叉树广义表字符串有错!\n"); exit(1); } top--;break; case ',' : k=2;break; default : if((a[i]>='a'&&a[i]<='z')||(a[i]>='A'&&a[i]<='Z')) { p=malloc(sizeof(struct BTreeNode)); p->data=a[i];p->left=p->right=NULL; if(* BT==NULL) * BT=p; else { if(k==1) s[top]->left=p; else s[top]->right=p; } } else {printf("二叉树广义表字符串有错!\n");exit(1);} } i++; } } void Preorder(struct BTreeNode * BT) { struct BTreeNode * s[10]; int top=-1; struct BTreeNode * p=BT; printf("先序遍历结点的访问序列为:\n"); while(top!=-1||p!=NULL) { while(p!=NULL) { top++; s[top]=p; printf("%c",p->data); p=p->left; } if(top!=-1) {

用递归和非递归算法实现二叉树的三种遍历

○A ○C ○D ○B ○E○F G 《数据结构与算法》实验报告三 ——二叉树的操作与应用 一.实验目的 熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用 二. 实验要求（题目） 说明：以下题目中（一）为全体必做，（二）（三）任选其一完成 （一）从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；（二）分别用递归和非递归算法实现二叉树的三种遍历； （三）模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) 三. 分工说明 一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。 四. 概要设计 实现算法，需要链表的抽象数据类型： ADT Binarytree { 数据对象：D是具有相同特性的数据元素的集合 数据关系R： 若D为空集，则R为空集，称binarytree为空二叉树；

若D不为空集，则R为{H}，H是如下二元关系； （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集； （3）若D1不为空，则D1中存在唯一的元素x1，∈H，且存在D1上的关系H1是H的子集；若Dr不为空集，则Dr中存在唯一的元素 Xr，∈H，且存在Dr上的关系Hr为H的子集；H={,,H1,Hr}; (4) (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr}) 是一颗符合本定义的二叉树，称为根的右子树。 基本操作: Creatbitree(&S，definition) 初始条件：definition给出二叉树S的定义 操作结果：按definition构造二叉树S counter(T) 初始条件：二叉树T已经存在 操作结果：返回二叉树的总的结点数 onecount(T) 初始条件：二叉树T已经存在 操作结果：返回二叉树单分支的节点数 Clearbintree(S) 初始条件：二叉树S已经存在 操作结果：将二叉树S清为空树 Bitreeempty(S) 初始条件：二叉树S已经存在 操作结果：若S为空二叉树，则返回TRUE，否则返回FALSE Bitreedepth(S,&e) 初始条件：二叉树S已经存在 操作结果：返回S的深度 Parent(S) 初始条件：二叉树S已经存在，e是S中的某个结点 操作结果：若e是T的非根结点，则返回它的双亲，否则返回空Preordertraverse(S) 初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。 操作结果：先序遍历S，对每个结点调用函数visit一次且仅一次。 一旦visit失败，则操作失败。 Inordertraverse (S,&e) 初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。

非递归方式建树并按任一种非递归遍历次序输出二叉树中

//非递归方式建树，并按任一种非递归遍历次序输出二叉树中的所有结点； #include #include #include #define MaxSize 50 typedef char ElemType; typedef struct TNode{ ElemType data; struct TNode *lchild,*rchild; }BTree; //------------------------------------------------------------------------------ ElemType str[]="A(B(C(D,E(F,G(,H))),I(J,K(L))),M)"; //"A(B(D,E(G,H(I))),C(F))"; //------------------------------------------------------------------------------ void CreateBTree(BTree **T,ElemType *Str); //非递归建树； void TraverseBTree(BTree *T); //选择非递归算法的遍历方式; void PreOrderUnrec(BTree *T); //先序遍历非递归算法; void InOrderUnrec(BTree *T); //中序遍历非递归算法; void PostOrderUnrec(BTree *T); //后序遍历非递归算法; //------------------------------------------------------------------------------ int main(void) { BTree *T = NULL; printf("\n二叉树的广义表格式为：\n\t"); puts(str); CreateBTree(&T,str); TraverseBTree(T); system("pause"); return 0; } //------------------------------------------------------------------------------ void CreateBTree(BTree **T,ElemType *Str) { //按二叉树广义表建立对应的二叉树存储结构; BTree *p = NULL,*Stack[MaxSize];//数组为存储树根结点指针的栈,p为指向树结点的指针; int top = -1; //top为Stack栈的栈顶指针; char flag; //flag为处理结点的左子树(L)和右子树(R)的标记; *T = NULL; while(*Str) { if (*Str == '(') {Stack[++top] = p;flag = 'L';} //入栈; else if(*Str == ')') --top; //出栈; else if(*Str == ',') flag = 'R'; else { if(!(p = (BTree *)malloc(sizeof(BTree)))) exit (1); p->data = *Str; p->lchild = p->rchild = NULL; //初始化新结点;

java二叉树的遍历(递归非递归)

import java.util.Stack; public class MyTree{ public static void main(String[] s){ new MyTree(); } public MyTree(){ TreeNode root = init();//初始化二叉树并返回根节点 System.out.println("递归先序遍历"); preorder(root); System.out.println(); System.out.println("递归中序遍历"); inorder(root); System.out.println(); System.out.println("递归后续遍历"); posorder(root); System.out.println(); System.out.println("非递归先序遍历"); preorder(root); System.out.println(); System.out.println("非递归中序遍历"); _inorder(root); System.out.println(); System.out.println("非递归后续遍历"); _posorder(root); System.out.println(); } public void preorder(TreeNode root){//递归二叉树的前序遍历 if(root != null){ System.out.print(root.getValue());//访问节点值 preorder(root.getLeft()); preorder(root.getRight()); } } public void _preorder(TreeNode p){ Stack stack = new Stack(); if(p!=null){ stack.push(p); while(!stack.empty()){ p = stack.pop(); System.out.print(p.getValue()); //右子结点先进栈，左子结点再进栈，所以先访问的 是左子结点 if(p.getRight()!= null)

后序遍历的非递归算法.doc

第六章树二叉树 后序遍历的非递归算法。在对二叉树进行后序遍历的过程中，当指针p 指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将此结点的地址进栈保存。当其左子树遍历完毕之后，再次搜索到该结点时(该结点的地址通过退栈得到) ，还不能对它进行访问，还需要遍历它的右子树，所以，再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈，引入一个标志变量nae,有0 表示该结点暂不访问 1 表示该结点可以访问标志flag 的值随同进栈结点的地址一起进栈和出栈。因此，算法中设置两个空间足够的堆栈,其中, STACKlCM] 存放进栈结点的地址, STACK2[M] 存放相应的标志n 昭的值, 两个堆栈使用同一栈顶指针top , top 的初值为— 1 。 具体算法如下： #defineH 100 /?定义二叉树中结点最大数目。/ voidPOSTOiRDER(BTREET) { / *T 为二叉树根结点所在链结点的地址。/ BTREESTACKl[H] , p=T ；intSTACK2[M] , flag,top= —1；if(T!=NULL) d0{ while(p!=NULL){ STACK/[++top]=p ; /?当前p所指结点的地址进栈?/ STACK2[top]= 0 ; /,标志0 进栈?/ p=p->lchild ；/?将p 移到其左孩子结点x/ } p=STACKl[top) ；flag=STACK2[top--] ；if(flag==0){ STACKl[++top]=p ; /,当前p所指结点的地址进栈。/ STACK2[toP]=1 ; /?标志1 进栈?/ p=p->rchild ; /x将p移到其右孩子结点o/ } else{ VISIT(p) ; /x访问当前p所指的结点x/ p=NULL ； } }while(p!=NULLtttop!=-1) ； } 不难分析,上述算法的时间复杂度同样为O(n) 7．6．3 二叉树的线索化算法 对--X 树的线索化,就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程, 因此, 二叉树的线索化过程只能 在对二叉树的遍历过程中进行。 下面给出二叉树的中序线索化的递归算法。算法中设有指针pre,用来指向中序遍历过 程中当前访问的结点的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点， 但在算法执行过程中，T总是指向当前访问的结点。voldlNTHREAD(TBTREET) { TBTREE pre ； if(T!=Null){ INTHREAD(T —>lchild)； if(T —>rchild==NULL)

递归非递归两种算法遍历二叉树

. 一、设计思想 1. 用递归算法遍历 设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。 后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 2. 用非递归算法遍历 设计思想：主要是通过栈的存取，判空，从而实现树的遍历 前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。 后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。

递归非递归两种算法遍历二叉树讲解

一、设计思想 1.用递归算法遍历 设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边 或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用, 重复输出和遍历右子树的操作。 后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 2.用非递归算法遍历 设计思想：主要是通过栈的存取，判空，从而实现树的遍历 前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。 后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重 复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避 免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。

遍历二叉树(递归+非递归)实验资料报告材料

实验报告

附：源程序： 递归算法程序 #include #include #include #define maxsize 100 #define FALSE 0 #define TRUE 1 typedef struct node //二叉树结构体类型定义{ char data; struct node *lchild; struct node *rchild; }bitnode,*bitree; /*扩展先序序列创建二叉链表*/ void cteatebitree(bitree *bt) {

char ch; ch=getchar(); if(ch=='.')*bt=NULL; else { *bt=(bitree)malloc(sizeof(bitnode)); (*bt)->data=ch; cteatebitree(&((*bt)->lchild)); cteatebitree(&((*bt)->rchild)); } } /*先序递归遍历*/ void preorder(bitree root) { if(root!=NULL) { printf("%c ",root->data); preorder(root->lchild); preorder(root->rchild); } } /*中序递归遍历*/ void inorder(bitree root) { if(root!=NULL) { preorder(root->lchild); printf("%c ",root->data); preorder(root->rchild);

递归非递归两种算法遍历二叉树讲解

一、设计思想 1. 用递归算法遍历 设计思想：主要是通过不同程序顺序，从而实现递归的顺序遍历 前序遍历：先判断节点是否为空，如果不为空，则输出。再判断左节点是否为空，如果不为空，则递归调用，直到遍历到最左边。接着再遍历最左边的右子树，如果此时右子树不为空，则递归遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯上次的递归调用，重复输出和遍历右子树的操作。 中序遍历：先遍历左节点是否为空，如果不为空，则递归调用，直到遍历到最左边或者叶子节点，然后输出，接着再遍历最左边的右子树，如果此时右子树不为空，则递归重复遍历左子树的操作，直到遍历到叶子节点。如果右子树为空，则回溯到上次递归调用，重复输出和遍历右子树的操作。 后序遍历：先判断左节点是否为空，如果不为空则一直递归直到遍历到最左边，然后遍历右节点，再接着遍历到左子树的最右边，直到遍历到叶子节点。此时输出，回溯到上次递归，继续执行后面的操作，重复，直到将整个树遍历完毕。 2. 用非递归算法遍历 设计思想：主要是通过栈的存取，判空，从而实现树的遍历 前序遍历：通过一个循环实现。先输出节点的数值，因为栈的特性，则需要先判断右子树是否为空，如果不为空，则将右子树压栈。然后判断左子树是否为空，如果不为空，则将左子树压栈。接着再将栈里面的子树弹出赋给给当前节点变量，重复上述操作，直到栈为空后退出循环。 中序遍历：通过循环实现。将树一直遍历到最左端，并将中间所经过的节点保存在栈中，当遍历到最左边的时候，则弹出栈里面的子树。输出数值，将当前节点赋值为当前节点的右子树，遍历右子树，即重复上述操作，直到当前节点为空，并且栈内元素为0。 后序遍历：通过循环和标记栈实现。将数一直遍历到最左端，并将中间的节点保存在树栈中，同时同步的添加一个标记栈。当遍历到最左边的时候，弹栈并赋值给当前栈，然后判断标记栈的数值，如果数值为0的话则代表当前树没有遍历过，遍历右子树。然后重复上面的操作，如果数值为1的话则代表此时数已经遍历过了，可以开始输出了，为了避免重复输出，将当前栈赋为空。重复循环操作，直到栈内没有元素，且当前节点为空（因为一直左的操作并没有将右子树压栈）。

数据结构试验报告用先序中序建立二叉树后序遍历非递归

数据结构》实验报告 ◎实验题目: 创建并遍历二叉树◎实验目的：熟悉二叉树存储结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。 ◎实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。 一、需求分析 该程序用非递归的方法，利用先序和中序建立二叉树，然后用后序遍历的方法输出二叉树的 1、输入的形式和输入值的范围；程序运行时输入二叉树的先序和中序序列，为字符型元素。 2、输出的形式；运行结果为输出二叉树的后序序列，亦为字符型元素。 3、程序所能达到的功能；本程序可以建立一个二叉树存储结构，并且访问其结点元素。 4、测试数据：输入：先序：abcde 中序：edcba 输出：后序：edcba 二概要设计 1. 本程序中首先需定义二叉树的节点类型，节点为一个含有数据与和指针域的结构体。 2. 其次，本程序中需要用两个栈，一个用来存放指针，一个用来存放数组元素的下标。 3. 主程序中，分别输入两个字符串，作为二叉树的先序和中序序列；两个子函数分别实现创建二叉树和后序遍历输出二叉树的功能。而在子函数中还调用了例如出栈入栈等子函数。 三详细设计 1. 定义二叉树节点类型 struct node { char data; struct node *lchild; struct node *rchild; }BTree; 2. 定义两个栈的类型 struct snode { int top; int a[MAX]; }; struct snode1 int top; struct node *c[MAX]; }; 3．主函数void main() { char a[MAX]={0}; char b[MAX]={0};

用递归,非递归两种方法遍历二叉树

一、设计思想 递归实现二叉树遍历的思想: 1.要遍历二叉树首先的问题是创建二叉树。二叉树的创建可以采用很多的方法。例如：先序，中序，后序，还可以采用层次的方法创建二叉树。本程序采用的是先序递归的方式创建的二叉树。 2.然后是中序，先序，后序递归遍历二叉树。递归的思想是一直调用方法本身。 3.中序递归遍历二叉树的思想是先访问左子树，然后访问根节点，最后访问右子树。当访问左子树或是右子树的时候，实际上调用的是函数本身。在这里就体现了递归的思想，当函数的返回值是0的时候，则返回上一次的程序，继续执行下面的语句。 4.先序递归遍历二叉树的思想是先访问根节点，然后访问左子树，最后访问右子树。同样如步骤3的方式相同，当访问左子树或者是右子树的收，实际上调用的是函数本身，直到返回值是0的时候，返回上一层的程序继续执行。 5.后序递归遍历二叉树的思想是先访问左子树，然后访问右子树，最后访问根节点。 同样跟步骤3的方式相同，当访问左子树或者右子树的时候实际上是调用的是方法本直到有返回值的时候才返回上一层的程序，继续执行. 非递归实现二叉树遍历的思想: 1.跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。 2.然后是中序，先序，后序非递归遍历二叉树。 3.中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。 4.先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进栈。重复上面的操作，直到栈为空。 5.后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。 二、算法流程图 递归方法遍历二叉树的流程图如图1