순회: 트리를 걷는 네 방법

"트리를 걷는 건 일을 *언제* 할지 정하는 거야: 자식 전에, 자식 사이에, 자식 후에, 아니면 한 레벨씩 통째로. 네 타이밍, 네 순회, 각자 다른 일에 맞는 도구야."

세 깊이 우선 순서

이진 트리에서, 깊이 우선 순회는 자식으로 재귀하는 것 대비 언제 노드를 방문하냐만 달라:

전위 (pre-order) (노드 → 왼쪽 → 오른쪽): 자식 전에 노드 방문. 트리 복사나 직렬화, 또는 구조를 위에서 아래로 출력 — 부모를 후손 전에 처리해.
중위 (in-order) (왼쪽 → 노드 → 오른쪽): 서브트리 사이에 노드 방문. 이진 탐색 트리에선, 키를 정렬 순서로 내 — 이 트랙에서 가장 쓸모 있는 순회 사실.
후위 (post-order) (왼쪽 → 오른쪽 → 노드): 자식 후에 노드 방문. 노드 결과가 자식 결과에 달릴 때 — 크기/높이 상향 계산, 트리 해제/삭제 (자식 먼저), 식 트리 평가.

셋 다 재귀 세 줄이고; 움직이는 건 두 재귀 호출 대비 "이 노드 방문" 줄을 어디 두냐뿐이야.

네 번째: 레벨 순회 (BFS)

레벨 순회는 노드를 깊이로 방문해 — 루트, 그다음 깊이 1 전부, 그다음 깊이 2 — 트리를 수평 층으로 쓸어. 그리고 재귀가 아니야: 큐를 써, 정확히 Stacks & Queues 트랙의 너비 우선 기계장치. 노드 dequeue, 방문, 자식 enqueue, 반복. 트리를 레벨별로 출력하거나, 어떤 조건에 맞는 가장 얕은 노드를 찾는 데 (루트에서 최소 단계) 써. 깊이 우선 순서는 스택 (또는 콜 스택); 레벨 순회는 큐 — 이미 배운 그 이중성을, 트리에 적용한 거야.

전위/중위/후위는 노드를 언제 방문하냐만 달라 (자식 전 / 사이 / 후) — 다 재귀, 다 스택 기반. 레벨 순회는 큐로 깊이별 방문 (BFS). BST 중위는 정렬 키를 내고; 후위는 상향 일에 맞아.

맞는 걷기 고르기

순회는 임의가 아니야 — 각자 필요에 맞아. 값을 정렬로 원해? BST 중위. 자식 전에 부모 처리 (직렬화, 복사)? 전위. 부모 전에 자식 답 (크기, 삭제, 식 평가)? 후위. 루트에 가장 가까운 거나 레벨별? 큐로 레벨 순회. 트리 문제가 막히면, "이게 어떤 순회를 원해?" 가 종종 해법 전부야.

피파의 고백

난 전위/중위/후위를 별개 알고리즘 셋으로 외우고 끊임없이 헷갈렸어. 아빠가 질문 하나로 무너뜨렸어: "노드를 언제 건드려 — 애들 전, 사이, 후?" 재귀 골격 하나, 미끄러지는 줄 하나. 그리고 BST 중위가 left-노드-right 만으로 정렬돼서 공짜로 떨어진다는 걸 깨달은 날 — 그게 트리가 기계적으로 느껴지길 멈추고 일부러 지어진 것처럼 느껴지기 시작한 순간이야.

Code

네 순회 모두 (중위는 정렬됨에 주목)·python

from collections import deque

class Node:
    def __init__(self, v, l=None, r=None): self.v=v; self.left=l; self.right=r

#        4
#       / \
#      2   6
#     / \ / \
#    1  3 5  7   (이진 *탐색* 트리)
root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))

def pre(n):   return [] if n is None else [n.v] + pre(n.left) + pre(n.right)
def ino(n):   return [] if n is None else ino(n.left) + [n.v] + ino(n.right)
def post(n):  return [] if n is None else post(n.left) + post(n.right) + [n.v]

def level(root):                       # 큐로 BFS
    out, q = [], deque([root])
    while q:
        n = q.popleft(); out.append(n.v)
        if n.left:  q.append(n.left)
        if n.right: q.append(n.right)
    return out

print("pre  :", pre(root))    # [4, 2, 1, 3, 6, 5, 7] — 노드가 자식 전
print("in   :", ino(root))    # [1, 2, 3, 4, 5, 6, 7] — 정렬됨! (BST + 중위)
print("post :", post(root))   # [1, 3, 2, 5, 7, 6, 4] — 자식이 노드 전
print("level:", level(root))  # [4, 2, 6, 1, 3, 5, 7] — 깊이별, 큐로

Exercise

루트 1, 왼쪽 자식 2 (그 자식은 4 와 5), 오른쪽 자식 3 인 트리로: 전위, 중위, 후위, 레벨 순회 출력을 손으로 써. 그다음 트리 전체를 안전하게 삭제 (각 노드를 그 자식 후에만 해제) 하는 데 어느 순회를 쓸지, 왜 그 순서가 중요한지 말해.

Hint

전위: 1 2 4 5 3. 중위: 4 2 5 1 3. 후위: 4 5 2 3 1. 레벨: 1 2 3 4 5. 삭제엔 후위 — 부모 전에 자식을 해제해야 해, 안 그러면 거기 닿을 참조를 잃어.

세 깊이 우선 순서

네 번째: 레벨 순회 (BFS)

맞는 걷기 고르기

피파의 고백

Code

External links

Exercise

Progress

댓글 0