백준 1991 트리 순회
https://www.acmicpc.net/problem/1991
그래프가 주어질 때 전위, 중위, 후위 탐색을 하는 문제이다.
전위탐색(pre order traversal)
- 루트 노드
- 왼쪽 자식노드를 root로 하는 subtree
- 오른쪽 자식노드를 root로 하는 subtree 순서로 탐색
중위탐색(in order traversal)
- 왼쪽 자식노드를 root로 하는 subtree
- 루트 노드
- 오른쪽 자식노드를 root로 하는 subtree 순서로 탐색
후위탐색(post order traversal)
- 왼쪽 자식노드를 root로 하는 subtree
- 오른쪽 자식노드를 root로 하는 subtree
- 루트 노드 순서로 탐색
수업에서 한번쯤 들어봤을거라 생각한다. 탐색 방법만 안다면 구현은 쉬운 문제이다.
#include<bits/stdc++.h>
using namespace std;
const int SZ=30;
char parent[SZ];
char ll[SZ]; // 왼쪽 자식
char rr[SZ]; // 오른쪽 자식
void prtravel(char node){
if(node==-1) return;
printf("%c",node);
prtravel(ll[node-'A']);
prtravel(rr[node-'A']);
}
void itravel(char node){
if(node==-1) return;
itravel(ll[node-'A']);
printf("%c",node);
itravel(rr[node-'A']);
}
void potravel(char node){
if(node==-1) return;
potravel(ll[node-'A']);
potravel(rr[node-'A']);
printf("%c",node);
}
int main(void){
memset(parent,-1,sizeof(parent));
memset(ll,-1,sizeof(ll));
memset(rr,-1,sizeof(rr));
int n; cin>>n;
for(int i=0;i<n;i++){
char p,l,r; cin>>p>>l>>r;
if(l!='.') ll[p-'A']=l,parent[l-'A']=p;
if(r!='.') rr[p-'A']=r,parent[r-'A']=p;
}
prtravel('A'); cout<<'\n';
itravel('A'); cout<<'\n';
potravel('A'); cout<<'\n';
return 0;
}
