二叉树遍历 递归/非递归 模板（？？）

递归版

void First_order_traversal(int i) //先序
{
	printf("%d\n", key[i]);
	First_order_traversal(lc[i]);
	First_order_traversal(rc[i]);
}
void Sequential_traversal(int i) //中序
{
	Sequential_traversal(lc[i]);
	printf("%d\n", key[i]);
	Sequential_traversal(rc[i]);
}
void Post_order_traversal(int i) //后序
{
	Post_order_traversal(lc[i]);
	Post_order_traversal(rc[i]);
	printf("%d\n", key[i]);
}

非递归版

int vis[MAXN], lc[MAXN], rc[MAXN], key[MAXN];
void First_order_traversal(int i)
{
	stack<int> st;
	st.push(i);
	while(!st.empty())
	{
		i = st.top(); st.pop();
		printf("%d\n", key[i]);
		if(rc[i]) st.push(rc[i]);
		if(lc[i]) st.push(lc[i]);
	}
}
void Sequential_traversal(int i)
{
	stack<int> st;
	st.push(i);
	while(!st.empty())
	{
		if(!(i=st.top())) { st.pop(); continue; }
		i = st.top(); vis[i]++;
		if(vis[i] == 1) st.push(lc[i]);
		else if(vis[i] == 2) printf("%d\n", key[i]), st.push(rc[i]);
		else st.pop();
	}
}
void Post_order_traversal(int i)
{
	stack<int> st;
	st.push(i);
	while(!st.empty())
	{
		if(!(i=st.top())) { st.pop(); continue; }
		vis[i]++;
		if(vis[i] == 1) st.push(lc[i]);
		else if(vis[i] == 2) st.push(rc[i]);
		else printf("%d\n", key[i]), st.pop();
	}
}