[백준] 1991번 트리순회 (C++)

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다.
둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.
노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다.
자식 노드가 없는 경우에는 .으로 표현한다.

예제 입력 1

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다.
각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

예제 출력 1

ABDCEFG
DBAECFG
DBEGFCA

풀이

문제 해결 방법

이 문제는 이진 트리의 세 가지 순회 방식을 구현하는 문제입니다. 각 순회 방식의 특징은 다음과 같습니다:

1. 전위 순회(Preorder): 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리
2. 중위 순회(Inorder): 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리
3. 후위 순회(Postorder): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

각 순회는 재귀 함수를 사용하여 구현할 수 있으며, 시간 복잡도는 모든 노드를 한 번씩 방문하므로 O(N)입니다.

코드

#include<stdio.h>

int n;
int child[27][3];
char a,b,c;

void preorder(int node)
{
    if(node==0)return;
    printf("%c",node+'A'-1);
    preorder(child[node][0]);
    preorder(child[node][1]);
}

void inorder(int node)
{
    if(node==0)return;
    inorder(child[node][0]);
    printf("%c",node+'A'-1);
    inorder(child[node][1]);
}

void postorder(int node)
{
    if(node==0)return;
    postorder(child[node][0]);
    postorder(child[node][1]);
    printf("%c",node+'A'-1);
}

int main()
{
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
        scanf(" %c %c %c",&a,&b,&c);
        if(b!='.')
            child[a-'A'+1][0]=b-'A'+1;
        if(c!='.')
            child[a-'A'+1][1]=c-'A'+1;
    }

    preorder(1);
    puts("");
    inorder(1);
    puts("");
    postorder(1);

    return 0;
}