我們知道二叉樹的遞歸遍歷寫起來很簡單，但是稍微不太容易理解。為了更好地理解二叉樹的遍歷過程，這里用棧來模擬遞歸的步進(jìn)步出。

#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;//按先序遍歷創(chuàng)建二叉樹    //BiTree *CreateBiTree()     //返回結(jié)點(diǎn)指針類型    //void CreateBiTree(BiTree &root)      //引用類型的參數(shù)    void CreateBiTree(BiTNode **root)    //二級指針作為函數(shù)參數(shù)    {	char ch; //要插入的數(shù)據(jù)    	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); //輸出數(shù)據(jù)    	PreOrder(root->lchild); //遞歸調(diào)用，前序遍歷左子樹    	PreOrder(root->rchild); //遞歸調(diào)用，前序遍歷右子樹    }//前序遍歷的非遞歸算法程序void Pre_NoRecursion(BiTNode* root){	stack<BiTNode*>sta;	BiTNode * p = root;	while (p||!sta.empty())	{		if (p)//  if/else可以保證一直尋找到“最左下角的節(jié)點(diǎn)		{			cout << p->data<<" "; //保證先序			sta.push(p);			p = p->lchild;		}		else //左孩子為空，訪問右節(jié)點(diǎn)		{			p = sta.top();			sta.pop();			p = p->rchild;		}	}}//中序遍歷的遞歸算法程序    void InOrder(BiTNode *root){	if (root == NULL)		return;	InOrder(root->lchild); //遞歸調(diào)用，前序遍歷左子樹    	printf("%c ", root->data); //輸出數(shù)據(jù)    	InOrder(root->rchild); //遞歸調(diào)用，前序遍歷右子樹    }//中序遍歷的非遞歸算法程序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;			}	}}//后續(xù)遍歷的非遞歸算法程序void  Post_NoRecursion(BiTNode* root){	BiTNode *p = root;	BiTNode *pre = NULL;//用來記錄當(dāng)前訪問節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)	stack<BiTNode*> sta;	while (p || !sta.empty())	{		while (p)		{			sta.push(p);			p = p->lchild;		}		p = sta.top();		//訪問當(dāng)前節(jié)點(diǎn)需要滿足以下兩個(gè)條件之一：		//1：當(dāng)前節(jié)點(diǎn)的右孩子為空;2：或者右孩子已經(jīng)訪問過.		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;}構(gòu)造的樹是：
程序運(yùn)行結(jié)果：