[알고리즘/파이썬] 백준 1191 - 트리순회

문제

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

1991번: 트리 순회

 

풀이

트리 순회에 대한 기본적인 문제다. 전위 중위 후위 다 까먹고 있었는데 오랜만에 기억을 더듬더듬.. 하니 좋았다.

트리는 딕셔너리 형태로 구현했다. 트리의 순회는 일정한 기준으로 왼쪽 먼저 순회라면 왼쪽을 다 순회한 후 다음 노드를 순회한다. 따라서 재귀를 통해 원하는 부분 먼저 끝까지 순회할 수 있게끔 해줘야 한다.

 

코드

N = int(input())
tree = {}
 
for n in range(N):
    root, left, right =input().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')