Algorithm DFS(Depth-first search)

알고리듬 DFS(Depth-first search)를 알아보겠습니다.

DFS는 깊이 우선 탐색인데요. 2진 트리가 있을 때 깊이를 먼저 탐색하는 것을 말합니다.
​
​
아래와 같은 트리가 있다고 봅시다.

깊이 우선 탐색은 아래로 내려간다는 뜻입니다. 즉, 1 번 다음에 2 번으로 가고 4 번으로 내려가면서 먼저 탐색을 합니다.

이와는 다른 개념으로 옆으로 탐색하는 방법인 BFS(Breadth-first search) 너비 우선 탐색도 있습니다. 여기서는 BFS는 다루지 않겠습니다.

​

​

이 트리를 DFS로 모두 탐색하는 방법에는 3가지가 있습니다.

Preorder Traversal, 전위 순회 (Root -> Left -> Right)

Inorder Traversal, 중위 순회 (Left -> Root -> Right)

Postorder Traversal, 후위 순회 (Left -> Right -> Root)

​

Pre(전), In(중), Post(후)가 뜻하는 것은 root(첫 노드)의 위치입니다.

​

차례대로 봅시다.

​

전위 순회(Preorder Traversal)의 경우 첫 노드(Root) -> 왼쪽(Left) -> 오른쪽(Right) 순서로 탐색합니다.

탐색 순서는 다음과 같이 됩니다.

1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

중위 순회(Inorder Traversal)의 경우 왼쪽(Left) -> 첫 노드(Root) -> 오른쪽(Right) 순서로 탐색합니다.

탐색 순서는 다음과 같이 됩니다.

4 -> 2 -> 5 -> 1 -> 6 -> 7 -> 3

후위 순회(Postorder Traversal)의 경우 왼쪽(Left) -> 오른쪽(Right) -> 첫 노드(Root) 순서로 탐색합니다.

탐색 순서는 다음과 같이 됩니다.

4 -> 5 -> 2 -> 7 -> 6 -> 3 -> 1

끝.

카테고리: Algorithm