[ BOJ / C++ ] 1991번 : 트리 순회

[ BOJ ] 1991번 : 트리 순회

문제 : https://www.acmicpc.net/problem/1991

---

[  문제  ]

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

[  입력  ]

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

[  출력  ]

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

---

[  문제 접근 및 풀이  ]

전위 순회는 루트 - 왼쪽 자식 - 오른쪽 자식

중위 순회는 왼쪽 자식 - 루트 - 오른쪽 자식

후위 순회는 왼쪽 자식 - 오른쪽 자식 - 루트 순으로

DFS를 돌면서 전위 순회 같은 경우는 루트 출력, DFS(왼쪽 자식) , DFS(오른쪽 자식)

이런 식으로 중위 순회, 후위 순위까지 해준 후 출력해주면 된다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N;
int L[30],R[30];
void Q_1991();
void preorder_traversal(int now);
void inorder_traversal(int now);
void postorder_traversal(int now);
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_1991();
}
void Q_1991(){
    cin >> N;
    for(int i=0;i<N;i++){
        char a,b,c;
        cin >> a >> b >> c;
        if(b!='.') L[a-'A']=b-'A';
        if(c!='.') R[a-'A']=c-'A';
    }
    preorder_traversal(0);
    cout <<"\n";
    inorder_traversal(0);
    cout <<"\n";
    postorder_traversal(0);
}
void preorder_traversal(int now){
    cout << char(now+'A');
    if(L[now]) preorder_traversal(L[now]);
    if(R[now]) preorder_traversal(R[now]);
}
void inorder_traversal(int now){
    if(L[now]) inorder_traversal(L[now]);
    cout << char(now+'A');
    if(R[now]) inorder_traversal(R[now]);
}
void postorder_traversal(int now){
    if(L[now])postorder_traversal(L[now]);
    if(R[now])postorder_traversal(R[now]);
    cout << char(now+'A');
}

---