二叉树三种遍历方式(非递归)

二叉树的先序、中序、后序遍历，采用非递归实现。

非递归实现的一个基本思路:在遍历的过程中要用栈来保存遍历中经过的结点。

#include<stdio.h>
#include<stdlib.h>
typedef char DataType;

//定义二叉树类型的节点
typedef struct BTnode{
	DataType data;//数据域
	struct BTnode* lchild,*rchild;//左孩子和右孩子
	int isFirst;//后序遍历用到,用于表示是不是第一次入栈
}BTree;

//创建二叉树,以先序的方式输入，如果左孩子或右孩子为空，则输入#
/*
   例子  A      输入为:ABD##E##CF###
        / \
	   B   C
	  / \  / 
	 D   E F    
*/
void createBTree(BTree * &t)
{
	char c;
   	c=getchar();
	if(c=='#')
		t=NULL;
	else
	{
		t=(BTree*)malloc(sizeof(BTree));
		t->data=c;
		createBTree(t->lchild);//创建左子树
		createBTree(t->rchild);//创建右子树
	}
}

/*

根据先序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，
因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树;
当访问完其左子树时，再访问它的右子树。因此其处理过程如下：

对于任一结点q：

1)访问结点q，并将结点q入栈;

2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，
并将栈顶结点的右孩子置为当前的结点q，循环至1);
若不为空，则将q的左孩子置为当前的结点q;

3)直到栈为空，则遍历结束。

*/
//非递归先序遍历
void preOrder(BTree * root)
{
	BTree * q,*s[100];
	q=root;
	int top=0;
	while(1)
	{
		while(NULL!=q)
		{
			printf("%c  ",q->data);//访问q结点
			top++;
			s[top]=q;
			q=q->lchild;
		}
		if(0!=top)
		{
			q=s[top];//出栈
			top--;
			q=q->rchild;//搜索右子树
		}
		else 
			break;
	}
}

/*

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，
然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，
然后按相同的规则访问其右子树。因此其处理过程如下：

对于任一结点P，

1)若其左孩子不为空，则将q入栈并将P的左孩子置为当前的q，然后对当前结点q再进行相同的处理；

2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的q置为栈顶结点的右孩子;

3)直到栈为空则遍历结束

*/
//非递归中序遍历
void inOrder(BTree * root)
{
	BTree * q,*s[100];//数组的每个元素是链表结点,s当做栈
	q=root;
	int top=0;//栈顶指针
	while(1)
	{
		while(NULL!=q)
		{
			top++;
			s[top]=q;  //先把左子树的每个结点入栈
			q=q->lchild;
		}
		if(0!=top)
		{
			q=s[top];//左子树全部入栈后开始出栈
			top--;
			printf("%c  ",q->data);//访问出栈的根节点
			q=q->rchild; //搜索右子树
		}
		else 
			break;//栈空时停止
	}
}

/*

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，
要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，
这就为流程的控制带来了难题。下面介绍两种思路。

第一种思路：
对于任一结点q，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，
但是此时不能将其出栈并访问，因为其右孩子还没被访问。所以接下来按照相同的规则对其右子树进行相同的处理，
当访问完其右孩子时,该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。
可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。
因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

*/
//非递归后序遍历 方法一
void postOrder1(BTree * root)
{
	BTree * q,*s[100];
	q=root;
	int top=0;
	while(1)
	{
		while(NULL!=q)//沿左子树一直往下搜索，直至出现没有左子树的结点 
		{
			top++;
			q->isFirst=1;
			s[top]=q;
			q=q->lchild;
		}
		if(0!=top)
		{
			q=s[top];
			top--;
			if(q->isFirst)//第一次出现在栈顶
			{
				q->isFirst=0;
				top++;
				q=q->rchild;

			}
			else//第二次出现在栈顶
			{
				printf("%c  ",q->data);
				q=NULL;
			}
		}
		else 
			break;
	}
}
/*

第二种思路：
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点q，先将其入栈。
如果q不存在左孩子和右孩子,则可以直接访问它;或者q存在左孩子或者右孩子,但是其左孩子和右孩子都已被访问过了,
则同样可以直接访问该结点。若非上述两种情况，则将q的右孩子和左孩子依次入栈，
这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

*/
//非递归后序遍历 方法二
void postOrder2(BTree * root)
{
	BTree * q,*s[100],*pre=NULL;//pre 前一次访问的结点  
	q=root;
	int top=0;
	s[++top]=q;
	while(1)
	{
		q=s[top];
		//如果当前结点没有孩子结点或者孩子节点都已被访问过 
		if((q->lchild==NULL&&q->rchild==NULL)||(pre!=NULL&&(pre==q->lchild||pre==q->rchild)))
		{
			printf("%c  ",q->data);
			top--;
			pre=q;
		}
		else
		{
			if(NULL!=q->rchild)
				s[++top]=q->rchild;//右孩子先入栈
			if(NULL!=q->lchild)
				s[++top]=q->lchild;
		}
		if(top==0)
			break;
	}
}

int main()
{
	BTree *root;
	createBTree(root);
    preOrder(root);
	printf("\n");
	inOrder(root);
	printf("\n");
	postOrder1(root);
	printf("\n");
	postOrder2(root);
	printf("\n");
	return 0;
}