728x90
트리 순회(Tree Traversal)
- 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문
- 트리 순회는 항상 왼쪽에서 오른쪽으로 조회함
트리 순회 방법
- 전위 순회(preorder traverse) : 루트부터 순회를 시작해 왼쪽에서 오른쪽으로 이동해 노드 탐색
탐색 순서 : 0 → 1 → 3 → 7 → 4 → 8 → 2 → 5 → 9 → 6
- 중위 순회(inorder traverse) : 왼쪽에서 순회를 시작해 루트를 중간에 거쳐 오른쪽으로 이동해 노드 탐색
탐색 순서 : 7 → 3 → 1 → 8 → 4 → 0 → 9 → 5 → 2 → 6
- 후위 순회(postorder traverse) : 왼쪽에서 오른쪽으로 노드 탐색 후 루트를 가장 마지막에 순회
탐색 순서 : 7 → 3 → 8 → 4 → 1 → 9 → 5 → 6 → 2 → 0
그래프 탐색
- 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문
그래프 탐색 방법
- 너비 우선 탐색(BFS, Breadth-First Search) : 가장 가까운 정점부터 탐색. 정점 사이의 최단 경로를 찾을 때 사용
- 깊이 우선 탐색(DFS, Depth-First Search) : 하나의 경로를 끝까지 탐색한 후 다음 경로 탐색. 모든 노드를 방문하고자 할 때 사용
728x90
'백엔드 개발자 공부 > 자료구조, 알고리즘' 카테고리의 다른 글
| [알고리즘] Algorithm with Math: 순열 / 조합 (0) | 2022.09.29 |
|---|---|
| [자료구조] 이진 트리(Binary Tree) (0) | 2022.09.23 |
| [자료구조] 트리(Tree) (0) | 2022.09.23 |
| [자료구조] 그래프(Graph) (0) | 2022.09.23 |
| [자료구조] 스택(Stack) / 큐(Queue) (0) | 2022.09.22 |