[알고리즘 수업] 백준 1991번 파이썬

import sys
input = sys.stdin.readline

tree_dict = {}

n=int(input())
for i in range(n):
    root, left, right = input().split()
    tree_dict[root] = [left, right]

def preorder(root):
    if root != '.':
        print(root, end="")
        preorder(tree_dict[root][0])
        preorder(tree_dict[root][1])
def inorder(root):
    if root != '.':
        inorder(tree_dict[root][0])
        print(root, end="")
        inorder(tree_dict[root][1])
def postorder(root):
    if root != '.':
        postorder(tree_dict[root][0])
        postorder(tree_dict[root][1])
        print(root, end="")

preorder("A")
print()
inorder("A")
print()
postorder("A")

핵심 아이디어

1. tree 를 dictionary로 생성하고, root는 key로, left와 right는 value로 둔다.

tree = {}
tree["A"] = "B", "C"

1. 전위순회, 중위순회, 후위순회는 재귀함수를 이용한다.

코드 설명

1. 이진트리 노드의 개수를 n으로 입력받고

2. n만큼 반복하여 root, left, right node를 입력받는다.

3. tree_dict라는 tree를 담을 dictionary를 생성한다.

4. 전위 순회 함수
만약, 노드가 비어있지 않으면(if root != '.')
1. print(root, end="") 해당 루트 노드를 방문하고,
2. preorder(tree_dict[root][0]) 트리의 왼쪽 자식을 방문하는 재귀 함수를 호출한다. 수행 도중 if root != '.' 에 도달하면 재귀 호출을 끝낸다.
3. preorder(tree_dict[root][1]) 트리의 오른쪽 자식을 방문하는 재귀 함수를 호출한다. 수행 도중 if root != '.' 에 도달하면 재귀 호출을 끝낸다.

5. 중위 순회 함수
만약, 노드가 비어있지 않으면(if root != '.')
1. preorder(tree_dict[root][0]) 트리의 왼쪽 자식을 방문하는 재귀 함수를 호출한다. 수행 도중 if root != '.' 에 도달하면 재귀 호출을 끝낸다.
2. print(root, end="") 왼쪽 자식을 모두 탐색했으면 해당 노드를 방문한다.
3. preorder(tree_dict[root][1]) 트리의 오른쪽 자식을 방문하는 재귀 함수를 호출한다. 수행 도중 if root != '.' 에 도달하면 재귀 호출을 끝낸다.

6. 후위 순회 함수
만약, 노드가 비어있지 않으면(if root != '.')
1. preorder(tree_dict[root][0]) 트리의 왼쪽 자식을 방문하는 재귀 함수를 호출한다. 수행 도중 if root != '.' 에 도달하면 재귀 호출을 끝낸다.
2. preorder(tree_dict[root][1]) 트리의 오른쪽 자식을 방문하는 재귀 함수를 호출한다. 수행 도중 if root != '.' 에 도달하면 재귀 호출을 끝낸다.
3. print(root, end="") 왼쪽과 오른쪽 자식을 모두 탐색했으면 해당 노드를 방문한다.