[C/C++] 백준 #1991 트리순회(깊이 우선 탐색)

트리를 순회하는 방법은 크게 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있습니다.

깊이 우선 탐색은 스택(또는 재귀호출)을 이용하고 너비 우선 탐색은 큐를 사용하죠.  그런데, 깊이 우선 탐색의 경우에는 방문을 했다는 표시를 하는 방법에 따라서 전위(pre), 중위(in), 후위(post) 탐색으로 나눌 수 있습니다.

 

preorder, inorder, postorder

 

이번문제는 깊이 우선 탐색에서 전위, 중위, 후위 탐색의 결과를 출력하는 것입니다.  이 세가지 방법은 사실 기본적으로 호출하는 것은 똑같지만, 언제 방문 여부를 표시하는가에 따라서 다를 뿐입니다.

 

각각의 탐색 방법에 따라 함수를 따로 만드는 것이 시간상으로 더 효율적이겠지만, 저는 하나의 함수로 작성해보았습니다.  이 방법이 좋다는 것은 아니지만, 세가지 탐색 방법을 알아보기 좋게 프로그램한 것이라고 생각합니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1991
//        - by Aubrey Choi
//        - created at 2019-07-07
//------------------------------------------------
#include <stdio.h>

void traverse(char tree[][3], int r, int s)
{
    if(r == -1) return;
    if(s == 0) putchar(tree[r][0]);
    traverse(tree, tree[r][1], s);
    if(s == 1) putchar(tree[r][0]);
    traverse(tree, tree[r][2], s);
    if(s == 2) putchar(tree[r][0]);
}

int main()
{
    char tree[26][3], P[2], L[2], R[2];
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%s%s%s", P, L, R);
        int p = P[0] - 'A';
        tree[p][0] = P[0];
        tree[p][1] = L[0] == '.' ? -1 : L[0] - 'A';
        tree[p][2] = R[0] == '.' ? -1 : R[0] - 'A';
    }
    traverse(tree, 0, 0); putchar('\n');
    traverse(tree, 0, 1); putchar('\n');
    traverse(tree, 0, 2); putchar('\n');
    return 0;
}