김덕우

트리 순회는 그래프 순회의 일종으로,

트리 자료구조에서 각 노드를 한 번 방문하는 과정을 말한다.

DFS 또는 BFS로 탐색 하는데,

이진 트리에서 DFS는 노드의 방문 순서에 따라 크게 3가지 방식으로 구분된다.

1. 전위(Pre-Order) 순회(NLR)

현재 노드(N) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순서대로 탐색하는 방식이다

재귀 구조로 구현한 코드와 그래프는 아래와 같다

빨간색 선으로 이어진 순서대로(A - B - D - F - H - I -C -G -J ) 값이 출력된다.

2. 중위(In-Order) 순회

 왼쪽 서브트리(L) -> 현재 노드(N) -> 오른쪽 서브트리(R) 순서대로 탐색하는 방식이다.

출력 순서는 D - B - G -E -H - A -C - I -F 이다

3. 후위(Post-Order) 순회

왼쪽 서브트리(L) -> 오른쪽 서브트리(R) -> 현재 노드(N) 순서대로 탐색하는 방식이다.

출력 순서는 D - G - H - E - B - I - F -C -A 순서이다.

트리 순회의 직관적인 이해가 필요한 사람은 아래 영상을 참조해도 좋겠다.

https://www.youtube.com/watch?v=bOZhvOc5xlQ&t=223s