Tree Traversal

트리를 순회하는방법은 세가지로 나눌수있다.

전위순회 (preOrder) / Root -> Left -> Right
1 - 2 - 4 - 5 - 3

중위순회 (inOrder) / Left -> Root -> Right
4 - 2 - 5 - 1 - 3

후위순회 (postOrder) / Left -> Right -> Root
4 - 5 - 2 - 3 - 1

BFS/DFS ?

그래프의 탐색은 모든 정점들을 한번씩 방문 하는것을 목적으로 삼는다.

최대한 불필요한 이동을 하지않기위해서.

최단경로를 찾는 목적에도 여러가지 방법이 있듯이. 그래프의 모든 정점 탐색방법은 여러가지 가 있다.

가장 대표적인게 BFS , DFS이다.

결국 순서의 차이이고, 모든 자료를 하나씩 확인해 본다는점은 같다.

BFS

Breadth-First Search , 너비우선 탐색 이라고 한다.

가까운 정점부터 탐색 한다.

그리고 더는 탐색할 정점이 없을때, 그 다음 떨어져 있는 정점을 순회한다.

주로 두 정점 사이의 최단 경로를 찾고 싶을 때 사용한다.

DFS

Depth-First Search , 깊이우선 탐색 이라고 한다.

하나의 경로를 끝까지 탐색한 후, 도착이 아니라면 다음 경로로 넘어가 탐색한다.

하나의 노선을 끝까지 들어가서 확인하고, 다음으로 넘어가기 때문에

운이좋다면 단 몇번 만에 경로를 찾을수 있다.

DFS와 BFS는 모든 정점을 한번만 방문한다는 공통점을 가지고 있지만, 사용할 때의 장단점ㅇ은 분명하기 때문에 해당 상황에 맞는 탐색기법을 사용해야 한다.