[C++] BOJ 1991번 : 트리 순회

 

 

 

 

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

 

문제 3줄 요약

 

1. 이진 트리의 순회 결과를 출력한다.

2. 전위 / 중위 / 후위 순으로 순회할 것이다.

3. 순회 방법은 순회 결과가 힌트!

 

---

 

학부 수업 때,

트리 순회를 외우려고 친구들과 고민하던 중

친구 한 명이 알려줬던 방법이 기억에 잘 남아서 아직도 잊혀지지 않는다..!

 

그 방법은

트리에 막대기를 붙여서 경로를 이어주는 방법이었다.

 

전위 순회는 막대를 각 노드의 왼쪽,

중위 순회는 막대를 각 노드의 아래쪽,

후위 순회는 막대를 각 노드의 오른쪽에 붙여주고 경로를 이어주면

막대기의 순서가 순회 결과 순으로 된다는 것이었다.

 

예를 들어,

위의 이진 트리의 중위 순회를 해본다면

 

 

막대기는 순회 방식에 따라 다르게 설정해준다.

하지만 경로는 항상 왼쪽 위부터 시작해서

오른쪽으로 한바퀴를 도는 형식으로 돌아준다.

 

그럼 가는 길에 먼저 닿는 막대기 순서는

D - B - A - E - C - F - G

이다.

 

위의 문제와 좀 관계 없는 이야기였지만,,

나름 유용하게 써먹고 있던 기억 중에 하나라 적어봤다.

 

 

다시 문제로 돌아와서

문제에서 순회 방식 간의 코드 차이는

 

알파벳 / 알파벳의 좌측 자식 / 알파벳의 우측 자식

 

이 3가지 중 무엇을 먼저 방문 처리 해주느냐에

전위 / 중위 / 후위가 달라진다.

 

아까 위에 예시로 봤던

중위 순회 (In-order) 부터 살펴보면 쉽게 이해할 수 있다.

 

결국엔

가장 좌측에 있는 자식부터 방문하고

그다음 올라오면서 부모 알파벳들을 방문 처리 해주고

그 다음 우측이다.

 

그래서

문제 요약 3번

 

 

순회 결과의 우측에 써있는 것이

방문 처리 순서라고 보면 되겠다.

 

아래에는 필자의

재귀 DFS로 구현한 순회 코드이다.

 

void preorder(int n)
{
    cout << char(n+65);
    if(lc[n] != '.') preorder(lc[n]-65);
    if(rc[n] != '.') preorder(rc[n]-65);
}

void inorder(int n)
{
    if(lc[n] != '.') inorder(lc[n]-65);
    cout << char(n+65);
    if(rc[n] != '.') inorder(rc[n]-65);
}

void postorder(int n)
{
    if(lc[n] != '.') postorder(lc[n]-65);
    if(rc[n] != '.') postorder(rc[n]-65);
    cout << char(n+65);
}

 

좌측 / 우측 자식들은 배열에 담아서

부모 노드의 인덱스에 따라 자식들을 접근할 수 있게 작성하였다.

 

- 65를 해주는 것은 알파벳을

A부터 0, B는 1 ... 이 순으로 인덱스를 설정하기 위해

대문자 A의 아스키 코드 값인 65를 빼준 것이다.

 

그 이 외에는

자식이 있을 때만 재귀 호출을 하는 것 말곤 순회 간 자식 호출 순서만 다르다.

 

아래는 전체 코드이다.

 

#include <iostream>

char lc[27];
char rc[27];

using namespace std;

void preorder(int n)
{
    cout << char(n+65);
    if(lc[n] != '.') preorder(lc[n]-65);
    if(rc[n] != '.') preorder(rc[n]-65);
}

void inorder(int n)
{
    if(lc[n] != '.') inorder(lc[n]-65);
    cout << char(n+65);
    if(rc[n] != '.') inorder(rc[n]-65);
}

void postorder(int n)
{
    if(lc[n] != '.') postorder(lc[n]-65);
    if(rc[n] != '.') postorder(rc[n]-65);
    cout << char(n+65);
}

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n;
    cin >> n;


    while(n--)
    {
        char P, L, R;
        cin >> P >> L >> R;
        int index = (P-65);
        lc[index] = L;
        rc[index] = R;
    }
    preorder(0);
    cout << "\n";
    inorder(0);
    cout << "\n";
    postorder(0);

    return 0;
}

 

---

 

트리 문제는

기존의 BFS 또는 DFS에 vector를 통한 다음 노드 지정이 아닌

배열을 통한 자식 노드 탐색하는 방식인 것이 흥미로웠다.

 

끝!