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

1312 단어 도론틀
귀속판
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(); } }

좋은 웹페이지 즐겨찾기