백준 1991번 "트리순회"

백준 1991번 “트리순회”

Question:

이진 트리를 입력받아
전위 순회(preorder traversal),
중위 순회(inorder traversal),
후위 순회(postorder traversal)한 결과를
출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

Input:

첫째 줄에는
이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다.
둘째 줄부터
N개의 줄에 걸쳐
각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.
노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며,
항상 A가 루트 노드가 된다.
자식 노드가 없는 경우에는 .으로 표현한다.

Output:

첫째 줄에 전위 순회,
둘째 줄에 중위 순회,
셋째 줄에 후위 순회한 결과를 출력한다.
각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

Restriction:

시간제한:
2 초

Example Case:

Input case 1:

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

Output case 1:

ABDCEFG
DBAECFG
DBEGFCA

풀이 과정:
크리스마스날에 다루는 “트리” 순회이다.
애인이 없어서 슬프지만 대신 재밌는 트리순회를 살펴보자…

이 문제는 기본적인 트리 순회를 구현하는 문제이다.

트리를 순회하는 방식에는

1. 전위 순회[preorder] (NLR)
2. 중위 순회[inorder] (LNR)
3. 후위 순회[postorder] (LRN)

이 존재한다.
위에는 등장하지 않지만, 트리의 레벨별로 순회하는 레벨 순회도 존재한다(BFS).

각 순회의 이름에 걸맞게,
루트 노드를 방문하는 것의 순서를 나타냈다고 생각하면 된다.

예를 들어, 전위순회란,
루트노트를 방문 한 뒤 => 왼쪽 서브 트리 탐색 => 오른쪽 서브 트리 탐색
순서의 순회방법이다.

여기서는 이진트리를 c++ stl중 하나인 map을 사용하여 표현하였다.

트리를 배열이나 연결리스트 형태로 나타낼 수 있지만,
이 문제에선 map을 사용하였다.
특히, 배열로 이진트리를 나타내는 경우는
힙(우선순위 큐,힙 정렬)을 이용할 때 사용한다.

C++의 STL중 map 이란,
key , value 값 한 쌍을 한 노드안에 저장하는 트리라고 생각하면 된다.
따라서, pair로 저장이 되는데,
first = key / second = value 라고 생각하면 된다.
특히 map STL에서 주목해야할 점은
map이란 헤더를 포함시켜야하고(#include <map>), 자동으로 오름차순으로 내부에서 정렬이 진행되고,
키들의 중복을 허락하지 않는다.

이 문제에서는 트리를 표현하기 위해,
map <char, pair<char,char» tree; 로 선언한 뒤
입력 받은 노드들의 관계를
tree[node].first = 왼쪽 자식 노드,
tree[node].second = 오른쪽 자식 노드로 표현하였다.

즉, 한 Node = key라고 생각하게 되면,
value 값 자체를 pair로 두어 이진트리를 표현한 것이다.

아래는 소스코드이다.

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

map <char,pair<char,char>> tree; //tree => map 

// pre,in,postorder are showing node's order
void preorder(char node) {
    cout << node << "";
    if(tree[node].first != '.') {
        preorder(tree[node].first);
    }
    if(tree[node].second != '.') {
        preorder(tree[node].second);
    }
}

void inorder(char node) {
    if(tree[node].first != '.') {
        inorder(tree[node].first);
    }
    cout << node << "";
    if(tree[node].second != '.') {
        inorder(tree[node].second);
    }
}

void postorder(char node) {
    if(tree[node].first != '.') {
        postorder(tree[node].first);
    }
    if(tree[node].second != '.') {
        postorder(tree[node].second);
    }
    cout << node << "";
}


int main() {
    int N;
    cin >> N;
    char a,b,c; //tree[a].first = b tree[a].second = c (left/right node)
    for(int i = 0;i<N;i++) {
        cin >> a >> b >> c;
        tree[a] = make_pair(b,c); //tree node input
    }
    preorder('A');
    cout << endl;
    inorder('A');
    cout << endl;
    postorder('A');
}

• 백준
• 문제풀이
• 알고리즘