🌳
트리
전·중·후위·레벨 순회
강의 17: 트리 순회 (Tree Traversal)
이진 트리의 네 가지 순회 방식을 재귀·반복으로 구현하고 입출력 변환에 활용합니다.
트리순회재귀
소요 시간
⏱ 약 1시간
난이도
📊 중급
선수 조건
🎯 단원 14
결과물
이진 트리의 네 가지 순회 방식을 재귀·반복으로 구현하고 입출력 변환에 활용합니다.
이 강의에서 배우는 것
- 1트리의 구조(노드, 간선, 루트, 리프)를 이해하고 Python으로 구현할 수 있다.
- 2전위/중위/후위 순회를 재귀와 반복(스택) 방식으로 모두 구현할 수 있다.
- 3레벨 순회(BFS)와 지그재그 순회를 큐를 이용해 구현하고, 각 순회의 활용 상황을 설명할 수 있다.
소개
트리(Tree)는 **사이클이 없는 연결된 그래프**의 특수한 형태입니다. n개의 노드를 가진 트리는 정확히 n-1개의 간선을 가지며, 임의의 두 노드 사이에는 유일한 경로가 존재합니다.
그래프 순회(DFS/BFS)를 트리에 적용하면 **순회 순서(traversal order)** 에 따라 다른 결과가 나옵니다. 이 순서가 중요한 이유:
- **전위 순회(pre-order)**: 트리 복사, 직렬화(serialization)
- **중위 순회(in-order)**: 이진 탐색 트리에서 정렬된 순서 출력
- **후위 순회(post-order)**: 트리 삭제, 파일 시스템 크기 계산
- **레벨 순회(level-order)**: BFS, 최단 경로, 너비 우선 처리
text
트리 vs 일반 그래프
───────────────────────────────────────────────────────
특성 트리 일반 그래프
───────────────────────────────────────────────────────
사이클 없음 있을 수 있음
연결성 항상 연결됨 연결 안 될 수 있음
간선 수 n-1 0 ~ n(n-1)/2
루트 있음(보통) 없음
부모-자식 명확 방향 없음(무향)
───────────────────────────────────────────────────────핵심 개념
트리 노드 구조
python
class TreeNode:
def __init__(self, val: int = 0,
left: 'TreeNode | None' = None,
right: 'TreeNode | None' = None):
self.val = val
self.left = left
self.right = right텍스트 아트: 예제 트리
text
1 ← 레벨 0 (루트)
/ \
2 3 ← 레벨 1
/ \ / \
4 5 6 7 ← 레벨 2 (리프)
전위 순회 (Pre-order): 1 → 2 → 4 → 5 → 3 → 6 → 7
중위 순회 (In-order): 4 → 2 → 5 → 1 → 6 → 3 → 7
후위 순회 (Post-order): 4 → 5 → 2 → 6 → 7 → 3 → 1
레벨 순회 (Level-order): 1 → 2 → 3 → 4 → 5 → 6 → 7순회 방법 비교
text
┌─────────────────────┬──────────────┬──────────────────────────────────┐
│ 순회 방법 │ 시간 복잡도 │ 공간 복잡도 │
├─────────────────────┼──────────────┼──────────────────────────────────┤
│ 전위 (재귀) │ O(n) │ O(h) — 재귀 스택 (h=높이) │
│ 중위 (재귀) │ O(n) │ O(h) │
│ 후위 (재귀) │ O(n) │ O(h) │
│ 전위 (반복) │ O(n) │ O(h) — 명시적 스택 │
│ 중위 (반복) │ O(n) │ O(h) │
│ 후위 (반복) │ O(n) │ O(h) │
│ 레벨 순회 (BFS) │ O(n) │ O(w) — w=최대 너비 │
└─────────────────────┴──────────────┴──────────────────────────────────┘
※ 균형 트리: h = O(log n), 편향 트리(사슬): h = O(n)
※ 완전 이진 트리 최대 너비: w = n/2 (마지막 레벨)재귀 순회 핵심 패턴
text
전위 (Pre-order): [현재] → [왼쪽] → [오른쪽]
중위 (In-order): [왼쪽] → [현재] → [오른쪽]
후위 (Post-order): [왼쪽] → [오른쪽] → [현재]반복 순회 — 스택 사용
text
전위 반복:
stack = [root]
while stack:
node = stack.pop()
visit(node)
if node.right: stack.push(node.right) ← 오른쪽 먼저 (나중에 처리)
if node.left: stack.push(node.left) ← 왼쪽 나중에 (먼저 처리)
중위 반복:
stack = [], curr = root
while curr or stack:
while curr:
stack.push(curr)
curr = curr.left
curr = stack.pop()
visit(curr)
curr = curr.right레벨 순회 — 큐 사용
text
queue = deque([root])
while queue:
node = queue.popleft()
visit(node)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)예제로 보기
| 파일 | 내용 |
|---|---|
| `src/01_tree_node.py` | TreeNode 클래스, 트리 생성, 출력 |
| `src/02_recursive_traversal.py` | 전위/중위/후위 재귀 순회 |
| `src/03_iterative_traversal.py` | 전위/중위/후위 반복(스택) 순회 |
| `src/04_level_order.py` | 레벨 순회 BFS, 지그재그 순회 |
자주 하는 실수
- **None 체크 누락**: 재귀 함수에서 `if node is None: return` 기저 조건을 빠뜨리면 AttributeError 발생
- **후위 반복 순서 혼동**: 후위 반복은 "전위의 역순"을 이용하거나 두 스택을 사용 — 단순히 스택 순서만 바꾸면 틀림
- **레벨 구분 없는 BFS**: `queue.popleft()` 할 때 레벨별로 묶으려면 반드시 `level_size = len(queue)`로 현재 레벨 크기를 먼저 저장
- **높이와 깊이 혼용**: 높이(height)는 노드에서 리프까지, 깊이(depth)는 루트에서 노드까지 — 방향이 반대
- **편향 트리 재귀 오버플로**: Python 기본 재귀 한도 1000 — 입력이 클 경우 `sys.setrecursionlimit()` 또는 반복 방식 사용
정리
- 모든 트리 순회는 **시간 O(n), 공간 O(h)** (레벨 순회는 O(w))
- 재귀는 코드가 간결하지만 깊은 트리에서 스택 오버플로 위험
- 반복(스택/큐) 방식은 명시적 스택으로 재귀를 대체
- **중위 순회 = 이진 탐색 트리의 정렬된 출력** (다음 강의와 연결)
직접 해 보기
- 트리의 최대 깊이(max depth)를 BFS와 DFS 각각으로 구현해 보기
- 두 트리가 동일한지 비교하는 함수 작성 (재귀 활용)
- 경로 합(path sum)이 target과 같은 경로가 존재하는지 판별
과제
📂 `homework/README.md` 참조
- 백준 1991 (트리 순회) — Silver I
- 백준 11725 (트리의 부모 찾기) — Silver II