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

문제

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

풀이

• 이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력

전위 순회란?

루트 노드를 먼저 방문하고 왼쪽 자식 노드를 순회한 후 오른쪽 자식 노드를 순회하는 방식

루트 -> 왼쪽 자식 -> 오른쪽 자식 순입니다.

루트 'A' -> 왼쪽 자식 'BDE' 서브트리 -> 오른쪽 자식 'CFG' 서브트리 순으로 순회를 하는 것이죠
서브트리 안에서도 전위 순회 방식대로 적용하면,
루트 'B' -> 왼쪽 자식 'D' -> 오른쪽 자식 'E'
루트 'C' -> 왼쪽 자식 'F' -> 오른쪽 자식 'G'

이걸 풀게 되면, A->B->D->E->C->F->G가 됩니다.

중위 순회나 후위 순회도 이런 방식으로 똑같이 진행됩니다.

중위 순회란?

왼쪽 자식 노드를 먼저 순회하고, 루트 노드를 방문한 후 오른쪽 자식 노드를 순회하는 방식

후위 순회란?

왼쪽 자식 노드를 먼저 순회하고, 오른쪽 자식 노드를 순회한 후 루트 노드를 방문하는 방식

---

순회에 대해서 알아봤으니 구현을 시작해 보겠습니다.

루트 노드에 자식 노드(왼쪽, 오른쪽) 2개만 받으면 되니 이를 연결하기 쉽게 하기 위해 딕셔너리를 이용해 풀겠습니다.

if __name__ == "__main__": # 메인문
    n = int(input())
    tree = dict()
    for _ in range(n):
        root, left, right = input().split()
        tree[root] = (left, right)

n번 반복하여 루트 노드, 왼쪽 자식 노드, 오른쪽 자식 노드를 입력 받고, 루트 노드: 왼쪽 자식 노드, 오른쪽 자식 노드 형태로 트리에 입력해줍니다.

순회를 진행할 이진트리를 만들었으니 순회를 시작할게요

def preoder(node):
    if node == '.': # 없을 경우 무시
        return ''
    left, right = tree[node]
    return node + preoder(left) + preoder(right)

전위 순회(루트 -> 왼쪽 자식 -> 오른쪽 자식)

def inorder(node):
    if node == '.': # 없을 경우 무시
        return ''
    left, right = tree[node]
    return inorder(left) + node + inorder(right)

중위 순회(왼쪽 자식 -> 루트 -> 오른쪽 자식)

def postorder(node):
    if node == '.': # 없을 경우 무시
        return ''
    left, right = tree[node]
    return postorder(left) + postorder(right) + node

후위 순회(왼쪽 자식 -> 오른쪽 자식 -> 루트)

루트 노드인 'A'부터 시작하여 출력해주면 끝 🥳

코드

import sys
input = sys.stdin.readline

def preoder(node):
    if node == '.':
        return ''
    left, right = tree[node]
    return node + preoder(left) + preoder(right)

def inorder(node):
    if node == '.':
        return ''
    left, right = tree[node]
    return inorder(left) + node + inorder(right)

def postorder(node):
    if node == '.':
        return ''
    left, right = tree[node]
    return postorder(left) + postorder(right) + node
    
if __name__ == "__main__":
    n = int(input())
    tree = dict()
    for _ in range(n):
        root, left, right = input().split()
        tree[root] = (left, right)
        
    print(preoder('A'))
    print(inorder('A'))
    print(postorder('A'))