二叉树遍历-递归与非递归遍历_二叉树遍历递归和非递归的区别

二叉树的遍历原则

先序遍历：①访问当前结点，②遍历左子树，③遍历右子树

中序遍历：①遍历左子树，②访问当前结点，③遍历右子树

后序遍历：①遍历左子树，②遍历右子树，③访问当前结点

递归遍历

递归写法易懂，按照遍历原则递归即可，详见代码21~41行

非递归遍历

非递归先序和中序遍历套路相似，后序遍历比较麻烦，因为先序和中序都是在右子树之前就输出了根结点，而后序必须记住根结点，等待右子树遍历完才能输出根结点。非递归遍历必须借助栈

【先序遍历】

初始p为根结点

1. 当前结点p入栈，并输出。若p有左子树，令p=左孩子，执行1；否则执行2
2. 取出栈顶结点p（其左子树要么没有，要么已遍历）。若p有右子树，令p=右孩子，并执行1；否则继续执行2
3. 迭代结束的标识是p空且栈空

【中序遍历】

非递归中序与先序的思路一致，只是输出时机不同。

初始p为根结点

1. 当前结点p入栈。若p有左子树，令p=左孩子，执行1；否则执行2
2. 取出栈顶结点p，并输出（其左子树要么没有，要么已遍历）。若p有右子树，令p=右孩子，并执行1；否则继续执行2

【后序遍历】

非递归的先序和后序，在进入右子树之后，父结点就因出栈而丢弃了。而后序遍历必须记住父结点以便右子树访问结束后输出父结点。故不能再用先序或中序的思路。这里我写了3种方法。资料上常见的是方法1，但我觉得方法3最容易理解，最不易出错。

注意：①初始p为根结点。②用p==NULL标记为左子树已访问（不存在也视为已访问），③栈始终保存根结点root到当前结点p之间的所有结点

【方法1】

注意：

①初始p为根结点。

②用p==NULL标记为左子树已访问（不存在也视为已访问），

③栈始终保存根结点root到当前结点p之间的所有结点

④用last标记上一个输出的结点，若last是当前结点p的右子树，则表示右子树已访问

1. p不为NULL，则入栈，令p=左孩子。循环执行此步；直到p为NULL，即无左子树，执行2
2. 取栈顶结点记为p，则p的左子树不存在(由1知)或已访问(由3标记)
3. ①若p无右孩子或已访问（即 last 是p的右孩子），则输出当前结点p，并出栈；更新last为p，并标记p为NULL代表左子树已访问（因为当前p的右子树都访问了，那左子树一定已经访问过了），执行1。②否则，令p=右孩子，执行1
4. 迭代结束的标识是p空且栈空

【方法2】

与方法1很相似，但省去了last指针。后序遍历重要性质：若p是右孩子，则下一个访问的一定是其父结点。

注意：

①初始p为根结点。

②用p==NULL标记为左子树已访问（不存在也视为已访问），

③栈始终保存根结点root到当前结点p之间的所有结点

1. p不为NULL，则入栈，令p=左孩子。循环执行此步；直到p为NULL，即无左子树，执行2
2. 取栈顶结点记为p，则p的左子树不存在(由1知)或已访问(由3标记)
3. ①若p有右孩子，则令p=右孩子，执行1。②否则直接输出p，利用重要性质，若p是右孩子，持续输出其父结点；标记p为NULL（标记左子树已访问，别再访问了），执行1
4. 迭代结束的标识是p空且栈空

【方法3】

该方法与前两种大有不同，但最容易理解并记住。

注意：last 记录上一个输出的结点。

1. 根结点root入栈，然后进入迭代
2. 取栈顶记为p，若左孩子未访问则持续向下访问，直到没有左孩子。执行3。注意判断条件
3. 若右孩子未访问，则让右孩子入栈；否则输出p，并出栈，更新last为p。执行2

 

样例

代码中执行函数createTree()并输入ABD##E##C#FG##H##可以建立如下二叉树，

先序序列：ABDECFGH

中序序列：DBEACGFH

后序序列：DEBGHFCA

【代码】

#include<stdio.h>
#include<stdlib.h>
struct node{
	char data;
	struct node *lchild,*rchild;
};
 
node* createTree()  //先序建树,样例ABD##E##C#FG##H##
{
	char ch=getchar();
	if(ch!='#'){
		node* p=(node*)malloc(sizeof(node));
		p->data = ch;
		p->lchild = createTree();
		p->rchild = createTree();
		return p;
	}
	return NULL;
}
 
void display_pre(node *rt)	//递归先序 
{
	if(rt==NULL)return;
	putchar(rt->data);
	display_pre(rt->lchild);
	display_pre(rt->rchild);
}
void display_mid(node *rt)	//递归中序 
{
	if(rt==NULL)return;
	display_mid(rt->lchild);
	putchar(rt->data);
	display_mid(rt->rchild);
}
void display_back(node *rt)	//递归后序 
{
	if(rt==NULL)return;
	display_back(rt->lchild);
	display_back(rt->rchild);
	putchar(rt->data);
}
 
void display_pre_stack(node *rt)  //非递归先序
{
	node *p=rt,*st[100]; //st栈
	int top=0; //栈实时大小
	while(p||top>0){
		if(p){
			printf("%c",p->data);
			st[top++]=p;
			p=p->lchild;
		}else{
			p=st[--top];
			p=p->rchild;
		}
	}
}
 
void display_mid_stack(node *rt)  //非递归中序
{
	node *p=rt,*st[100]; //st栈
	int top=0; //栈实时大小
	while(p||top>0){
		if(p){
			st[top++]=p;
			p=p->lchild;
		}else{
			p=st[--top];
			printf("%c",p->data);
			p=p->rchild;
		}
	}
}
 
void display_back_stack1(node *rt) //非递归后序(方法1)
{
	node *last=NULL, *p=rt, *st[100];
	int top=0; //栈元素数量
	while(p||top>0)
	{
		while(p)	//p作为左子树还未访问
		{
			st[top++]=p;
			p=p->lchild;
		}
		p=st[top-1];      				  //此时p的左孩子已访问或不存在
		if(p->rchild && last != p->rchild)//p右孩子存在&&未访问
		{
			p=p->rchild;
		}
		else
		{
			printf("%c",p->data);
			top--;       //出栈
			last=p;
			p=NULL;      //p标记为NULL,告诉下一次循环别误入左孩子,因为已访问
		}
	}
}
 
void display_back_stack2(node *rt) //非递归后序(方法2)
{
	node *p=rt, *st[100];
	int top=0;//栈元素数量
	while(p||top>0)
	{
		while(p)          //直入最左孩子,若p为NULL,则左孩子已访问 
		{
			st[top++]=p;
			p=p->lchild;
		}
		p=st[top-1];      //此p的左孩子已访问或不存在
		if(p->rchild)	  //有右则右
		{
			p=p->rchild;
		}
		else 			 //无右则输出
		{
			printf("%c",p->data);
			top--;
			while(top>0 && st[top-1]->rchild == p) //若p是右孩子,则下一个输出的必为其父 
			{
				p=st[--top]; 					   //取其父,并输出 
				printf("%c",p->data);
			}
			p=NULL;     //标记为NULL,告诉下一次循环别进入左孩子了 
		}
	}
}
 
void display_back_stack3(node *rt) //非递归后序(方法3)
{
	node *last=NULL, *p, *st[100];
	int top=0; //栈元素数量
	st[top++]=rt;
	while(top>0)
	{
		p=st[top-1];                        //取栈顶为p
		while(p->lchild && p->lchild!=last && p->rchild!=last) //p左子树存在&&未访问
		{
			p=p->lchild;
			st[top++]=p;
		}
		if(p->rchild && p->rchild!=last)   //p右子树存在&&未访问
		{
			p=p->rchild;
			st[top++]=p;
		}
		else							   //左右均已访问,输出p 
		{
			printf("%c",p->data);
			top--;       //p出栈
			last=p;
		}
	}
}
 
 
int main()	//测试 
{
	printf("建树：");
	node *root = createTree();
	display_pre(root); puts(" ----递归先序");
	display_mid(root); puts(" ----递归中序");
	display_back(root); puts(" ----递归后序\n");
	
	display_pre_stack(root);    puts(" ----非递归先序");
	display_mid_stack(root);    puts(" ----非递归中序");
	display_back_stack1(root);  puts(" ----非递归后序（方法1）");
	display_back_stack2(root);  puts(" ----非递归后序（方法2）");
	display_back_stack3(root);  puts(" ----非递归后序（方法3）");
}

【运行结果】