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

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

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

이번 문제는 tree traversal (트리 순회) 문제이다.

 

트리 순회에는 문제에서 요구하는 데로 3가지 방법이 있다.

1. preorder traversal (전위 순회)

2. inorder traversal (중위 순회)

3. postorder traversal (후위 순회)

 

트리에서 각각의 순회 방법에 따른 출력 방법 또한 문제에서 주어진 것처럼 아래와 같다.

1. preorder traversal -> (root) (left child) (right child)

2. inorder traversal -> (left child) (root) (right child)

3. postorder traversal -> (left child) (right child) (root)

 

여기서 left child와 right child에 해당하는 부분은 각각 주어진 tree의 subtree로써 left child와 right child가 root가 되는 subtree에 해당한다. 그리고 left subtree와 right subtree에서 같은 순회 방법을 반복해서 사용하는 것이다.

 

import sys

sys.setrecursionlimit(10**6)

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

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

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

n = int(input())
tree = {}

# make tree
for _ in range(n):
    root, left, right = input().split()
    tree[root] = (left, right)

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

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다