두 갈래 트리 반복 귀속/비귀속 템플릿 (??)
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();
}
}