[탐색/자료구조] 백준 1991 트리 순회 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1991번: 트리 순회

 

 

2. 문제 풀이

 주어진 트리를 '전위', '중위', '후위' 탐색하는 문제입니다.

 

전위 순회: 중간 -> 왼쪽 -> 오른쪽
중위 순회: 왼쪽 -> 중간 -> 오른쪽
후위 순회: 왼쪽 -> 오른쪽 -> 중간

 자료구조 단골 시험문제죠. "주어진 트리를 전위/중위/후위 순회하시오."

 

 

(좌) 전위, 중위 / (우) 후위

 전위와 중위는 탐색 경로는 같으나, '방문'하는 시점이 다릅니다. '전위'는 루트부터 찍고 왼쪽 오른쪽을 탐색하고, '중위'는 왼쪽부터 탐색하고 중간, 오른쪽으로 탐색합니다.

 '후위'는 왼쪽, 오른쪽, 중간 순서로 탐색합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
tree = {}
for _ in range(n):
    root, left, right = input().rstrip().split()
    tree[root] = [left, right]

# 전위 순회
def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right

# 중위 순회
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right

# 후위 순회
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root

# 출력
preorder('A')
print()
inorder('A')
print()
postorder('A')