두 갈래 트리 반복 귀속/비귀속 템플릿 (??)

귀속판

void First_order_traversal(int i) // 
{
	printf("%d
", key[i]);
	First_order_traversal(lc[i]);
	First_order_traversal(rc[i]);
}
void Sequential_traversal(int i) // 
{
	Sequential_traversal(lc[i]);
	printf("%d
", key[i]);
	Sequential_traversal(rc[i]);
}
void Post_order_traversal(int i) // 
{
	Post_order_traversal(lc[i]);
	Post_order_traversal(rc[i]);
	printf("%d
", key[i]);
}

비귀속판

int vis[MAXN], lc[MAXN], rc[MAXN], key[MAXN];
void First_order_traversal(int i)
{
	stack st;
	st.push(i);
	while(!st.empty())
	{
		i = st.top(); st.pop();
		printf("%d
", key[i]);
		if(rc[i]) st.push(rc[i]);
		if(lc[i]) st.push(lc[i]);
	}
}
void Sequential_traversal(int i)
{
	stack 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
", key[i]), st.push(rc[i]);
		else st.pop();
	}
}
void Post_order_traversal(int i)
{
	stack 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
", key[i]), st.pop();
	}
}