트리 순회 알고리즘

트리의 순회는 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미합니다.

대표적인 트리 순회 방법은 전위 순회, 중위 순회, 후위 순회가 있습니다.

위 그림의 트리를 예제로 구현해보겠습니다.

트리 구현을 위해 다음과 같은 클래스를 정의합니다.

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

n = int(input())
tree = {}

for i in range(n):
	data, left, right = input().split()
    if left == "None":
    	left = None
    if right == "None":
    	right = None
    tree[data] = Node(data, left, right)

# 전위 순회 실행 
pre_order(tree['A']) # A는 시작 노드 

전위 순회(pre-order traverse)

: 루트를 먼저 방문합니다.

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

중위 순회(in-order traverse)

: 왼쪽 자식을 방문한 뒤에 루트를 방문합니다.

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

후위 순회(post-order traverse)

: 오른쪽 자식을 방문한 뒤에 루트를 방문합니다.

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