[C언어 백준 풀이] 1991번 : 트리 순회 (preorder, inorder, postorder 차이)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 Class 4에 해당하는 문제인 1991번 : 트리 순회의 풀이 코드와 해설을 다루고 있습니다.

 

이번에는 '트리 순회' 문제를 풀이하며 효율적인 데이터 구조를 설계하기 위해 반드시 필요한 요소 중 하나인 트리의 순회 과정들의 종류와 그 차이점에 대해 다루어보도록 하겠습니다.

 

 

1991번 : 트리 순회

 

위의 그림과 같이 노드들의 연결 관계가 상위 노드와 하위 노드들로 구성된 노드들의 집합을 트리라고 합니다.

이 트리에 대한 입력이 각 노드의 이름과 왼쪽 자식, 오른쪽 자식의 입력을 통해 수행된다고 할 때, 입력받은 트리를 구성하고 이들에 대한 3가지 순회에 대한 결과를 출력하는 문제입니다.

 

Binary 트리의 순회에는 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)가 있습니다.

- 전위 순회(preorder)는 부모 -> 왼쪽 자식 -> 오른쪽 자식 순으로 순회하는 순회 방법입니다.

- 중위 순회(inorder)는 왼쪽 자식 -> 부모 -> 오른쪽 자식 순으로 순회하는 순회 방법입니다.

- 후위 순회(postorder)는 왼쪽 자식 -> 오른쪽 자식 -> 부모 순으로 순회하는 순회 방법입니다.

 

 

가령 제가 임의로 만든 위와 같은 트리가 있을 때, 세 가지 순회 순서는 다음과 같습니다.

- preorder : 1 -> 2 -> 3 -> 4 -> 6 -> 5

- inorder : 2 -> 1 -> 6 -> 4 -> 3 -> 5

- postorder : 2 -> 6 -> 4 -> 5 -> 3 -> 1

 

순서를 자세히 보면 알겠지만 세 가지 방법 모두 재귀적으로 탐색해나가는 과정이기 때문에 재귀함수를 써서 구현합니다.

 

#include <stdio.h>
#define PREORDER 1
#define INORDER 2
#define POSTORDER 3

struct node { char left, right; } tree[30];

void tour(char node, int type) {
    if(node == '.') return;
    if(type == PREORDER) printf("%c", node);
    tour(tree[node-'A'].left, type);
    if(type == INORDER) printf("%c", node);
    tour(tree[node-'A'].right, type);
    if(type == POSTORDER) printf("%c", node);
}

int main() {
    int n;
    char a, b, c;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf(" %c %c %c", &a, &b, &c);
        tree[a-'A'].left = b;
        tree[a-'A'].right = c;
    }
    tour('A', PREORDER);
    printf("\n");
    tour('A', INORDER);
    printf("\n");
    tour('A', POSTORDER);
}

 

풀이는 위와 같고, 트리의 구현을 위해 배열만 사용해도 되지만 코드의 가독성을 위해 구조체를 사용했습니다.

tour 함수는 세 순회 방법의 차이를 가장 간단하게 설명하고 있는데, 단순히 왼쪽, 오른쪽을 탐색하는 순서에 따라 그 순회 방법이 달라진다는 것입니다.

preorder의 경우 부모 노드를 먼저 출력하고 탐색해 나가면 구현이 되며, 반대로 postorder는 모두 탐색이 끝난 뒤 역순으로 출력해나가면 구현이 됩니다.

 

다른 부분보다도 printf 함수와 함수 호출 부분이 어디에 배치되어 있는지를 보시면서 순서에 집중하시면 이해가 더욱 빨리 되실 것입니다.