[백준1991&파이썬] 파이썬에서 이진트리의 전위,중위,후위 간단히 수행해보자.

# 문제

백준 1991 트리 순회 파이썬 풀이

1991번: 트리 순회

# 코드

import sys
from collections import defaultdict

N = int(sys.stdin.readline().strip())
graph = defaultdict(lambda : defaultdict(str))
LEFT = 1
RIGHT = -1

for _ in range(N) :
  parent, left, right = sys.stdin.readline().split()
  if left != "." :
    graph[parent][LEFT] = left
  if right != "." :
    graph[parent][RIGHT] = right

def left(node) :
  return graph[node][LEFT]

def right(node) :
  return graph[node][RIGHT]

def preorder(cur) :
  l = left(cur)
  r = right(cur)
  # ----------- #

  print(cur,end="")
  if l != "" :
    preorder(l)

  if r != "" :
    preorder(r)

def inoredr(cur) :
  l = left(cur)
  r = right(cur)
  # ----------- #


  if l != "":
    inoredr(l)
  print(cur,end="")
  if r != "":
    inoredr(r)

def postorder(cur) :
  l = left(cur)
  r = right(cur)
  # ----------- #

  if l != "":
    postorder(l)
  if r != "":
    postorder(r)
  print(cur, end="")

preorder("A")
print()
inoredr("A")
print()
postorder("A")

# 풀이

• 이진 트리를 입력받아 구성해야 하기 때문에 어떠한 식으로 트리를 구성할지, 그에대한 자료구조를 정해야 한다.
• 먼저 전위,중위,후위 수식의 경우 재귀를 사용하여 푸는 문제이기 때문에 이 구조를 이해하고 있어야 한다.
• 부모노드와 부모 노드의 LEFT, RIGHT만을 표현 할 수 있으면 되고, 해당 노드가 존재하지 않는 경우를 생각하면 된다.
• 딕셔너리를 사용하여 풀이가 가능할것 같았고, defaultdict을 두번 사용하여 해결할 수 있다.
• 딕셔너리 안에 또 다시 딕셔너리를 담아야 하기 때문에 아래와 같이 graph를 선언해준다.

graph = defaultdict(lambda : defaultdict(str))

• 정해진 재귀의 방법에 따라 순서대로 방문한다.