Tree 순회

Tree Traversal 정의

트리구조에서 각각의 노드를 정확히 한 번만 방문하는 과정을 말한다. wiki

트리 순회는 그래프 순회와 마찬가지로 DFS 또는 BFS로 탐색한다.
특히 이진 트레에서 DFS는 방문순서에 따라 크게 3가지 방식으로 구분된다/

• 전위 순회 Pre-Order
• 중위 순회 In-Order
• 후위 순회 Post-Order

용어

• N : 현재 노드
• L : N의 왼쪽 서브 트리
• R : N의 오른쪽 서브 트리

순회 방식에 따른 방문 순서

Pre-Order 빨간색 NLR

F -> B -> A -> D -> C -> E -> G -> I -> H

In-Order 초록색 LNR
A -> B -> C -> D -> E -> F -> G -> H -> I

Post-Order 파란색 LRN
A -> C -> E -> D -> B -> H -> I -> G -> F

전위 순회 NLR

1. 현재 노드를 방문한다.
2. 재귀적으로 왼쪽 서브트리를 방문한다.
3. 재귀적으로 오른쪽 서브 트리를 방문한다.

python 구현

def preorder(node):
    if node is None:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

중위 순회 LNR

1. 왼쪽 서브트리를 재귀적으로 방문한다.
2. 현재노드를 방문한다
3. 오른쪽 서브트리를 재귀적으로 방문한다

python 구현

def inorder(node):
  if node is None:
    return
  inorder(node.left)
  print(node.val)
  inorder(node.right)

후위 순회 LRN

1. 왼쪽 서브트리를 재귀적으로 방문한다.
2. 오른쪽 서브트리를 재귀적으로 방문한다.
3. 현재 노드를 방문한다.

python 구현

def postorder(node):
  if node is None:
    return
  postorder(node.left)
  postorder(node.right)
  print(node.val)