[백준 파이썬] 1991 트리순회

 

1991번: 트리 순회

문제

트리를 전위, 중위, 후위 순회한 값을 구하는 문제이다.

---

 

아이디어

이진 트리는 각각 root와 자식이 존재하는 트리이다. 따라서 key-value를 이용할 수 있겠다고 생각했다.

root를 key로 자식을 value로 입력받으면 root에 따른 자식을 쉽게 구할 수 있기 때문이다.

---

풀이

tree = {}

for i in range(N):
    root, left, right = map(str, input().split())
    tree[root] = [left, right]  # key value로 저장

tree = {} 로 dicionary로 초기화 한 후 root에 따른 자식을 입력받았다.

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


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


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

이후 전위 순회, 중위 순회, 후위 순회에 따른 함수를 정의했다.

전위순회의 경우 root의 값을 출력 후 왼쪽 자식부터 순회하도록 하였다.

중위순회의 경우 왼쪽순회 후 root 출력 후 오른쪽 자식 순회를 순서로 하였고,

후위순회의 경우 왼쪽, 오른쪽 자식을 순회한 후 root를 출력하게 하였다.

---

코드

N = int(input())

tree = {}

for i in range(N):
    root, left, right = map(str, input().split())
    tree[root] = [left, right]  # key value로 저장


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


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


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


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

첫 root는 A라고 했으므로 모든 함수에 A를 넣고 출력하였다.