ツリーが再帰的でないバージョンを巡回する

#include 

using namespace std;

typedef struct Node* pNode;

struct Node {
	char c;
	pNode lchild, rchild;
	Node(char c, pNode lchild = nullptr, pNode rchild = nullptr) :
		c(c), lchild(lchild), rchild(rchild) {}
};

pNode build()
{
	/*
			 A
		   /  \
		 B     C
		/ \   / \
	   D   E F   G
			/ \
		   H   I
	*/
	pNode root = new Node('A');
	root->lchild = new Node('B');
	root->rchild = new Node('C');
	root->lchild->lchild = new Node('D');
	root->lchild->rchild = new Node('E');
	root->rchild->lchild = new Node('F');
	root->rchild->rchild = new Node('G');
	root->rchild->lchild->lchild = new Node('H');
	root->rchild->lchild->rchild = new Node('I');
	return root;
}

void visit(pNode x)
{
	cout << x->c << " ";
}


/*
	    ，         ，       ，
	          ，      ，       ；
	              ，              ，
	           ，             ，    .
*/
void preVisitStack(pNode root)
{
	stack<pNode> st;
	pNode p = root;
	while (p || !st.empty()) {
		if (p) {
			visit(p);
			st.push(p);
			p = p->lchild;
		}
		else {
			p = st.top();
			st.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}

/*
	       ，                ，
	                  ，
	         ，                    ，
	       ，      .
*/
void midVisitStack(pNode root)
{
	stack<pNode> st;
	pNode p = root;
	while (p || !st.empty()) {
		if (p) {
			st.push(p);
			p = p->lchild;
		}
		else {
			p = st.top();
			visit(p);
			st.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}


/*
	         ，           ，          ，
	              ，                          ，
	           ，                   1，
	            ，       ；
	       ，           ，
	   1，       ，           2，
	           ，          ，
	   2，         ，         .

	             ，    STL  pair        .
*/
void backVisitStack(pNode root)
{
	stack<pair<pNode, int> > st;
	pNode p = root;
	while (p || !st.empty()) {
		if (p) {
			st.push(make_pair(p, 1));
			p = p->lchild;
		}
		else {
			auto now = st.top();
			st.pop();
			if (now.second == 1) {
				st.push(make_pair(now.first, 2));
				p = now.first->rchild;
			}
			else
				visit(now.first);
		}
	}
	cout << endl;
}

int main()
{
	pNode root = build();
	preVisitStack(root);
	midVisitStack(root);
	backVisitStack(root);
}