[数据结构与算法]二叉树的后序遍历（非递归）

法一：采用标注，分为第一次访问和第二次访问节点

第一次访问该节点，记做1，第二次记做2，使用数组存储标注

当第3次访问该节点的时候弹出堆栈，输出。

void PostOrderTraverse2(BT T) {
	BT Tmp = T;
	Stack S = CreatStack();
	BT stack[MaxLen];
	int top = -1;
	int flagstack[MaxLen];
	while (T || top != -1) {
		if (T) {
			stack[++top] = T;
			flagstack[top] = 1;
			T = T->lchild;
		}
		else {
			if (flagstack[top] == 1) {
				T = stack[top];
				flagstack[top] = 2;
				T = T->rchild;
			}
			else {
				if (flagstack[top] == 2) {
					T = stack[top--];
					printf("%2c", T->Data);
					T = NULL;
				}
			}
		}
	}
}

法二：后序遍历为左右根，我们可以反过来存储序列，按照根右左顺序存储到向量当中。

void PostOrderTraversal(BinTree BT){
	BinTree T = BT;
	Stack S = CreateStack();  // 创建并初始化堆栈 S
	vector<BinTree> v;
	Push(S,T);
	while(!IsEmpty(S)){  // 当树不为空或堆栈不空 
		T = Pop(S);
		v.push_back(T);
		if(T->Left)
			Push(S,T->Left);
		if(T->Right)
			Push(S,T->Right);
	}
	reverse(v.begin(),v.end());  // 逆转 
	for(int i=0;i<v.size();i++)
		printf("%d",v[i]->Data);
}