• 문제: https://www.acmicpc.net/problem/1991

설명

• 입력 값들을 트리에 저장하기 위해 dictionary를 사용한다.
• 입력받은 각 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 값을 각 노드는 key로, 왼쪽 자식 노드와 오른쪽 자식 노드는 리스트로 저장한다.
  ex) {A: [B, C]}
• root가 .이 아닐 때에만, 트리 순회를 재귀 함수로 진행한다. 재귀함수로 깊이 들어가 순회 결과를 출력한다.
  • preorder: root -> left -> right
  • inorder: left -> root -> right
  • postorder: left -> right -> root

코드

from sys import stdin as s

s = open("input.txt", "rt")

N = int(s.readline())

tree = {}
for i in range(N):
    root, left, right = s.readline().split()
    tree[root] = [left, right]

# 전위 순회
def preorder(root):
    if root != '.':
        print(root, end='')			# 루트
        preorder(tree[root][0])		# 왼쪽
        preorder(tree[root][1])		# 오른쪽

# 중위 순회
def inorder(root):
    if root != '.':
        inorder(tree[root][0])		# 왼쪽
        print(root, end='')			# 루트
        inorder(tree[root][1])		# 오른쪽

# 후위 순회
def postorder(root):
    if root != '.':
        postorder(tree[root][0])	# 왼쪽
        postorder(tree[root][1])	# 오른쪽
        print(root, end='')			# 루트

preorder('A')
print()
inorder('A')
print()
postorder('A')
print()