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

문제

1991번: 트리 순회 (acmicpc.net)

1991번: 트리 순회

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

예제 입력

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력

ABDCEFG
DBAECFG
DBEGFCA

소스코드

import sys
 
N = int(sys.stdin.readline().strip())
tree = {}
 
for n in range(N):
    root, left, right = sys.stdin.readline().strip().split()
    tree[root] = [left, right]
 
 
def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right
 
 
def inorder(root):
    if root != '.':
        inorder(tree[root][0])  # left
        print(root, end='')  # root
        inorder(tree[root][1])  # right
 
 
def postorder(root):
    if root != '.':
        postorder(tree[root][0])  # left
        postorder(tree[root][1])  # right
        print(root, end='')  # root
 
 
preorder('A')
print()
inorder('A')
print()
postorder('A')

트리를 사전으로 간단하게 관계만 표현했다.

{ A : [B, C] } 이런식으로

 

트리 순회는 재귀 함수로 진행 할 수 있다.

preorder는 root->left->right 순으로,

inorder는 left->root->right 순으로,

postorder는 left->right->root 순으로 출력하도록 하면 된다.

 

root가 '.'이 아닐때만 수행하고, root는 출력 left는 다시 함수에 넣어 실행시키는 것이 큰 틀이다.