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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1991번 문제인 트리 순회이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1991

1991번: 트리 순회

이 문제에서는 이진 트리를 순회하는 세 가지 방법인 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)를 구현해보는 문제이다.

주어진 트리의 노드는 알파벳으로 주어지지만, 각 문자 또한 숫자로 취급할 수 있다는 것을 떠올리면 구현하는 데에 특별히 어려운 점은 없다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::vector;
using std::pair;

pair<int, int> G[128];

void preorder(int root, int past) {
    if (root != '.') {
        cout << char(root);
        preorder(G[root].first, root);
        preorder(G[root].second, root);
    }
}

void inorder(int root, int past) {
    if (root != '.') {
        inorder(G[root].first, root);
        cout << char(root);
        inorder(G[root].second, root);
    }
}

void postorder(int root, int past) {
    if (root != '.') {
        postorder(G[root].first, root);
        postorder(G[root].second, root);
        cout << char(root);
    }
}

int main()
{
    int N;
    cin >> N;
    char root, l, r;
    for (int i = 0;i < N;i++) {
        cin >> root >> l >> r;
        G[root] = { l,r };
    }
    preorder('A', 0); cout << '\n';
    inorder('A', 0); cout << '\n';
    postorder('A', 0);

    return 0;
}