DS二叉树--后序遍历非递归算法

后序遍历一般算法：

1.若二叉树为空，则返回；否则：

2.后序遍历左子树(L)

3.后序遍历右子树(R)

4.访问根节点(D)        

 

后序遍历非递归实现需要使用到栈（需要把前几层的节点先放入后输出）

具体步骤为：

入栈走左子树，若栈顶右子树为空或栈顶右子树为刚输出的，出栈；否则走右子树。出栈时输出。

可理解为：

按照先左后右顺序，若一个节点没有后续节点，则出栈输出，若此时栈顶元素右节点未被走过，则继续将右节点压入栈中，否则，出栈输出，直到栈空。

下面讲得更加清楚：

(155条消息) 二叉树：后序遍历非递归算法_花间半盘棋的博客-CSDN博客_后序遍历的非递归算法

输入样例：

3
AB0C00D00
ABC00D00EF000
ABCD0000E0F00

输出：

CBDA
CDBFEA
DCBFEA

详细代码为：

（由于需要记录某节点是否已被走过，使用flag做标志位）

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
 
class BiTreeNode{
	public:
		char data;
		int flag=0;
		BiTreeNode* leftChild;
		BiTreeNode* rightChild;
		BiTreeNode():leftChild(NULL),rightChild(NULL){
		}
		~BiTreeNode(){
			delete leftChild;
			delete rightChild; 
		}
};
class BiTree{
	BiTreeNode *root;
	int pos;
	string sTree;
    BiTreeNode* CreateTree() {
	BiTreeNode* T;
	char c=sTree[pos++];
	if(pos<=sTree.length()){
		if(c != '0') {
			T = new BiTreeNode();
			//cout<<c<<endl;
			T->data = c;
			T->leftChild=CreateTree();
			T->rightChild=CreateTree();
			
		}
	else T = NULL;	
	}
 
	return T;
	
}
	public:
	queue<char> q;
	int floor;
	BiTree() :root(NULL) {};
	void Create(string vArray){
	pos = 0;
	sTree.assign(vArray);	//把参数保存到内部字符串
	root = CreateTree();	//建树成功后root指向根结点
}
   void PostOrder(){//后序遍历无递归
		stack<BiTreeNode*> s;
		s.push(root);
		BiTreeNode *t=root;
		root->flag=1;//用flag标记该节点是否被记录过
		while(!s.empty()&&t!=NULL){
			if(t->leftChild&&t->leftChild->flag!=1){//若该节点后续有左分支，且未被走过，压入栈中
				s.push(t->leftChild);
				t=t->leftChild;
			}
			else if(t->rightChild&&t->rightChild->flag!=1){/若该节点后续有右分支，且未被走过，压入栈中
				s.push(t->rightChild);
				t=t->rightChild;
			}
			else {//出栈输出，栈空结束
			cout<<s.top()->data;
			s.pop();
              if(!s.empty())
			  t=s.top();
			}
		}
	}
};
 
int main(){
	int t;
	cin>>t;
	string s;
	while(t--){
		cin>>s;
		BiTree t;
		t.Create(s);
	    t.PostOrder();
	    cout<<endl;
	}
	return 0;
	
}