순서 트리 탐색 (너비 우선 탐색 : BFS, 깊이 우선 탐색 : DFS)

순서 트리

 

순서 트리는 각 노드에 순서가 부여된 트리를 말한다.

예를 들어 위와 같은 2개의 트리가 있는 경우

 

무순서 트리에서는 B와 C의 순서가 부여되지 않았기 때문에

 

위 2개의 트리는 동일한 트리이다.

 

하지만 순서 트리에서는 B와 C에 순서가 부여되었기 때문에

 

위 2개의 트리는 다른 트리이다.

---

이진 트리 탐색

 

이진 트리는 순서 트리 중 노드의 자식 노드가 최대 2개인 경우를 말한다.

 

컴퓨터 과학에서 이진 트리를 이용해 값을 탐색하고 이것을 이진 트리 탐색이라고 한다.

 

다음은 이진 트리 탐색 방법 중 너비 우선 탐색과 깊이 우선 탐색에 대해 정리해본다.

---

너비 우선 탐색(Breadth-First Search, BFS)

너비 우선 탐색은 낮은 레벨(깊이)에서 시작해 왼쪽에서 오른쪽 방향으로 탐색하고

 

해당 레벨(깊이)을 모두 탐색하면 다음 레벨(깊이)로 내려가는 방식으로 탐색한다.

 

 

위 예시의 탐색 순서

a -> b -> c -> d -> e -> f  -> g -> h

 

직관적이기 때문에 쉽게 이해된다.

---

깊이 우선 탐색(Depth-First Search, DFS)

깊이 우선 탐색은 가장 마지막 노드까지 내려가면서 탐색하는 것을 우선으로 하는 탐색 방법이다.

 

깊이 우선 탐색은 너비 우선 탐색과 다르게

 

부모 노드를 방문하는 순서에 따라 3가지로 나누어진다.

 

노드에 방문하는 것과 해당 노드로 이동하는 것(지나치는 것)은 다르며

방문을 했을 때 탐색하였다고 한다.

 

왼쪽의 이진 트리를 기준으로 현재 판단하는 노드에서

 

매번 동일한 과정을 반복한다고 생각하면 쉽게 이해할 수 있을 것이다.

 

A : 부모 노드

B : 왼쪽 자식 노드

C : 오른쪽 자식 노드

 

 

 

아래 트리를 예시로 3가지 탐색 방법에 대해 설명한다.

전, 중, 후 순회 예시

---

전위 순회(Preorder) - 부모 노드를 1번째로 방문

전위 순회는

부모 노드 방문 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드

 

순으로 탐색한다.

 

전위 순회 탐색 순서

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

---

중위 순회(Inorder) - 부모 노드를 2번째로 방문

중위 순회는

왼쪽 자식 노드 -> 부모 노드 방문 -> 오른쪽 자식 노드

 

순으로 탐색한다.

 

가장 처음 시작하는 것은 부모 노드이지만 방문하지 않고 왼쪽 자식 노드로 이동한다.

 

 

왼쪽 트리를 예로 들면

 

A에서 시작하지만 B로 이동하여

 

B 방문 -> A 방문 -> C 방문

 

 

 

 

중위 순회 탐색 순서

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

---

후위 순회(Postorder) - 부모 노드를 3번째로 방문

후위 순회는

왼쪽 자식 노드 -> 오른쪽 자식 노드  -> 부모 노드 방문

 

순으로 탐색한다.

 

후위 순회 탐색 순서

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

 

---

참조

Do it! 자료구조와 함께 배우는 알고리즘 입문

너비 우선 탐색

깊이 우선 탐색

트리 종류