백준 1991번: 트리 순회

✔ 풀이를 위한 아이디어

• 트리 (Tree) 와 재귀 (Recursion)
  
  

✔ 정답 코드

import sys

N = int(input())
BST = {}

for i in range(N):
    pN, lN, rN = sys.stdin.readline().split()
    if i == 0: Root = pN
    BST[pN] = (lN, rN)

def preOrder(data):
    print(data, end="")
    if BST[data][0] != '.':
        preOrder(BST[data][0])
    if BST[data][1] != '.':
        preOrder(BST[data][1])

def inOrder(data):
    if BST[data][0] != '.':
        inOrder(BST[data][0])
    print(data, end="")    
    if BST[data][1] != '.':
        inOrder(BST[data][1])
        
def postOrder(data):
    if BST[data][0] != '.':
        postOrder(BST[data][0])    
    if BST[data][1] != '.':
        postOrder(BST[data][1])
    print(data, end="")
    
preOrder(Root)
print()
inOrder(Root)
print()
postOrder(Root)
print()

• 자료구조 수업 과제로 BST ADT를 구현했던 때와는 다르게, 딕셔너리를 활용하여 비교적 심플하게 구현해보았다. 이전에 짰던 코드는 아래의 주소에서 볼 수 있다. (사실 정확히 말자하면, 문제 속 트리와 BST는 다르다)
  https://github.com/ddongseop/datastructure/blob/master/BST/dongseop%20BST.py
• 3가지 순회 모두 기본적인 방식은 비슷하다. left나 right에 값이 있으면 해당 값을 parameter로 넘겨주어 재귀호출을 해나가는 방식이다. 다만, 자신을 출력하는 위치가 코드의 어느 부분에 있는지에 따라 순회의 종류가 달라지게 된다.
  
  

✔ 관련 개념

• Binary Tree Traversals: PreOrder, InOrder, and PostOrder