[알고리즘] 백준 1991번 : 트리 순회

백준 1991번 : 트리 순회 (문제 링크)

• 사용 언어 : 파이썬(Python)
• 문제 유형 : 트리, 구현
• 난이도 : 하

소스코드

import sys

n = int(sys.stdin.readline())

class Node:
    def __init__(self, head, left, right):
        self.head = head
        self.left = left
        self.right = right

tree = dict()

for _ in range(n):
    head, left, right = sys.stdin.readline().split()
    tree[head] = Node(head, left, right)

def pre_order(node):
    print(node.head, end='')
    if node.left != '.':
        pre_order(tree[node.left])
    if node.right != '.':
        pre_order(tree[node.right])
def in_order(node):
    if node.left != '.':
        in_order(tree[node.left])
    print(node.head, end='')
    if node.right != '.':
        in_order(tree[node.right])
def post_order(node):
    if node.left != '.':
        post_order(tree[node.left])
    if node.right != '.':
        post_order(tree[node.right])
    print(node.head, end='')

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

설명

• 트리 구현의 가장 기본이 되는 문제이다.

• 전위, 중위, 후위 순회는 재귀적으로 이루어진다. 이 세가지 방식에 대해 반드시 기억해두자!

  

• 전위 순회 : 루트 → 왼 → 오 / ABDECF

• 중위 순회 : 왼 → 루 → 오 (단순히 x축을 기준으로 트리의 가장 왼쪽 노드부터 차례로 도는 특징이 있다!) / DBEACF

• 후위 순회 : 왼 → 오 → 루 / DEBFCA

• 트리를 구현하는 방법은 다양하지만, 데이터 개수가 적고 간단하게 구현할 때는 위의 코드와 같이 딕셔너리를 이용할 수 있다.