学步园

　　 如图，二叉树中，从根节点到任一节点所形成的路径中，到终点节点所在层为止，每一层有且仅有一个节点存在于这条路径中。因此，这条路径序列可以和一个栈序列相对应，其中，栈的第n个元素代表路径序列中，位于二叉树第n层的元素。

算法思想

　　根据以上分析，我们只需要模拟按箭头经过每一节点的过程，并在每次进入插入对应的访问函数，就可以形成对应的遍历算法。

　　 如何模拟呢？当每次进入一个节点，我们需要根据已经进入该节点的次数来决定下一节和所使用的访问函数，所以首先需要对节点的进入次数进行计数。计数和访问该节点之后，下一节点可能是子节点，也可能是父节点。综上，可以通过对每一节点的数据结构增设一计数量和一父指针来实现该算法。

　　现在讨论另一种实现方式，即通过计数栈来实现。

　　 基于以上分析，由于每一条路径唯一对应于一个栈状态，并且，如果栈的元素是节点，那么栈中每一元素的上一个元素就是该节点的父节点，所以可以一边访问每一个节点，一边形成对应的栈，在需要返回父节点时，只需要出栈上一节点即可，并且，注意到任一节点只有在访问满3次后才会从栈中移除，因此可以将该计数值设置在栈元素上，而不必设置到每一个节点上。由于栈的最大深度对应于树的深度，所以相对于前一种实现方案，该方案将节省许多空间。

数据结构

struct BTree
{
	int value;
	BTree* lchild;
	BTree* rchild;
};

具体算法

void travel(BTree* tree)
{
	stack<pair<BTree*, int>> work_stack;
	work_stack.push(make_pair(tree, 0)); 

	while (!work_stack.empty())
	{
		pair<BTree*, int> p = work_stack.top();
		work_stack.pop();

		// increase the count to indicate that the node
		// has been entered (again)
		int count = ++p.second;

		if (count == 1)
		{
			preVisit(p.first);
			work_stack.push(p);
			if (p.first->lchild != NULL)
				work_stack.push(make_pair(p.first->lchild, 0));
		}
		else if (count == 2)
		{
			inVisit(p.first);
			work_stack.push(p);
			if (p.first->rchild != NULL)
				work_stack.push(make_pair(p.first->rchild, 0));
		}
		// if it's the third time entering the node
		// then don't push it because we will never
		// come back again
		else
			postVisit(p.first);
	}
}

void preVisit(BTree* node)
{
	cout << "first time visit node " << node->value << endl;
}

void inVisit(BTree* node)
{
	cout << "second time visit node " << node->value << endl;
}

void postVisit(BTree* node)
{
	cout << "third time visit node " << node->value << endl;
}

const int SIZE = 7;

int main()
{
	BTree nodes[SIZE];
	for (int i = 0; i < SIZE; i++)
	{
		nodes[i].value = i+1;
		
		int l = i*2+1;
		int r = i*2+2;
		
		if (l < SIZE)
			nodes[i].lchild = &nodes[l];
		else
			nodes[i].lchild = NULL;

		if (r < SIZE)
			nodes[i].rchild = &nodes[r];
		else
			nodes[i].rchild = NULL;
	}

	travel(nodes);
}