二叉树前序、中序、后序非递归遍历

我们知道二叉树的递归遍历写起来很简单，但是稍微不太容易理解。为了更好地理解二叉树的遍历过程，这里用栈来模拟递归的步进步出。

#include<iostream>#include<cstdio>#include<vector>#include<algorithm>#include<cmath>#include<string>#include<cstring>#include<stack>#include<queue>#include<map>#include<set>#include<unordered_set>#include<unordered_map>using namespace std;typedef struct BiTNode{	char data;	struct BiTNode *lchild, *rchild;      //左右孩子    }BiTNode, *BiTree;//按先序遍历创建二叉树    //BiTree *CreateBiTree()     //返回结点指针类型    //void CreateBiTree(BiTree &root)      //引用类型的参数    void CreateBiTree(BiTNode **root)    //二级指针作为函数参数    {	char ch; //要插入的数据    	cin>>ch;    	if (ch == '#')		*root = NULL;	else	{		*root = (BiTNode *)malloc(sizeof(BiTNode));		(*root)->data = ch;		PRintf("请输入%c的左孩子：", ch);		CreateBiTree(&((*root)->lchild));		printf("请输入%c的右孩子：", ch);		CreateBiTree(&((*root)->rchild));	}}//前序遍历的递归算法程序    void PreOrder(BiTNode *root){	if (root == NULL)		return;	printf("%c ", root->data); //输出数据    	PreOrder(root->lchild); //递归调用，前序遍历左子树    	PreOrder(root->rchild); //递归调用，前序遍历右子树    }//前序遍历的非递归算法程序void Pre_NoRecursion(BiTNode* root){	stack<BiTNode*>sta;	BiTNode * p = root;	while (p||!sta.empty())	{		if (p)//  if/else可以保证一直寻找到“最左下角的节点		{			cout << p->data<<" "; //保证先序			sta.push(p);			p = p->lchild;		}		else //左孩子为空，访问右节点		{			p = sta.top();			sta.pop();			p = p->rchild;		}	}}//中序遍历的递归算法程序    void InOrder(BiTNode *root){	if (root == NULL)		return;	InOrder(root->lchild); //递归调用，前序遍历左子树    	printf("%c ", root->data); //输出数据    	InOrder(root->rchild); //递归调用，前序遍历右子树    }//中序遍历的非递归算法程序void In_NoRecursion(BiTNode* root){	BiTNode * p = root;	stack<BiTNode*> sta;	while (p || !sta.empty())	{		if (p)		{			sta.push(p);			p = p->lchild;		}		else		{			 p = sta.top();			cout << p->data<<" ";			sta.pop();			p = p->rchild;			}	}}//后续遍历的非递归算法程序void  Post_NoRecursion(BiTNode* root){	BiTNode *p = root;	BiTNode *pre = NULL;//用来记录当前访问节点的上一个节点	stack<BiTNode*> sta;	while (p || !sta.empty())	{		while (p)		{			sta.push(p);			p = p->lchild;		}		p = sta.top();		//访问当前节点需要满足以下两个条件之一：		//1：当前节点的右孩子为空;2：或者右孩子已经访问过.		if (p->rchild == NULL || p->rchild == pre)		{			cout << p->data << " ";			pre = p;			sta.pop();			p = NULL;		}		else			p = p->rchild;	}}int main(){	BiTNode *root = NULL;	CreateBiTree(&root);	PreOrder(root);	cout << endl;	Pre_NoRecursion(root);	cout << endl;	InOrder(root);	cout << endl;	In_NoRecursion(root);	cout << endl;	Post_NoRecursion(root);	return 0;}构造的树是：
程序运行结果：