백준: 1991 트리 순회

문제

1991번: 트리 순회

 

문제 풀이

 트리를 순회하는 것은 깊이 우선으로 탐색하므로 재귀 호출을 사용하면 쉽게 구현할 수 있다. 재귀 호출을 언제 할지 구현하면 전위, 중위, 후위 순회를 할 수 있다. 즉, 재귀 호출을 할 때 부모를 언제 출력하느냐에 따라 순회 방법이 달라진다. 순회하는 방법은 아래와 같다.

 

• 전위 순회 : 부모 → 왼쪽 자식 → 오른쪽 자식
• 중위 순회 : 왼쪽 자식 → 부모 → 오른쪽 자식
• 후위 순회 : 왼쪽 자식 → 오른쪽 자식 → 부모

 

코드

from sys import stdin


def traversal(cur_node, order):
    left, right = graph[cur_node].values()

    if order == 'pre':
        print(cur_node, end='')
    if left != '.':
        traversal(left, order)
    if order == 'in':
        print(cur_node, end='')
    if right != '.':
        traversal(right, order)
    if order == 'post':
        print(cur_node, end='')


if __name__ == '__main__':
    n = int(stdin.readline())
    graph = dict()
    for _ in range(n):
        node, left, right = stdin.readline().split()
        graph[node] = {'l': left, 'r': right}

    for order in ('pre', 'in', 'post'):
        traversal('A', order)
        print()