Tree Traversal (트리 순회): BFS and DFS

1. Tree Traversal

자료구조의 종류 중 하나인 Tree 에서 각각의 Node를 한 번씩 방문하는 과정을 가르킴.

 

크게 BFS와 DFS로 나뉨.

선택의 원칙은 다음과 같음:

• 모든 노드를 방문하고자 하는 경우에 DFS를 선택하는 경우가 낫다 (BFS도 가능함).
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
• 검색 속도 자체는 너비 우선 탐색(BFS)이 더 빠름

Tree가 크다면 DFS이고, Tree가 소규모이고 탐색 대상이 근처라면 BFS가 낫다.

• 모든 node 방문: 둘 다 가능.
• 방문 경로의 특징을 저장해야 하는 경우: DFS만 가능.
• 최단 거리 구해야 하는 경우: BFS가 유리.

---

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

Queue를 이용하여 구현 (recursive하지 않음)하며 node에 이전에 방문을 했었는지 여부를 반드시 체크해야함 

가까운 Node 부터 탐색을 시작하므로 최단경로 검색에 유리.

 

위의 예에서 2,3,2,4,5,2,3,5,4 의 순서로 탐색이 이루어짐.

---

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

Stack을 이용하는 알고리즘이며, Recursive call을 통해 구현시 매우 간결하게 구현 가능.

DFS는 최대한 멀리 있는 Node부터 탐색

 

다음의 3가지 방법이 있음.

3-1. in-order traversal (중위순회)

가장 일반적인 방법 (BST 에서 사용됨)

Left, Root, Right의 순으로 순회를 함.

---

3-2. pre-order traversal (전위순회)

Root, Left, Right의 순으로 순회를 함.

---

3-3. post-order traversal (후위순회)

Left, Right, Root의 순으로 순회를 함.  

---

4. Example

BFS: 0,1,2,3,4,5,6

DFS:

• inorder: 3,1,4,0,5,2,6
• preorder: 0,1,3,4,2,5,6
• postorder: 3,4,1,5,6,2,0

---

관련하여 같이보면 좋은 자료

https://dsaint31.tistory.com/463

[CE] Tree vs. Graph

 

2024.11.16 - [CE] - [CE] Heap and Complete Binary Tree

[CE] Heap and Complete Binary Tree

 

---