[백준 1991번] 트리 순회 (C++)

문제링크 : https://www.acmicpc.net/problem/1991

1991번: 트리 순회

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

pair <char, char> tree[26];

void pre(char node)  //전위
{
    if(node == '.') return;

    cout << node;
    pre(tree[node-'A'].first);
    pre(tree[node-'A'].second);

}

void in(char node)   //중위
{
    if(node == '.') return;

    in(tree[node-'A'].first);
    cout << node;
    in(tree[node-'A'].second);
}

void post(char node)  //후위
{
    if(node == '.') return;
    
    post(tree[node-'A'].first);
    post(tree[node-'A'].second);
    cout << node;
}

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

    int N;
    cin >> N;

    while(N--)
    {
        char root, left, right;
        cin >> root >> left >> right;
        tree[root - 'A'].first = left;   //부모 왼쪽
        tree[root - 'A'].second = right;  //부모 오른쪽
    }

    pre('A');
    cout<<"\n";

    in('A');
    cout<<"\n";

    post('A');
    
    return 0;

}

각 부모 노드에 맞게 왼쪽 자식과 오른쪽 자식을 할당했다.

배열에 담는데 문자로 담을 수 없으니 root - 'A'를 통해서 정수로 변환하여 해당 칸에 자식들을 넣어준다.

 

그리고 전위, 중위, 후위에 맞춰서 출력과 재귀를 적절히 넣어주면 된다.

 

전위 -> root(출력), left, right

중위 -> left, root(출력), right

후위 -> left, right(출력), root