[baekjoon] 백준 1991번(파이썬): 트리 순회

문제

1991번: 트리 순회

알고리즘

- 반복문을 통해 트리를 생성한다.

- 전위 순회, 중위 순회, 후위 순회를 하는 함수를 생성한다.

- 함수를 생성할 때 각 순회에 특징에 따라 루트 노드 출력, 재귀적으로 왼쪽과 오른쪽 탐색을 할 수 있게 한다.

코드

import sys

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

# 반복문을 통해 트리 생성
for i in range(n):
    root, left, right = map(str, sys.stdin.readline().split())
    tree[root] = left, right


# 전위 순회
def preorder(v):
    if v != ".": # 자식이 있다면
        print(v, end="") # 루트 노드 출력
        preorder(tree[v][0]) # 재귀적으로 왼쪽 노드 탐색
        preorder(tree[v][1]) # 재귀적으로 오른쪽 노드 탐색


# 중위 순회
def inorder(v):
    if v != ".": # 자식이 있다면
        inorder(tree[v][0]) # 재귀적으로 왼쪽 노드 탐색
        print(v, end="") # 루트 노드 출력
        inorder(tree[v][1]) # 재귀적으로 오른쪽 노드 탐색


# 후위 순회
def postorder(v):
    if v != ".": # 자식이 있다면
        postorder(tree[v][0]) # 재귀적으로 왼쪽 노드 탐색
        postorder(tree[v][1]) # 재귀적으로 오른쪽 노드 탐색
        print(v, end="") # 루트 노드 출력


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

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법