이진 트리(Binary Tree)는 데이터를 계층적으로 저장하고, 각 노드가 최대 두 개의 자식 노드를 갖는 구조이다.
트리를 탐색(Traversal)하는 방법에는 여러 가지가 있지만, 대표적으로 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 세 가지가 있다.
아래 이미지는 각각의 순회 방식에 따른 노드 방문 순서를 시각적으로 보여준다.
🔹 1. 전위 순회 (Preorder Traversal)
방문 순서: Root → Left → Right
전위 순회는 루트 노드를 가장 먼저 방문하고, 그 다음 왼쪽 서브트리, 마지막으로 오른쪽 서브트리를 방문한다.
즉, “부모 노드를 자식 노드보다 먼저 방문한다”는 특징이 있다.
예시:
1 → 2 → 3 → 4 → 5 → 6 → 7
활용:
- 트리 구조를 복사하거나 출력할 때 사용한다.
- 루트부터 탐색이 필요한 경우 유용하다.
🔹 2. 중위 순회 (Inorder Traversal)
방문 순서: Left → Root → Right
중위 순회는 왼쪽 서브트리를 먼저 방문하고, 이후 루트, 그리고 오른쪽 서브트리를 방문한다.
이 방법은 이진 탐색 트리(Binary Search Tree, BST) 에서 사용하면 오름차순 정렬된 결과를 얻을 수 있다.
예시:
1 → 2 → 3 → 4 → 5 → 6 → 7
활용:
- 정렬된 데이터를 출력할 때 사용한다.
- 이진 탐색 트리의 값들을 순서대로 확인할 때 적합하다.
🔹 3. 후위 순회 (Postorder Traversal)
방문 순서: Left → Right → Root
후위 순회는 자식 노드를 모두 방문한 후 마지막에 루트를 방문한다.
즉, “부모 노드를 가장 나중에 방문한다”는 특징을 가진다.
예시:
1 → 3 → 2 → 5 → 4 → 6 → 7
활용:
- 트리의 삭제 연산 시, 자식 노드를 먼저 처리한 뒤 부모를 제거할 때 사용한다.
- 하위 노드의 연산 결과를 이용해 부모 노드의 연산을 수행할 때 유용하다.
🧩 정리
| 순회 방식 | 방문 순서 | 특징 |
|---|---|---|
| 전위 순회 | Root → Left → Right | 루트를 먼저 방문 |
| 중위 순회 | Left → Root → Right | 정렬된 결과를 얻을 수 있음 |
| 후위 순회 | Left → Right → Root | 루트를 가장 나중에 방문 |
