二叉树的遍历（先序、中序、后序和层次法）

一、二叉树的遍历

●遍历是指按指定的规律从根结点开始，对二叉树中的每个结点遍历一次且仅遍历一次。
●遍历可以采用递归方法（程序简单）和非递归方法（程序稍复杂）。从中可以寻出“足迹”。
例如下列一颗简单的二叉树：

遍历二叉树，可有3+1种方法：先序、中序、后序和层次法。
以下前三种方法从根部开始逆时针方向绕过各结点，形成一条蜿蜒“足迹”。

(1)先序法（又称先根法）
先序遍历：根，左子树，右子树
遍历的结果：A，B，C
遍历的足迹：沿途经过各结点的“左部”

(2)中序法（又称中根法）
中序遍历：左子树，根，右子树
遍历的结果：B，A，C
遍历的足迹：沿途经过各结点的“下部”

(3)后序法（又称后根法）
后序遍历：左子树，右子树，根
遍历的结果：B，C，A
遍历的足迹：沿途经过各结点的“右部”

(4)层次法
层次遍历：从根开始，层次自上到下，同层结点自左至右进行。
遍历的结果：A，B，C
遍历的足迹：第一层A，第二层B，C

例：下列二叉树的四种遍历

(1)先序遍历的结果：A，B，D，F，C，E，G

 - A（根）
 - B，D，F（先序根的左子树）
 - C，E，G（先序根的右子树）

(2)中序遍历的结果：B，F，D，A，E，G，C

 - B，F，D（中序根的左子树） 
 - A（根）
 - E，G ，C（中序根的右子树）

(3)后序遍历的结果：F，D，B，G，E，C，A

 - F，D，B（后序根的左子树）
 - G，E，C（后序根的右子树）
 - A（根）

注意：蜿蜒的路线仅用于展示思路，熟悉后心里知晓即可，不必画出。

(4)按层次遍历的结果：A，B，C，D，E，F，G

 - A根 （第一层）
 - B，C （第二层）
 - D，E （第三层）
 - F，G （第四层）
 现象：左右子树次序打乱
 A（根），B（左），C（右），D（左），E（右），F（左），G（右）

二、通过两个序列确定唯一二叉树

1.若中序确定，若再有先序（或后序）也确定，则该二叉树唯一确定；

注意：两个序列中必须有一个中序。
前序第一个是根节点。
后序最后一个是根节点。
而将如上节点放在中序序列中，左侧是根节点的左子树，右侧是根节点的右子树。

例如：
（1） 已知一棵二叉树的中序和后序遍历序列分别是：BFDGAEC和FGDBECA，试画出这棵二叉树。

（2） 已知一棵二叉树的先序和中序遍历序列分别是：ABCDEFG和CBDAFEG，试画出这棵二叉树。

2.若二叉树的先序和后序确定，则该二叉树不能唯一确定；
如：下列两棵不同的二叉树先序都是（A，B），而后序都是（B，A）。

三、二叉树的遍历算法

二叉树的先序遍历

遍历规律：先遍历根结点，再遍历左子树，最后遍历右子树
●先序遍历的递归算法和程序（较简单）

void PreOrder(BTree *bt)
{ 
	if(bt!=NULL)
	{ 
	printf(“%c ”,bt->data); 
	//遍历根结点（输出数据）
	PreOrder(bt->lchild); //递归遍历左子树
	PreOrder(bt->rchild); //递归遍历右子树
	}
}

●先序遍历的非递归算法和程序（稍复杂）
使用一个一维数组作为栈，存储二叉链表中的结点。思路为：从二叉树的根结点开始，沿左子树一直走到末端（左孩子为空）为止，在遍历过程中，依次把所遇结点入栈，当左子树为空时，从栈中退出栈顶结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空时止。

void PreOrder1(BTree *bt)
{
	BTree *s[100],*p=bt; //数组s作为栈
 	int top=0; //top为栈顶指针
 	while(p!=NULL||top>0)
 	{
  		while(p!=NULL) //遍历根和左子树
   		{ 
   			printf(“%c ”,p->data); 
			s[++top]=p; p=p->lchild;
		}
  	p=s[top--];p=p->rchild; //遍历右子树
	}
}

二叉树的中序遍历

遍历规律：先遍历左子树，再遍历根结点，最后遍历右子树。
●中序遍历的递归算法和程序（较简单）

在这里插入代码片
void InOrder(BTree *bt)
{ 
	if(bt!=NULL)
	{ 
		InOrder(bt->lchild); //递归遍历左子树 
 		printf(“%c ”,bt->data); 
		//遍历根结点（输出数据）
 		InOrder(bt->rchild); //递归遍历右子树
 	}
 }

●中序遍历的非递归算法和程序（稍复杂）
使用一个一维数组作为栈，存储二叉链表中的结点。思路为：从二叉树的根结点开始，沿左子树一直走到末端（左孩子为空）为止，在走的过程中，把依次遇到的结点入栈，待左子树为空时，从栈中退出结点并访问，然后再转向它的右子树。如此重复，直到栈为空或指针为空为止。

 void InOrder1(BTree *bt)
{
 	BTree *s[100],*p=bt; //数组s作为栈
 	int top=0; //top为栈顶指针
 	while(p!=NULL||top>0)
 	{
    	while(p!=NULL){s[++top]=p;p=p->lchild;} 
		//遍历左子树
 		p=s[top--];
 		printf(“%c ”,p->data);p=p->rchild; 
		//遍历根和右子树
	}
}

标题二叉树的后序遍历

遍历规律：先遍历左子树，再遍历右子树，最后遍历根结点。
●后序遍历的递归算法和程序（较简单）

void PostOrder(BTree *bt)
{ 
	if(bt!=NULL)
	{ 
		PostOrder(btlchild); //递归遍历左子树
 		PostOrder(btrchild); //递归遍历右子树
 		printf(“%c ”,btdata);
 		//遍历根结点（输出数据）
	}
}

●后序遍历的非递归算法和程序（稍复杂）
利用栈来实现二叉树的后序遍历比先序和中序复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点先要入栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，再次退栈时，才能访问该结点。
为了区分同一结点的两次进栈，引入一个次数标志，一个元素第一次进栈标志为0，第二次为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。

void PostOrder1(BTree *bt)
{
 	BTree *s1[100],*p=bt; 
	//栈s1存放树中的结点
 	int s2[100],b,top=0;  //栈s2存放进栈标志
 	do
 	{
  		while(p!=NULL) //遍历左子树
     	{
     		s1[top]=p;s2[top++]=0;
			//第一次进栈标志为0
      		p=plchild;}
 			if(top>0)
 			{
  				b=s2[--top]; p=s1[top];
  				if(b==0)
  				{
  					s1[top]=p;s2[top++]=1;
					//第二次进栈标志为1
   					p=prchild;
   				} //遍历右子树
			else {printf(“%c ”,pdata); p=NULL;} 
			//遍历根
		}
	}while(top>0);
}

例：算术表达式a+bc-d-e/f按不同的次序遍历此二叉树，将访问的结点按先后次序排列起来的次序是：

先序序列为(前缀表达式)：-+ab-cd/ef
中序序列为(中缀表达式)：a+bc-d-e/f
后序序列为(后缀表达式)：abcd-+ef/-