[백준 1991] 트리 순회

문제 

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

1991번: 트리 순회

 

 

문제 분석 

입력 받아 트리를 만들고 그 트리를 전위, 중위, 후위 순서대로 순회하여 값을 출력하는 간단한 문제이다. 

 

 

알고리즘 설계 

몇 가지의 노드가 있는지 입력 받고, 노드와 연결된 노드를 입력받아 이중 vector에 넣어준다. 

 

이후 전위, 중위, 후위 순회를 하여 출력해준다. 

 

 

유의점 

전위, 중위, 후위 순회에 간단한 이해가 필요한 문제이다. 

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> vec;

void PreorderTraverse(int index);
void InorderTraverse(int index);
void PostorderTraverse(int index);

int main()
{
    int index;
    char c1, c2, c3;
    cin >> index;
    vec.resize(index, vector<int>(2, -1));

    while (index--)
    {
        cin >> c1 >> c2 >> c3;
        if (c2 != '.')
            vec[c1 - 'A'][0] = (c2 - 'A');
        if (c3 != '.')
            vec[c1 - 'A'][1] = (c3 - 'A');
    }

    PreorderTraverse(0);
    cout << '\n';
    InorderTraverse(0);
    cout << '\n';
    PostorderTraverse(0);
}

void PreorderTraverse(int index)
{
    cout << (char)(index + 'A');
    if (vec[index][0] != -1)
        PreorderTraverse(vec[index][0]);
    if (vec[index][1] != -1)
        PreorderTraverse(vec[index][1]);
}

void InorderTraverse(int index)
{
    if (vec[index][0] != -1)
        InorderTraverse(vec[index][0]);
    cout << (char)(index + 'A');
    if (vec[index][1] != -1)
        InorderTraverse(vec[index][1]);
}

void PostorderTraverse(int index)
{
    if (vec[index][0] != -1)
        PostorderTraverse(vec[index][0]);
    if (vec[index][1] != -1)
        PostorderTraverse(vec[index][1]);
    cout << (char)(index + 'A');
}