[백준] 1991번 트리 순회

문제

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

풀이과정

기본적인 트리의 순회과정 구현을 묻는 문제다.

전위 순회(preorder)는 root->left->right
중위 순회(inorder)는 left->root->right
후위 순회(postorder)는 left->right->root

어떻게 구현을 해야할지 조금만 생각해보면 쉽게 풀 수 있는 문제다. 문제에서 입력되는 트리는 자식을 최대 2개로 가지는 이진 트리이므로 배열로 트리를 표현할 수 있다. a[26][2] 라는 배열을 선언하여 각 알파벳을 부모노드로 가지는 자식을 저장하면 된다. 각 순회의 구현은 재귀호출을 통해 구현하였다.

소스코드

#include <iostream>

using namespace std;

int a[26][2];
int N;

void preorder(int node)
{
    if (node == -1) return;

    cout << char(node + 'A');
    preorder(a[node][0]);
    preorder(a[node][1]);
}

void inorder(int node)
{
    if (node == -1) return;

    inorder(a[node][0]);
    cout << char(node + 'A');
    inorder(a[node][1]);
}

void postorder(int node)
{
    if (node == -1) return;

    postorder(a[node][0]);
    postorder(a[node][1]);
    cout << char(node + 'A');
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        char root, left, right;

        cin >> root >> left >> right;

        a[root - 'A'][0] = left != '.' ? left-'A' : -1;
        a[root - 'A'][1] = right != '.'? right-'A' : -1;
    }

    preorder(0);
    cout << "\n";
    inorder(0);
    cout << "\n";
    postorder(0);
    cout << "\n";

    return 0;
}