트리 순회 (Tree traversal)

트리 순회 (Tree traversal)
ㄴ 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것이 트리 순회(Tree traversal).

트리를 순회할 수 있는 3가지 방법?
ㄴ (!!! 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽)

• **전위순회 (Preorder)** = 가장 먼저 루트를 방문 후 루트에서부터 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.
• **중위순회 (Inorder)** = 루트를 가운데에 두고 순회하고, 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.
• **후위순회 (Postorder)** = 루트를 가장 마지막에 순회하고, 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.

BFS (Breadth-First Search)?
ㄴ 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 한다.
- 가까운 정점부터 탐색하고 더는 탐색할 정점이 없을 때, 그 다음 떨어져 있는 정점을 순서대로 방문한다.
DFS (Depth-First Search)?
ㄴ 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 한다.
- 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가서 탐색한다.

.
.
.
.
.
.
.
.
.
.
☁️🤦🏻‍♂️☁️