[자료 구조] - 트리 자료 구조(2)-트리의 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) :: Tree-Search (Breadth-First Search, Depth-First Search)

지난 시간에 우리는 트리에 대한 기본 개념과 용어에 대해서 알아보았으니 이제 트리를 파고들 준비가 되었다.

원래 BFS와 DFS는 그래프 자료구조쯤 가서야 구현도 할만하고 재밌지만 막상 가서 하려면 어려울 수 있으니 이번 시간에는 가볍게 읽어보고 이런게 있구나 하고 넘어가는 시간이 되었으면 좋겠다.

트리의 탐색

트리의 탐색에는 두 가지 방법이 있다.

1. 너비 우선 탐색
2. 깊이 우선 탐색

출처 : https://seing.tistory.com/29

BFS::너비 우선 탐색

너비 우선 탐색은 가장 낮은 레벨에서 시작히서 왼쪽에서 오른쪽 방향을 검색하고 한 레벨에서 검색이 끝나면 다음 레벨로 내려가는 방식으 검색 구조이다.

 

너비 우선 탐색은 가까운 정점을 먼저 방문 하고 멀리 있는 정점을 나중에 방문한다는 점에서 특정 정점과의 관계가 중요한 탐색 방법이다.

 

예를 들어 전 세계의 도시 이름을 검색한다고 하면, 도시 A와 B 는 같은 차수에 있기 때문에 도시 A에 있는 모든 동과 마을을 모두 조사하는 DFS보다 빠른 탐색이 가능하다.

DFS::깊이 우선 탐색

깊이 우선 탐색은 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다.

 

리프에 도달해서 더 이상 검색을 진행할 곳이 없으면 부모에게 돌아가고 다시 자식 노드로 내려간다.

 

깊이 우선 탐색에서는 언제 노드를 방문할지에 따라서 3가지 종류로 나뉜다.

Tree Traversals (트리 순회)

트리 순회 방법은 위에서 말 했던 것 처럼 언제 노드를 방문할지를 정하는 개념이다. 크게

1. 전위 순회 - PreOrder
2. 중위 순회 - InOrder
3. 후위 순회 - PostOrder

---