[C++] 백준 BOJ 1991 트리 순회

문제링크 : https://boj.am/1991

문제에서 입력은 A~Z로만 한정되어 있다. 이러한 특성 덕분에 간단한 형태로 트리를 구현할 수 있다.

char 형태의 A(65) ~ Z(90)에서 A(65)씩 빼주면 A(0) ~ Z(25)로 표현할 수 있기 때문이다.

따라서, 인덱스 번호 자체가 노드에 들어있는 문자를 의미하는 것이기 때문에 2개의 배열 만으로도 트리의 구현이 가능하다.

현재 노드를 V, 좌측 자식 노드를 L, 우측 자식노드를 R이라고 한다면

전위순회는 V-L-R 순서로

중위순회는 L-V-R 순서로

후위순회는 L-R-V 순서로 순회하게 된다.

스택을 이용하여 구현을 하려고 시도해봤으나 너무 복잡하여 재귀로 구현했다.

// BOJ 1991 트리 순회
#include <iostream>
 
using namespace std;
 
char lNode[26]; // 좌측 자식 노드
char rNode[26]; // 우측 자식 노드
 
void pre(int idx) {
    // 현재 노드 출력
    cout << char(idx + 'A');
    // 자식 노드가 비어있지 않으면
    if (lNode[idx] != '.')
        pre(lNode[idx] - 'A');
    if (rNode[idx] != '.')
        pre(rNode[idx] - 'A');
}
 
void mid(int idx) {
    if (lNode[idx] != '.')
        mid(lNode[idx] - 'A');
    cout << char(idx + 'A');
    if (rNode[idx] != '.')
        mid(rNode[idx] - 'A');
}
 
void post(int idx) {
    if (lNode[idx] != '.')
        post(lNode[idx] - 'A');
    if (rNode[idx] != '.')
        post(rNode[idx] - 'A');
    cout << char(idx + 'A');
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    int num;
    cin >> num;
    char v, l, r;
    for (int i = 0; i < num; i++) {
        cin >> v >> l >> r;
        // idx: 0~25 -> idx+A: A~Z
        int idx = v - 'A';
        lNode[idx] = l;
        rNode[idx] = r;
    }
    pre(0);
    cout << '\n';
    mid(0);
    cout << '\n';
    post(0);
 
    return 0;
}