BOJ 1991 - 트리 순회 / C++

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

1991번: 트리 순회

 

 

문제 풀이

저번 포스트에서 map을 이용하여 트리를 구현하는 법을 알아보았다.

트리 구조 - 개념 및 예제

 

이를 이용하여 트리를 구현하고 전위, 중위, 후위 순회를 구현하면 된다.

구현 방법은 재귀를 이용하고 기본 원리는 모두 비슷하다.

트리에서 해당 문자를 찾고 존재한다면 순서에 맞게 순회한다.

리프 노드는 문제의 조건에서 '.'으로 표현된다고 하였다.

순서는 주석을 참고하고 현재 방문한 노드는 출력해주면 된다.

 

소스 코드

#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;

unordered_map<char, pair<char, char> > tree;

void preorder(char c){
    if(tree.find(c) == tree.end()) return;
    else{
        cout << c;
        if(tree[c].first != '.') preorder(tree[c].first);
        if(tree[c].second != '.') preorder(tree[c].second);
    }
    
    return;
}//전위순회 현재->왼쪽->오른쪽 순서로 순회

void inorder(char c){
    if(tree.find(c) == tree.end()) return;
    else{
        if(tree[c].first != '.') inorder(tree[c].first);
        cout << c;
        if(tree[c].second != '.') inorder(tree[c].second);
    }
    
    return;
}//중위순회 왼쪽->현재->오른쪽 순서로 순회

void postorder(char c){
    if(tree.find(c) == tree.end()) return;
    else{
        if(tree[c].first != '.') postorder(tree[c].first);
        if(tree[c].second != '.') postorder(tree[c].second);
        cout << c;
    }
    
    return;
}//후위순회 왼쪽->오른쪽->현재 순서로 순회

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;

    cin >> n;
    for(int i=0; i<n; i++){
        char tmp[3];
        cin >> tmp[0] >> tmp[1] >> tmp[2];
        tree[tmp[0]] = make_pair(tmp[1], tmp[2]);
    }

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