Ch.6 트리 기초
이진트리 순회 — pre/in/post/level order
트리의 모든 노드를 빠짐없이 방문하라
트리에 저장된 데이터를 활용하려면 모든 노드를 방문해야 합니다. 하지만 배열처럼 순서대로 읽을 수 없죠. 4가지 순회 방법을 배웁니다.
같은 트리인데 순회 방법에 따라 출력 순서가 완전히 다르다?
Pre/In/Post/Level — 이 4가지만 알면 모든 트리 문제의 기초를 세울 수 있습니다.
핵심 개념
DFS(깊이 우선)
한 방향으로 끝까지 내려간 뒤 되돌아오는 탐색
BFS(너비 우선)
같은 깊이의 노드를 모두 방문한 뒤 다음 깊이로 내려가는 탐색
핵심 내용
배열은 인덱스 0부터 끝까지. 트리는? 선택지가 4가지입니다
전위·중위·후위는 DFS(깊이 우선), 레벨 순회는 BFS(너비 우선)입니다
전위 = 루트를 먼저 방문. Pre(먼저) + order(순서)
def preorder(node):
if not node:
return []
# 루트 → 왼쪽 → 오른쪽
return [node.val] + preorder(node.left) + preorder(node.right)
# 1
# / \
# 2 3
# / \
# 4 5
# 결과: [1, 2, 4, 5, 3]전위 순회는 트리 복사에 사용됩니다. 루트부터 복사하면 구조가 보존되니까요
중위 = 루트를 중간에 방문. 왼쪽 서브트리를 먼저 다 본 뒤!
def inorder(node):
if not node:
return []
# 왼쪽 → 루트 → 오른쪽
return inorder(node.left) + [node.val] + inorder(node.right)
# 1
# / \
# 2 3
# / \
# 4 5
# 결과: [4, 2, 5, 1, 3]BST(이진 탐색 트리)를 중위 순회하면 정렬된 순서로 출력됩니다. 이건 면접 단골 질문!
후위 = 루트를 맨 나중에 방문. 자식을 먼저 처리한 뒤 부모를 처리합니다
def postorder(node):
if not node:
return []
# 왼쪽 → 오른쪽 → 루트
return postorder(node.left) + postorder(node.right) + [node.val]
# 1
# / \
# 2 3
# / \
# 4 5
# 결과: [4, 5, 2, 3, 1]후위 순회는 트리 삭제에 사용됩니다. 자식부터 지워야 안전하니까요. 파일 시스템의 `rm -rf`도 후위 순회!
레벨 순회는 층(layer)별로 방문합니다. 큐(Queue)를 사용하는 BFS입니다
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# 결과: [1, 2, 3, 4, 5] ← 위→아래, 왼→오른쪽순회 요약 • Preorder: 루트→왼→오 (복사) • Inorder: 왼→루트→오 (정렬 출력) • Postorder: 왼→오→루트 (삭제) • Level order: 층별 BFS (최단 경로)
DFS 3가지는 재귀(or 스택), Level order는 큐. 이 차이를 확실히 기억하세요
BST를 중위 순회(Inorder)하면 결과가 어떻게 되는가?
레벨 순회(Level Order)에는 어떤 자료구조를 사용하는가?
후위 순회에서 루트 노드는 가장 마지막에 방문된다
핵심 용어
전위(Preorder)
루트 → 왼쪽 → 오른쪽
중위(Inorder)
왼쪽 → 루트 → 오른쪽
후위(Postorder)
왼쪽 → 오른쪽 → 루트
레벨(Level order)
위에서 아래로, 같은 층 먼저
정리 노트
이진트리 순회 — 4가지 방법
DFS 순회 (재귀/스택)
- Preorder
- 루트 → 왼 → 오 (복사)
- Inorder
- 왼 → 루트 → 오 (정렬)
- Postorder
- 왼 → 오 → 루트 (삭제)
BFS 순회 (큐)
- Level Order
- 층별 방문, deque 사용
시각 자료
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작