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

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

1991번: 트리 순회

 

 

# 조건

 

• 이진 트리를 입력받아 전위 순회, 중위 순회, 후위 순회 한 결과를 출력하여라
• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

 

입력

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

 

# 접근 방법

• 아스키 코드를 이용하여 1~ N번 인덱스에 왼쪽 자식, 오른쪽 자식 노드를 넣어준다.
• 이후, 출력 위치에 따라 전위, 중위, 후위 노드를 기록해주고 출력한다.
• 재귀를 이용하여 자식 노드부터 탐색한다.

import sys  

sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
# 전위 순회
def preorder(node):  
    if tree[node]:  
        print(f'{chr(node + 64)}', end='')  
        if tree[node][0][0] > 0:  
            preorder(tree[node][0][0])  
        if tree[node][0][1] > 0:  
            preorder(tree[node][0][1])  
  
# 중위
def in_order(node):  
    if tree[node]:  
        if tree[node][0][0] > 0:  
            in_order(tree[node][0][0])  
        print(f'{chr(node + 64)}', end='')  
        if tree[node][0][1] > 0:  
            in_order(tree[node][0][1])  
  
# 후위
def post_order(node):  
    if tree[node]:  
        if tree[node][0][0] > 0:  
            post_order(tree[node][0][0])  
  
        if tree[node][0][1] > 0:  
            post_order(tree[node][0][1])  
        print(f'{chr(node + 64)}', end='')  
  
  
N = int(input())  
tree = [[] for _ in range(N + 1)]  
info = [[*map(str, input().split())] for _ in range(N)]  
for i, j, k in info:  
    a, b, c = ord(i) - 64, ord(j) - 64, ord(k) - 64  
    # 부모 노드에 왼쪽 자식, 오른쪽 자식 넣어주기  
    tree[a].append((b, c))  
  
preorder(1)  
print()  
in_order(1)  
print()  
post_order(1)