[알고리즘] 트리 순회 (전위, 중위, 후위)와 중위+후위 -> 전위 순회 찾기

 트리 순회는 가장 기본적인 알고리즘인 DFS에 바탕을 두고 있다. DFS는 함수 스택을 이용한 재귀 호출로 구현하며, 스택이라는 특징을 바탕으로 트리를 순회할 수 있다.

 트리 순회는 트리의 특성과 DFS를 묻는 가장 기초적인 내용이다. 트리 순회 방법으로는 전위 / 중위 / 후위 순회가 있으며, 이는 각각 부모와 좌, 우의 자식 노드가 있을 때, 어느 노드부터 출력할 것인가에 대한 방식이다.

 전위 순회는 [부모 / 좌 / 우] 순서이며, 중위 순회는 [ 좌 / 부모 / 우 ] 그리고 후위 순회는 [ 좌 / 우 / 부모 ] 순서로 출력한다. 즉 부모(루트)의 출력 순서에 따라 나뉘게 된다.

 이러한 순서를 출력하는 것은 DFS의 출력 위치에 따라서 간단하게 구현할 수 있다. DFS(X)는 루트 X에 대하여 DFS(L(X))와 DFS(R(X))를 호출하게 되는데, 이 호출 전/중/후에 출력하는 함수를 위치하면 순회 값을 얻을 수 있다.

 코드로 보자.  해당 코드는 백준 1991번 트리순회에 기반을 두고 있다.

void preOrder(char x){
    if(x=='.') return;
    printf("%c", x);
    preOrder(h[x][0]);
    preOrder(h[x][1]);
}
void inOrder(char x){
    if(x=='.') return;
    inOrder(h[x][0]);
    printf("%c", x);
    inOrder(h[x][1]);
}
void postOrder(char x){
    if(x=='.') return;
    postOrder(h[x][0]);
    postOrder(h[x][1]);
    printf("%c", x);
}

 

 막상 이러한 순회값을 확인하다 보면, 재미 있는 사실을 알 수 있는데, 전위 순회값과 중위 순회 값 또는 중위 순회와 후위 순회값을 이용하면 나머지 순회 값을 찾을 수 있다. 

  ACM-ICPC에서 기출된 적이 있는 문제로, 다음에 또 나올 가능성은 적지만 divide and conquer 패러다임의 개념으로 한번쯤 풀어보는 것도 좋다.

 

 중위 순회 + 후위 순회으로 전위 순회값 찾기

원리부터 말하자면, 중위 순회는 항상 부모가 중앙에 오고 후위 순회의 경우 항상 부모가 맨 마지막에 온다. 즉, 부분 문제를 배열이 주어졌을 때 부모와 그 자식을 중위, 후위 순회 값에서 뽑아내는 것으로 정하면 된다.

 코드로 보자. 해당 코드는 백준 2263번 트리의 순회에 기반을 두고 있다.

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

int n;
int in[100001];
int post[100001];

int search(int* arr, int x, int st, int en){
    for(int i = st; i < en; i++)
        if(arr[i] == x) return i;
    return -1;
}
void find(int li, int ri, int lp, int rp){
    if(ri == li) return;
    int root = post[rp-1];
    int inRoot = search(in, root, li, ri);
    printf("%d ", root);
    if(inRoot >= 0){
        find(li, inRoot, lp, lp+(inRoot-li));
        find(inRoot+1, ri, lp+(inRoot-li), rp-1);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n ; i++){
        cin >> in[i];
    }
    for(int i = 0; i < n ; i++){
        cin >> post[i];
    }
    find(0, n, 0, n); printf("\n");
}