트리 탐색(Tree Traversal) 알고리즘

개요

트리 탐색(Tree Traversal)은 트리 구조를 가진 자료구조의 노드를 특정 순서에 따라 방문하는 알고리즘이다. 이진 트리(Binary Tree), 이진 탐색 트리(BST), 힙(Heap) 등 다양한 트리 구조에서 데이터를 순차적으로 접근하거나 연산을 수행할 때 사용된다. DFS 기반의 전위/중위/후위 순회와 BFS 기반의 레벨 순회로 나뉘며, 문제에 따라 적절한 탐색 방법을 선택해야 한다.

---

1. 개념 및 정의

트리 탐색은 다음과 같은 두 가지 유형으로 나뉜다:

• DFS(Depth-First Search): 깊이 우선 순회 (전위, 중위, 후위 순회)
• BFS(Breadth-First Search): 너비 우선 순회 (레벨 순회)

---

2. DFS 기반 트리 순회

순회 방식	방문 순서	주요 특징
전위 순회 (Preorder)	루트 → 왼쪽 → 오른쪽	복사, 구조 변환에 적합
중위 순회 (Inorder)	왼쪽 → 루트 → 오른쪽	이진 탐색 트리 출력 시 오름차순
후위 순회 (Postorder)	왼쪽 → 오른쪽 → 루트	삭제, 자식 먼저 처리 필요할 때 사용

---

3. BFS 기반 트리 순회

순회 방식	설명	자료구조
레벨 순회(Level-order)	루트부터 아래로 각 레벨을 순서대로 탐색	큐(Queue) 사용

레벨 순회는 트리의 계층 구조나 레벨별 출력 시 유용하다.

---

4. 파이썬 구현 예시

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# 전위 순회
def preorder(node):
    if node:
        print(node.key, end=' ')
        preorder(node.left)
        preorder(node.right)

# 중위 순회
def inorder(node):
    if node:
        inorder(node.left)
        print(node.key, end=' ')
        inorder(node.right)

# 후위 순회
def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.key, end=' ')

---

5. 시간 및 공간 복잡도

항목	복잡도
시간 복잡도	O(n) (모든 노드를 한 번씩 방문)
공간 복잡도	O(h) (h: 트리의 높이, 재귀 스택 또는 큐 사용 시)

균형 트리일수록 공간 복잡도는 log n에 가까워진다.

---

6. 시각적 예시 (이진 트리)

트리 구조:

        A
       / \
      B   C
     / \   \
    D   E   F

• 전위 순회: A B D E C F
• 중위 순회: D B E A C F
• 후위 순회: D E B F C A
• 레벨 순회: A B C D E F

---

7. 트리 탐색 활용 사례

분야	활용 예시
컴파일러	구문 트리 분석 (후위 순회)
표현식 계산	이진 수식 트리 순회
디렉터리 구조	전위 순회로 파일 계층 출력
파일 삭제	후위 순회로 자식부터 삭제
알고리즘 문제풀이	이진 트리 직렬화, 경로 탐색 등

---

8. DFS vs BFS 비교 (트리 탐색 기준)

항목	DFS (Pre/In/Post)	BFS (Level-order)
구현	재귀, 스택	큐
시간복잡도	O(n)	O(n)
사용 예시	수식 계산, 경로 탐색	레벨 탐색, 최단 거리
특징	깊이 우선	너비 우선, 계층별 탐색

---

9. 결론

트리 탐색은 트리 구조 데이터를 다룰 때 필수적인 알고리즘이며, 문제의 목적에 따라 전위/중위/후위/레벨 순회 중 적절한 방법을 선택해야 한다. 이진 탐색 트리 출력, 파일 삭제, 구문 분석, 계층 탐색 등 다양한 분야에서 활용되며, DFS와 BFS 개념을 트리에서 명확히 이해하는 것은 알고리즘 학습의 핵심이다.