[BOJ/백준 1991][C++] 트리 순회

문제

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

백준 1991

 

문제 내용

노드와 해당 노드에 연결된 왼쪽 자식, 오른쪽 자식 정보를 입력받는다.

입력받은 트리의 전위 순회, 중위 순회, 후위 순회 결과를 출력하면 된다.

 

문제 풀이

구현은 둘째 치고, 트리의 순회에 대해 알고 있는 것이 더 중요하다.

트리의 순회는 아래와 같이 재귀적으로 구현할 수 있다.

1. 전위 순회

1. 현재 정점을 방문
2. 왼쪽 서브 트리를 전위 순회
3. 오른쪽 서브 트리를 전위 순회

**) 전위 순회는 dfs의 방문 순서와 동일하다

2. 중위 순회

1. 왼쪽 서브 트리를 중위 순회
2. 현재 정점을 방문
3. 오른쪽 서브 트리를 중위 순회

**) 이진 탐색 트리라면, 중위 순회를 돌렸을 때 크기 순으로 출력이 된다.

3. 후위 순회

1. 왼쪽 서브 트리를 후위 순회
2. 오른쪽 서브 트리를 후위 순회
3. 현재 정점을 방문

 

코드

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

int n;
int lc[27]; // a가 1번
int rc[27];

void preOrder(int node) {
    if (node == 0)
        return;
    cout << (char)(node + 'A' - 1);
    preOrder(lc[node]);
    preOrder(rc[node]);
}

void inOrder(int node) {
    if (node == 0)
        return;
    inOrder(lc[node]);
    cout << (char)(node + 'A' - 1);
    inOrder(rc[node]);
}

void postOrder(int node) {
    if (node == 0)
        return;
    postOrder(lc[node]);
    postOrder(rc[node]);
    cout << (char)(node + 'A' - 1);
}

int main() {
    cin >> n;

    char alpha, l, r;
    for (int i = 0; i < n; i++) {
        cin >> alpha >> l >> r;
        if (l != '.')
            lc[(alpha - 'A' + 1)] = (l - 'A' + 1);
        if (r != '.')
            rc[(alpha - 'A' + 1)] = (r - 'A' + 1);
    }

    preOrder(1);
    cout << "\n";
    inOrder(1);
    cout << "\n";
    postOrder(1);
}