[그래프] 백준 1991. 트리 순회 (전위 순회, 중위 순회, 후위 순회)

문제

트리 순회 출력하기

+ 순회란, 노드와 간선(방향)으로 이루어진 트리를 어떤 순서로 탐색하는 지를 말한다.

 이진 트리의 경우 꼭 가계도처럼 생겼는데, 가지의 상위에 있는 정점(노드)을 부모 노드라고 하고, 아래에 딸려있는 노드들이 짜-식들이다. 전위 순회는 기본적으로 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 탐색한다. 중위 순회는 왼쪽자식 -> 부모 -> 오른쪽 자식, 후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 부모 순이다.

 

제일 깊은 데까지 가서 출력하는데, 진행 경로를 선으로 이어서 그려보면 이해하기 쉽다.

 

import sys
sys.stdin = open('input.txt','rt')
input = sys.stdin.readline





n = int(input())
dic = {}
for i in range(n):
    a, l, r = map(str, input().split())
    dic[a] = [l,r]

# 전위 순회
def preorder(s):
    if s != '.':
        print(s, end = '')
        preorder(dic[s][0])
        preorder(dic[s][1])
        return

# 중위 순회
def inorder(s):
    if s != '.':
        inorder(dic[s][0])
        print(s, end = '')
        inorder(dic[s][1])
    return

# 후위 순회
def postorder(s):
    if s != '.':
        postorder(dic[s][0])
        postorder(dic[s][1])
        print(s, end = '')
    return
    
preorder('A')
print()
inorder('A')
print()
postorder('A')

함수 호출할 때, for문 안에서 돌릴뻔했다... 가장 최상단의 root는 'A'로 고정이기 때문에 A를 기준으로 호출하면 된다.