알고리즘💻/트리

BOJ 1991번: 트리 순회

호프 2021. 2. 8. 19:45

www.acmicpc.net/problem/1991

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자

www.acmicpc.net

아이디어:

전위순회, 중위순회, 후위순회를 재귀로 구현하는 기본적인 문제이다.

중간에 if 문으로 '.'이 아닌 것을 확인해야 하는데, 처음에 이걸 print하기 전에만  해놔가지고 index에러가 났었다.

 

import sys

N = int(sys.stdin.readline())
graph = [[]for _ in range(N)]
for _ in range(N):
    node, left, right = sys.stdin.readline().split()
    graph[ord(node)-65] = [left, right]

def preorder(x):
    if (x!='.'):
        print(x, end="")
        xx = ord(x)-65
        preorder(graph[xx][0])
        preorder(graph[xx][1])

def inorder(x):
    if (x!="."):
        xx = ord(x)-65
        inorder(graph[xx][0])
        print(x, end="")
        inorder(graph[xx][1])

def postorder(x):
    if (x!="."):
        xx = ord(x)-65
        postorder(graph[xx][0])
        postorder(graph[xx][1])
        print(x, end="")
preorder('A')
print()
inorder('A')
print()
postorder('A')