트리순회

## 트리순회

- 트리순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한번 방문하는 과정을 말한다.

 

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

 

1. 전위 순회(NLR)

2. 중위 순회(LNR)

3. 후위 순회(LRN)

 

순회 방식의 영문 두문자어를 구성하는 L, R, N 중 L은 현재 노드의 왼쪽 서브트리 R은 현재 노드의 오른쪽 서브트리, N은 현재 노드 자신을 의미한다.

즉 전위 순회는 NLR이므로 현재 노드를 먼저 순회한 다음 왼쪽과 오른쪽 서브트리를 순회하고, 중위 순회는 LNR이므로 왼쪽 서브트리를 순회한 다음 현재 노드 마지막으로 오른쪽 노드, 후회 순회는 LRN이므로 왼쪽과 오른 쪽 서브트리를 순회한 다음 현재 노드를 순회한다.

 

순회 방식 

-  전위 순회: F, B, A, D, C, E, G, I, H

-  중위 순회: A, B, C, D, E, F, G, H, I

-  후위 순회: A, C, E, D, B ,H ,I ,G ,F

 

그렇다면 수도 코드로는 어떻게 표현 될 수 있을까?

 

재귀로 구현할 시 매우 직관적으로 표현할 수 있다.