[BOJ] #1991 트리 순회

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

1991번: 트리 순회

---

재귀함수를 활용하여 이진트리의 전위,중위,후위 순회를 출력하는 문제이다. 트리의 입력값도 사전에 다 주고, N의 개수도 최대 26까지이기 때문에 크게 까다로운 점은 없었다.

다만 이 문제에서의 핵심 포인트는 처음 루트값이 A라는 것을 활용하여 다른 자식 노드들을 따로 알파벳으로 접근하지 않고 pair<char, char>형의 배열의 인덱스로서 접근, 참조하는 것인데, 처음 풀때는 이 부분이 조금 이해가 가질 않았다. 하지만 이해하고 난 뒤에는 너무도 당연한 원리라 할 수 있다. 굳이 알파벳으로 노드를 참조하지 않아도 되는 이유는, 루트 노드를 제외한 모든 노드들은 어차피 부모 노드가 존재하기 때문에, 제일 조상 노드인 A를 활용하여 A노드의 자식들을 first, second인자로 참조하여 (pair<char,char>형이기에 left, right가 아닌 first, second로 사용하게 된다.) 접근하기 때문이다. 이를 활용하면, 맨 처음 조상인 A만 알파벳으로 참조하고, 그 이후에는 A의 자식 노드들을 재귀형태로 참조하면서 알고리즘이 돌아가게 된다.

#include <iostream>

using namespace std;

pair<char, char> arr[26];

void preOrder(char c) {
    if (c != '.') {
        cout << c;
        preOrder(arr[c-'A'].first);
        preOrder(arr[c-'A'].second);
    }
}

void inOrder(char c) {
    if (c != '.') {
        inOrder(arr[c-'A'].first);
        cout << c;
        inOrder(arr[c-'A'].second);
    }
}

void postOrder(char c) {
    if (c != '.') {
        postOrder(arr[c-'A'].first);
        postOrder(arr[c-'A'].second);
        cout << c;
    }
}

int main() {
    int N;
    cin >> N;

    while(N-->0) {
        char parent, left, right;
        cin >> parent >> left >> right;

        arr[parent-'A'].first = left;
        arr[parent-'A'].second = right;
    }

    preOrder('A');
    cout << endl;
    inOrder('A');
    cout << endl;
    postOrder('A');
    cout << endl;

    return 0;
}