챕터7-2. 트리 | 순회방법(전위, 중위, 후위)

트리의 순회(Tree Traversal)

- 트리도 그래프이기 때문에 DFS와 BFS 방식 모두 가능하다.
- 그런데 트리에서만 가능한 아래의 3가지 방법이 있다.(각각의 차이는 루트 노드의 방문을 언제 하냐의 차이)
- 이진트리에서는 아래의 3가지 방법이 모두 가능한데, 자식이 여러개인 트리에서는 '프리오더'와 '포스트오더'만 가능하다.
   그 이유는 자식이 여러개인 트리의 경우, '인오더 방식'에서 출력이 어느 부분에 위치해야할지 가늠할 수 없기 때문이다.

                        <이진트리>         <자식이 여러개인 트리>
   프리오더        루트 L R                  루트 children
   인오더            L 루트 R
   포스트오더     L R 루트                  루트 children

# Pre-order(전위순회)
* 그래프의 DFS와 순서가 같음.
   1) 루트노드 방문
   2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀)
   3) 오른쪽 자식 노드를 루트로 하는 서브 트리를 프리오더(재귀)

# In-order(중위순회)
* Binary Search Tree에서 Delete를 구현할 때 인오더를 주로 사용함.
   1) 왼쪽 자식 노드를 루트로 하는 서브 트리를 인오더(재귀)
   2) 루트노드 방문
   3) 오른쪽 자식 노드를 루트로 하는 서브 트리를 인오더(재귀)

# Post-order(후위순회)
* 트리 관련 다이나믹 문제에서 자식이 모두 처리된 다음에 부모노드를 처리하는 방식으로 자주 쓰임
   1) 왼쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더(재귀)
   2) 오른쪽 자식 노드를 루트로 하는 서브 트리를 포스트오더(재귀)
   3) 루트노드 방문

그림으로 보는 위 3가지 방식의 예시1

# Pre-order(전위순회)

# In-order(중위순회)

# Post-order(후위순회)

 

그림으로 보는 위 3가지 방식의 예시2

# Pre-order(전위순회)

 

# In-order(중위순회)

# Post-order(후위순회)