트리 자료구조에서 탐색(또는 검색)은 트리의 종류에 따라 많이 달라진다.
따라서 각 트리의 자료구조에 대한 이해가 필수적이다.
트리 자료구조에 대한 정리는 아래 페이지에 정리하겠다.
트리의 탐색 방식은 4가지가 있다. 아래에 표로 정리하였다.
| 방식 | 순서 | 특징 |
|---|---|---|
| 전위 순회 (Pre-order) | 루트 → 왼쪽 → 오른쪽 | 트리 구조 출력, 복제 |
| 중위 순회 (In-order) | 왼쪽 → 루트 → 오른쪽 | 이진 탐색 트리일 때 정렬된 순서 출력 |
| 후위 순회 (Post-order) | 왼쪽 → 오른쪽 → 루트 | 삭제 순서, 후처리에 유리 |
| 레벨 순서 순회 (Level-order) | 루트부터 층별 순서로 | BFS 기반, 시각화에 적합 |
예시를 들어보자.
A
/ \\
B C
/ \\ \\
D E F
위 트리에서 각 방식에 따라 방문하는 순서를 생각해보자.
전위의 경우
루트부터 시작한다. A
그 다음 왼쪽으로 쭉 같다. B → D
그 다음 작은 부분의 오른쪽을 방문하고 E
남은 오른쪽을 방문한다. C →F
따라서, A → B → D→ E → C → F 순으로 방문한다.
중위의 경우
왼쪽부터 진행하므로 D
이후 루트 → 오른쪽 B → E
다시 루트 →오른쪽 A → C → F
따라서 D→B→E→A→C→F 이다.
후위의 경우
왼쪽 → 오른쪽 → 루트이므로
시작은 D
다음 오른쪽 E
다음 루트 B
다음 왼쪽은 없으니 오른쪽 F
좌우 다 없으니 루트 C
좌우 다 없으니 루트 A로
따라서 D→E→B→F→C→A이다
이진 트리 탐색은 트리 자료구조 중 ‘이진 트리’의 모든 노드를 특정 순서에 따라 탐색하는 방법이다.
이진 트리는 자식이 2개인 트리를 의미하며