[BOJ/Python] 1991 : 트리 순회

👉 문제 링크

👉 트리 순회

트리의 모든 노드들을 방문하는 과정

• 전위 순회 : 0 1 3 7 8 4 9 10 2 5 11 6
• 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6
• 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0

👉 알고리즘

• 전위 순회

def preorder(node):
    if node == '.':
        return
    print(node, end='') #root
    preorder(tree[node][0]) #left 
    preorder(tree[node][1]) #right

• 중위 순회

def inorder(node):
    if node == '.':
        return
    inorder(tree[node][0]) #left
    print(node, end='') #root
    inorder(tree[node][1]) #right

• 후위 순회

def postorder(node):
    if node == '.':
        return
    postorder(tree[node][0]) #left
    postorder(tree[node][1]) #right
    print(node, end='') #root

👉 전체 코드

import sys
input = sys.stdin.readline

n =  int(input())
tree = {}

for _ in range(n):
    root, left, right = map(str, input().split())
    tree[root] = [left, right]

# 전위순회
def preorder(node):
    if node == '.':
        return
    print(node, end='')
    preorder(tree[node][0])
    preorder(tree[node][1])

# 중위순회
def inorder(node):
    if node == '.':
        return
    inorder(tree[node][0])
    print(node, end='')
    inorder(tree[node][1])

# 후위순회
def postorder(node):
    if node == '.':
        return
    postorder(tree[node][0])
    postorder(tree[node][1])
    print(node, end='')

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