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

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

1991번: 트리 순회

트리 순회

풀이

트리의 순회는 재귀 함수로 구현해주면 간단하게 풀 수 있다.

전위 순회는 루트 > 왼쪽 자식 > 오른쪽 자식 순으로,

중위 순회는 왼쪽 자식 > 루트 > 오른쪽 자식 순으로,후위 순회는 왼쪽 자식 > 오른쪽 자식 > 루트 순으로 순회가 이루어 진다는 점을 알아두자.

 

위 과정을 재귀함수로 단순하게 그대로 옮겨준다.

 

#include <iostream>
#include <vector>

#define endl '\n'

using namespace std;

vector<vector<char>> tree;

void preorder(char node) {
    if (node == '.')
        return;

    cout << node;
    preorder(tree[node - 65][0]);
    preorder(tree[node - 65][1]);
}

void inorder(char node) {
    if (node == '.')
        return;

    inorder(tree[node - 65][0]);
    cout << node;
    inorder(tree[node - 65][1]);
}

void postorder(char node) {
    if (node == '.')
        return;

    postorder(tree[node - 65][0]);
    postorder(tree[node - 65][1]);
    cout << node;
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    tree.resize(N + 1); // 0번 인덱스 = 왼쪽 자식, 1번 인덱스 = 오른쪽 자식
    char a, b, c;
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c;

        tree[a - 65].push_back(b);
        tree[a - 65].push_back(c);
    }

    preorder('A');
    cout << endl;
    inorder('A');
    cout << endl;
    postorder('A');
    cout << endl;

    return 0;
}