[data structure/tree] 백준 1991. 트리 순회

 

1991번: 트리 순회

기본 개념

한국어도 직역한 단어지만, 영어로 트리 순회 개념을 이해해두고 넘어가면 쉽다.

트리 순회 개념은 root 노드를 언제 들르냐에 따라 나뉜다.

 

preorder : 먼저 root부터 들르고 왼쪽자식 순회, 그리고 오른쪽 자식 순회

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

inorder : 왼쪽 자식 순회, 그리고 root 방문(왼쪽과 오른쪽 사이의 "in"), 이후 오른쪽 자식 방문

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

postorder : 왼쪽 자식 순회, 오른쪽 자식 순회, 그리고 나서 root 방문

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

 

문제 풀이

위 이해한 내용을 바탕으로 해당 문제에 대한 코드를 작성하면,

import sys
input = sys.stdin.readline

t = int(input())
tree = dict() # {}

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

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

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

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

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