너비 우선 탐색과 깊이 우선 탐색

[순서 트리의 노드 스캔 방법 2가지]

1. 너비 우선 탐색(가로형 탐색)

낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 따라가다가 한 레벨에서 탐색이 끝나면 다음 레벨로 내려간다.

---

2. 깊이 우선 탐색(세로형 탐색)

- 리프에 이를 때까지 아래로 내려가며 탐색. 리프에 도달해 더 이상 탐색할 곳이 없으면 부모에게 돌아갔다가 다시 자식 노드로 내려간다.

- 깊이 우선 탐색을 진행하면 노드를 몇 번 지나갔는지 확인할 수 있다.

- ‘언제 노드를 방문할지’에 따라 3종류로 구분된다.

 

1. 전위 순회 : 노드 방문 > 왼쪽 자식 > 오른쪽 자식

A → B → D → H → E → I → J → C → F → K → L → G

 

2. 중위 순회 : 왼쪽 자식 > 노드 방문 > 오른쪽 자식

H → D → B → I → E → J → A → K → F → L → C → G

3. 후위 순회 : 왼쪽 자식 > 오른쪽 자식 > (돌아와) 노드 방문

H → D → I → J → E → B → K → L → F → G → C → A