BOJ-1991 트리 순회

https://www.acmicpc.net/problem/1991

문제 소개

이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 각각 출력한다.

• 전위 순회 : 루트 $\rightarrow$ 왼쪽 자식 $\rightarrow$ 오른쪽 자식
• 중위 순회 : 왼쪽 자식 $\rightarrow$ 루트 $\rightarrow$ 오른쪽 자식
• 후위 순회 : 왼쪽 자식 $\rightarrow$ 오른쪽 자식 $\rightarrow$ 루트

노드의 개수인 n이 주어지며, .으로 자식 노드가 없음을 표현한다.

문제 풀이

입력받은 이진 트리는 딕셔너리형태로 저장하였다. 부모 노드가 키, 자식 노드가 값이 되도록 하였다.

각 순회 방식의 정의를 함수로 나타내었다. 함수는 재귀적으로 동작하며, if문을 통해 자식 노드의 유무를 검사한다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()


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


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


# 후위 순회
def postorder(start):
    if d[start][0] != '.':
        postorder(d[start][0])
    if d[start][1] != '.':
        postorder(d[start][1])
    print(start, end='')


# 입력
n = int(input())
d = dict()
for _ in range(n):
    k, a, b = input().split()
    d[k] = [a, b]

# 시작 노드를 A로 하여 동작
preorder('A')
print()
inorder('A')
print()
postorder('A')