트리 순회
트리의 모든 노드를 체계적으로 방문하는 방법. 순서에 따라 결과가 달라진다.
순회 종류
1
/ \
2 3
/ \
4 5
| 순회 | 순서 | 결과 | 용도 |
|---|
| 전위 (Preorder) | 루트→좌→우 | 1,2,4,5,3 | 트리 복사 |
| 중위 (Inorder) | 좌→루트→우 | 4,2,5,1,3 | BST 정렬 |
| 후위 (Postorder) | 좌→우→루트 | 4,5,2,3,1 | 삭제/계산 |
| 레벨 (Level) | 위→아래 | 1,2,3,4,5 | BFS |
기억법
전위: 루트 먼저! (Pre = 앞에)
중위: 루트 중간! (In = 가운데)
후위: 루트 나중! (Post = 뒤에)
중위 순회 = BST 정렬
BST:
4
/ \
2 6
/ \ / \
1 3 5 7
중위 순회: 1, 2, 3, 4, 5, 6, 7
→ 오름차순 정렬!
코드 (재귀)
def inorder(node):
if not node: return
inorder(node.left) # 왼쪽
print(node.val) # 루트
inorder(node.right) # 오른쪽
def preorder(node):
if not node: return
print(node.val) # 루트 먼저!
preorder(node.left)
preorder(node.right)
def postorder(node):
if not node: return
postorder(node.left)
postorder(node.right)
print(node.val) # 루트 나중!
레벨 순회 (BFS)
from collections import deque
def level_order(root):
q = deque([root])
while q:
node = q.popleft()
print(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
실무 활용
| 순회 | 활용 사례 |
|---|
| 전위 | 디렉토리 구조 출력, 직렬화 |
| 중위 | BST에서 정렬된 데이터 |
| 후위 | 파일 크기 합산, 메모리 해제 |
| 레벨 | 최단 경로, 계층별 처리 |
Q.전위, 중위, 후위 순회의 차이를 설명해주세요.
자기 자신을 언제 방문하는지가 다릅니다. 왼쪽과 오른쪽 순서는 셋 다 같습니다.
| 순회 | 순서 | 쓰이는 곳 |
|---|
| 전위 | 자기, 왼쪽, 오른쪽 | 트리 복사, 구조를 그대로 직렬화 |
| 중위 | 왼쪽, 자기, 오른쪽 | BST에서 정렬된 순서 얻기 |
| 후위 | 왼쪽, 오른쪽, 자기 | 자식을 먼저 정리해야 할 때. 트리 삭제, 디렉터리 용량 합계 |
1
/ \
2 3
/ \
4 5
| 순회 | 결과 |
|---|
| 전위 | 1, 2, 4, 5, 3 |
| 중위 | 4, 2, 5, 1, 3 |
| 후위 | 4, 5, 2, 3, 1 |
흔한 실수: 이름을 방문 순서 전체로 착각하는 것. 전위, 중위, 후위는 부모를 어디서 처리하는가만 가리킵니다. 그리고 후위가 필요한 이유를 못 대는 경우가 많은데, 자식을 먼저 처리해야 하는 작업(해제, 합계)이 답입니다.
Q.중위 순회가 BST에서 특별한 이유는?
중위 순회 결과가 정렬된 순서가 되기 때문입니다.
BST의 규칙은 왼쪽 하위 트리가 모두 자기보다 작고 오른쪽이 모두 크다는 것입니다. 중위 순회는 왼쪽을 다 본 뒤 자기, 그 다음 오른쪽을 보므로 작은 것부터 순서대로 나옵니다.
8
/ \
3 10
/ \ \
1 6 14
중위 순회: 1, 3, 6, 8, 10, 14
여기서 두 가지가 따라옵니다.
| 활용 | 방법 |
|---|
| BST 검증 | 중위 순회 결과가 증가하는지 확인한다 |
| k번째 작은 값 | 중위 순회를 k번째에서 멈춘다 |
흔한 실수: BST 검증을 각 노드의 자식만 비교해서 하는 것. 하위 트리 전체가 조건을 만족해야 하므로, 중위 순회로 확인하거나 범위(최소, 최대)를 내려보내며 검사해야 합니다.
Q.트리 순회를 반복문(스택)으로 구현할 수 있나요?
가능합니다. 재귀가 쓰던 호출 스택을 직접 만드는 것입니다.
전위 순회를 스택으로
스택에 뿌리를 넣는다
스택이 빌 때까지
꺼내서 방문한다
오른쪽 자식을 넣는다
왼쪽 자식을 넣는다 <- 나중에 넣어야 먼저 꺼내진다
중위 순회는 조금 더 복잡합니다. 왼쪽으로 내려가며 스택에 쌓고, 더 갈 수 없으면 꺼내 방문한 뒤 오른쪽으로 넘어갑니다.
반복문으로 바꾸는 이유는 깊은 트리에서 호출 스택이 넘치는 것을 막기 위해서입니다. 스택 영역은 보통 수백 KB에서 몇 MB로 제한되지만, 힙에 만든 스택은 훨씬 크게 쓸 수 있습니다.
흔한 실수: 왼쪽부터 스택에 넣는 것. 스택은 나중에 넣은 것이 먼저 나오므로 오른쪽을 먼저 넣어야 왼쪽이 먼저 방문됩니다.
Q.레벨 순회는 어떤 자료구조를 사용하나요?
큐를 씁니다. 같은 깊이를 모두 방문한 뒤 다음 깊이로 넘어가야 하므로, 발견한 순서대로 꺼내야 합니다.
큐에 뿌리를 넣는다
큐가 빌 때까지
꺼내서 방문한다
왼쪽 자식과 오른쪽 자식을 큐에 넣는다
깊이별로 나누고 싶으면 한 바퀴 시작할 때 큐의 크기를 재두고 그만큼만 꺼냅니다. 그 개수가 그 깊이의 노드 수입니다.
| 순회 | 자료구조 | 나오는 순서 |
|---|
| 레벨(너비 우선) | 큐 | 얕은 깊이부터 |
| 전위, 중위, 후위(깊이 우선) | 스택 또는 재귀 | 한 갈래를 끝까지 |
흔한 실수: 스택으로 레벨 순회를 시도하는 것. 스택은 방금 넣은 자식부터 꺼내므로 깊이 우선이 됩니다. 깊이를 층층이 보려면 반드시 큐입니다.
먼저 스스로 답해보고 아래 답변과 견줘보세요. 막히는 부분은 문제로 확인할 수 있어요.
읽었으면 문제로 확인해보세요
자료구조 문제를 풀면 틀린 문제가 자동으로 노트에 쌓입니다. 가입 없이 5문제를 먼저 풀어볼 수도 있어요.