트리 순회 - 전위 순회, 중위 순회, 후쉬 순회

전위 순회(pre-order)

• 루트 -> 왼쪽 자식 -> 오른쪽 자식

 

중위 순회(in-order)

• 왼쪽 자식 -> 루트 -> 오른쪽 자식
• x축 기준 왼쪽부터 출력

 

후위 순회(post-order)

• 왼쪽 자식 -> 오른쪽 자식 -> 루트

 

연습 문제

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

1991번: 트리 순회

 

코드

위에서 설명한 각 순회별 루트, 왼쪽 노드, 오른쪽 노드 방문 순서를 생각해 
재귀를 통해 구현해내면 아주 쉽게 구현할 수 있다.

class Node:
  def __init__(self, data, left, right):
    self.data = data
    self.left = left
    self.right = right

def pre_order(node):
  print(node.data, end='')
  if node.left != '.':
    pre_order(tree[node.left])
  if node.right != '.':
    pre_order(tree[node.right])

def in_order(node):
  if node.left != '.':
    in_order(tree[node.left])
  print(node.data, end='')
  if node.right != '.':
    in_order(tree[node.right])

def post_order(node):
  if node.left != '.':
    post_order(tree[node.left])
  if node.right != '.':
    post_order(tree[node.right])
  print(node.data, end='')

N = int(input())
tree = {}
for _ in range(N):
  data, left, right = input().split()
  tree[data] = Node(data, left, right)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])