트리 순회 1991

문제

접근 방법

이진 트리를 구현하고 재귀 함수를 이용해주면 된다고 생각했다.

코드

#include <iostream>
#include <map>
using namespace std;
map<char, pair<char, char>> tree;
void left(char p)
{
    if (p == '.')
        return;
    cout << p;
    left(tree[p].first);
    left(tree[p].second);
}
void mid(char p)
{
    if (p == '.')
        return;
    mid(tree[p].first);
    cout << p;
    mid(tree[p].second);
}
void right(char p)
{
    if (p == '.')
        return;
    right(tree[p].first);
    right(tree[p].second);
    cout << p;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i)
    {
        char p, c1, c2;
        cin >> p >> c1 >> c2;
        tree[p] = {c1, c2};
    }
    left('A');
    cout << '\n';
    mid('A');
    cout << '\n';
    right('A');
    return 0;
}

풀이

map으로 이진 트리를 표현해주고 left, mid, right 함수를 만들어줬다.
각 함수는 자기 자식을 재귀 형식으로 불러와 준다.
출력, 재귀 순서에 따라 전위, 중위, 후위 순회가 이루어진다.
map으로 트리를 구성하는 방법이 생각보다 편리했다.
자주 사용해줘야겠다.