[c++ | 백준] 1991번 트리 순회

c++ 문제풀이

 

 

 

---

 

 

 

[백준 1991번 트리 순회 문제]

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

 

 

 

---

 

풀이 코드

#include <map>
#include <iostream>
using namespace std;

void preorder(char c);
void inorder(char c);
void postorder(char c);
map<char, pair<char, char>> m;

int main(void)
{
    int n;
    char parent, left, right;

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> parent >> left >> right;
        m[parent] = make_pair(left, right);
    }

    preorder('A');
    cout << '\n';
    inorder('A');
    cout << '\n';
    postorder('A');

    return 0;
}

void preorder(char c) // 전위
{
    cout << c;
    if (m[c].first != '.')
        preorder(m[c].first);
    if (m[c].second != '.')
        preorder(m[c].second);
}

void inorder(char c) // 중위
{
    if (m[c].first != '.')
        inorder(m[c].first);
    cout << c;
    if (m[c].second != '.')
        inorder(m[c].second);
}

void postorder(char c) // 후위
{
    if (m[c].first != '.')
        postorder(m[c].first);
    if (m[c].second != '.')
        postorder(m[c].second);
    cout << c;
}

 

map으로 입력을 받아 값을 저장한 뒤 전위, 중위, 후위 순회를 재귀함수로 구현했습니다. 전위는 부모 -> 왼쪽자식 -> 오른쪽 자식 순으로 순회하기 때문에 부모를 출력한 뒤 자식이 자식을 가지고 있을 수도 있으니 자식들을 순서대로 재귀로 불러줍니다. 따라서 중위는 왼쪽자식 -> 부모 -> 오른자식 순으로, 후위는 왼쪽자식 -> 오른자식 -> 부모 순서이기 때문에 위와 같이 함수를 구현했습니다.

 

재귀를 사용하여 풀면 쉽게 풀리는 문제였습니다!