[백준/Python] (S1) 트리 순회 - 1991

Baekjoon Online Judge의 1991번 트리 순회 문제의 Python풀이입니다.

1991번: 트리 순회

🧠문제 분석

이 문제는 주어진 이진 트리에 대해 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)를 수행하여 결과를 출력하는 것입니다. 

🤔문제 풀이

preorder, inorder, postorder 함수는 각각 전위, 중위, 후위 순회를 수행하는 재귀 함수입니다. 이들은 주어진 노드가 '.' (즉, 없는 노드를 의미)가 아닐 때 해당 노드를 방문하고, 해당 순회 방식에 따라 왼쪽 및 오른쪽 자식 노드를 재귀적으로 방문합니다.
tree 딕셔너리는 각 노드와 그의 왼쪽 및 오른쪽 자식 노드의 관계를 저장합니다.
입력을 통해 주어진 트리 구조에 따라 tree를 구성하고, A 노드(루트 노드)를 시작으로 각 순회 함수를 호출합니다.
각 순회 함수는 방문한 노드를 출력합니다.

💻코드

def preorder(tree, node):
    if node != '.':
        print(node, end="")
        preorder(tree, tree[node][0])
        preorder(tree, tree[node][1])

def inorder(tree, node):
    if node != '.':
        inorder(tree, tree[node][0])
        print(node, end="")
        inorder(tree, tree[node][1])

def postorder(tree, node):
    if node != '.':
        postorder(tree, tree[node][0])
        postorder(tree, tree[node][1])
        print(node, end="")

n = int(input())
tree = {}
for _ in range(n):
    root, left, right = input().split()
    tree[root] = (left, right)

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