[C++] 백준 알고리즘 1991 트리 순회

[C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회 (tistory.com)

[C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회

위 게시글에서 트리의 순회에 대해 알아보았다.

C로 풀었던 트리의 순회를 C++에서는 map을 이용하여 풀 수 있다.

 

map은 파이썬에서의 딕셔너리와 비슷한 자료구조이다. key - value 쌍으로 저장이 되며, key 값을 정렬된 상태로 저장한다.

pair라는 것도 있는데, 이것은 두 값을 저장할 수 있다. 이 때에는 pair의 왼쪽 값을 first, 오른쪽 값을 second라고 접근한다.

 

map에 pair를 사용해보자.

map<int, pair<int,int>> tree;

를 쓰면, tree의 key에 특정 값이 들어올 수 있고,

tree[key값].first 를 이용하면 트리의 왼쪽 값을 접근할 수 있다.

first를 이진 트리의 left, second를 이진 트리의 right라고 생각하고 문제를 풀어보자.

 

1991번: 트리 순회 (acmicpc.net)

1991번: 트리 순회

위 문제는 전위, 중위, 후위 순회를 구하는 문제이다.

풀이는 아래와 같다.

#include <iostream>
#include <map>

using namespace std;

map<char,pair<int, int>> tree;

//전위 순회
void preorder(char c){
    if(c=='.')
        return;
    cout<<c;
    preorder(tree[c].first);
    preorder(tree[c].second);
}

//중위 순회
void inorder(char c){
    if(c=='.')
        return;
    inorder(tree[c].first);
    cout<<c;
    inorder(tree[c].second);
}

//후위 순회
void postorder(char c){
    if(c=='.')
        return;
    postorder(tree[c].first);
    postorder(tree[c].second);
    cout<<c;
}

int main(){
    int n;
    char root, left, right;
    cin>>n;
    while(n--){
        cin>>root>>left>>right;
        tree[root].first=left;
        tree[root].second=right;
    }

    //전위 순회
    preorder('A');
    cout<<'\n';

    //중중위 순회
    inorder('A');
    cout<<'\n';

    //후위 순회
    postorder('A');
    cout<<'\n';

}