[백준 1991 파이썬] 트리 순회 (실버 1, 트리)

알고리즘 유형 : 트리 순회
풀이 참고 없이 스스로 풀었나요? : 학습

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
tree = {}
for _ in range(N):
    parent, left, right = input().split()
    tree[parent] = (left, right)

# 전위 순회
def preorder(parent):
    if parent == ".":
        return ""
    left, right = tree[parent]
    left_travel = preorder(left)
    right_travel = preorder(right)
    return parent + left_travel + right_travel

# 중위 순회
def inorder(parent):
    if parent == ".":
        return ""
    left, right = tree[parent]
    left_travel = inorder(left)
    right_travel = inorder(right)
    return left_travel + parent + right_travel

# 후위 순회
def postorder(parent):
    if parent == ".":
        return ""
    left, right = tree[parent]
    left_travel = postorder(left)
    right_travel = postorder(right)
    return left_travel + right_travel + parent
    
print(preorder("A"))
print(inorder("A"))
print(postorder("A"))

풀이 요약

1. 전위 순회는 임의의 한 노드에 대해, 본인을 먼저 탐색하고, 이 후 왼쪽 서브트리를 탐색하고, 그 다음 오른쪽 서브트리를 모두 탐색한다.

   서브트리를 모두 탐색하는 과정도 루트 노드를 먼저 탐색 후, 왼쪽 서브트리, 오른쪽 서브트리를 탐색한다. 탐색의 형태가 재귀적인 형태를 띠므로, 재귀를 이용해서 순회 코드를 쉽게 작성할 수 있다.

   이는 중위 순회, 후위 순회 모두 마찬가지이다.

2. 우선 함수의 리턴 값은 인자로 받은 parent와 왼쪽 서브트리, 오른쪽 서브트리를 순회한 순서 값 문자열이다.

   따라서, 종료 조건으로서, 호출된 함수의 인자 parent가 "." 일 때, 빈 문자열을 반환한다. 애초에 존재하지 않는 노드를 뜻하는 값으로 정했으므로 탐색 자체가 일어나지 않아야하기 때문이다.

배운 점, 어려웠던 점

• 아직 재귀에 조금 미숙하다는 것을 느꼈다. 재귀와 같이 반복되는 구조를 파악하고, 종료 조건과 리턴 값을 제대로 설정하는 연습을 많이 해야겠다.