문제 1991.트리 순회 (대학생 심화반 6번)

난이도 :  실버 1

 

문제 요약 설명

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

 

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.

노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

입력 예제

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

// ans
ABDCEFG
DBAECFG
DBEGFCA

 

Tips

1. 해당 문제는 dfs를 사용하면 쉽게 풀리는 문제이다. dfs의 기본 순회 방식이 해당 문제에 나오는 전위 순회이기 때문.
2. 임의의 노드에서 왼쪽 또는 오른쪽 노드로 이동한 후, 도착한 노드 또한 해당 위치에서의 root 노드이다. 즉, 출력은 root 노드만 해줘도 모든 노드를 설정한 순회 순서로 출력이 된다.

 

정답 코드

#include <bits/stdc++.h>

#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

struct node{
    char left;
    char right;
};

map<char, node> tree;

// 전위 순회: (루트) (왼쪽 자식) (오른쪽 자식)
void print_preorder(char root){
    if(root == '.'){
        return;
    }

    cout << root;
    print_preorder(tree[root].left);
    print_preorder(tree[root].right);
}

// 중위 순회: (왼쪽 자식) (루트) (오른쪽 자식)
void print_inorder(char root){

    if(root == '.'){
        return;
    }
 
    print_inorder(tree[root].left);
    cout << root;
    print_inorder(tree[root].right);
}

// 후위 순회: (왼쪽 자식) (오른쪽 자식) (루트)
void print_postorder(char root){

    if(root == '.'){
        return;
    }
 
    print_postorder(tree[root].left);
    print_postorder(tree[root].right);
    cout << root;
}

int main() {
	fastio;
    int N; cin >> N;
    
    char root, left, right;
    char start_node;
    for(int i = 0; i < N; i++){
        cin >> root >> left >> right;
        tree[root] = {left, right};

        if(i == 0) start_node = root;
    }

    print_preorder(start_node);
    cout << '\n';

    print_inorder(start_node);
    cout << '\n';

    print_postorder(start_node);
    cout << '\n';
}

 

참고