알고리즘 설계 실습 - 트리 순환

---

문제

위의 문제처럼 트리를 만들고 preorder, inorder, postoder함수를 짜서 실행시켜보면되는 단순한 문제이다. 이전에 자료구조론 수업을 들을 때 C++로 몇날 몇일을 고생하면서 B트리를 설계했던 기억이 있는데 비교적 간단한 트리 순환 문제였다.

import sys
input = sys.stdin.readline

# 입력 받기
N = int(input())

# 빈 트리 정의
tree = {}

for n in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left, right]

# preorder
def preorder(root):
    if root != '.':
        print(root, end='')      # 일단 출력
        preorder(tree[root][0])  # 왼쪽 노드 탐색
        preorder(tree[root][1])  # 오른쪽 노드 탐색

#inorder
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # 왼쪽 노드 탐색
        print(root, end='')       # 왼쪽 자식 탐색후에 출력
        inorder(tree[root][1])  # 오른쪽 노드 탐색


# postorder
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # 왼쪽 노드 탐색
        postorder(tree[root][1])  # 오른쪽 노드 탐색
        print(root, end='')       # 자식이 아예 없으면 출력

#list(tree.keys())[0]을 통해 루트를 찾음
preorder(list(tree.keys())[0])
print()
inorder(list(tree.keys())[0])
print()
postorder(list(tree.keys())[0])
print()

전위, 중위, 후위 순환 그 이름대로 root를 어떤 순서에 출력할지만 결정해주면서 왼쪽 노드와 오른쪽 노드를 서치해 들어가면 자동으로 정렬이 되어 출력이 되었다. 트리 구조는 딕셔너리 구조로 짜주어 {'A': ['B', 'C'], 'B': ['D', '.'],.....} 이런 형태로 parent와 child를 연결 시켜 두었다. 알고보면 엄청나게 쉬워 보이는 알고리즘이지만 잘하는 친구들도 수업시간에 고생하는 것을 보니. 이전에 머리 박으면서 B-tree 구조와 traversal을 설계해보지 않았다면 이런 컨셉이 쉽게 떠오르지 않았을 것 같다. 결론은 무의미한 고생은 없다!

---