전위 순회 (Pre-order Traversal)

트리의 전위 순회는 루트 노드를 먼저 방문하고, 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문하는 순회 방식입니다.

순서: 루트 → 왼쪽 → 오른쪽

전위 순회 결과: A → B → D → E → C → F

전위 순회 구현 (재귀)

def preorder(node):
    if node is None:
        return
    print(node.val)       # 1. 루트
    preorder(node.left)   # 2. 왼쪽
    preorder(node.right)  # 3. 오른쪽

전위 순회 구현 (반복/스택)

def preorder_iterative(root):
    if not root:
        return []
 
    stack = [root]
    result = []
 
    while stack:
        node = stack.pop()
        result.append(node.val)
 
        # 오른쪽을 먼저 push → 왼쪽이 먼저 pop됨 (전위 순회 순서: 루트 -> 왼쪽 -> 오른쪽 유지)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
 
    return result

중위 순회 (In-order Traversal)

중위 순회는 이진 트리 순회 방법 중 하나로, 특히 이진 탐색 트리에서 중요한 역할을 합니다.

순서: 왼쪽 → 루트 → 오른쪽

중위 순회 결과: 1 → 2 → 3 → 4 → 5 → 6 → 7

이진 탐색 트리(Binary Search Tree)일 경우, 중위 순회를 하면 항상 오름차순 정렬된 값이 됩니다.

이진 탐색 트리는 왼쪽 서브트리는 루트보다 작은 값들, 오른쪽 서브트리는 루트보다 큰 값들, 그래서 중위 순회를 하면 항상 오름차순으로 정렬된 값이 나옵니다.

중위 순회 구현 (반복/스택)

def inorder_iterative(root):
    result = []
    stack = []
    node = root
 
    while node or stack:
        while node:
            stack.append(node)
            node = node.left  # 왼쪽 먼저 탐색
 
        node = stack.pop()
        result.append(node.val)
        node = node.right  # 오른쪽 탐색
 
    return result

후위 순회 (Post-order Traversal)

순서: 왼쪽 → 오른쪽 → 루트

후위 순회 결과: D → E → B → F → C → A

가장 마지막에 루트 노드를 방문합니다. 하위 트리를 다 처리한 후에 부모 노드를 처리하는 것이 특징입니다.

후위 순회 구현 (재귀)

def postorder(node):
    if not node:
        return
 
    postorder(node.left)     # 1. 왼쪽
    postorder(node.right)    # 2. 오른쪽
    print(node.val)          # 3. 루트

후위 순회 구현 (반복/스택)

def postorder_iterative(root):
    if not root:
        return []
 
    stack = [root]
    result = []
 
    while stack:
        node = stack.pop()
        result.append(node.val)
 
        # 왼쪽 먼저 push (그래야 나중에 pop되므로 오른쪽이 먼저 처리됨)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
 
    return result[::-1]  # 결과를 뒤집어야 후위 순서가 됨

레벨 순회 (Level-order Traversal, BFS)

트리의 각 레벨을 위에서 아래로, 왼쪽에서 오른쪽으로 순차적으로 방문합니다.
DFS 방식이 아닌 너비 우선 탐색(BFS) 방식으로, 큐(queue)를 사용해 구현합니다.

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]

활용 예시

최단 경로 탐색 (BFS 기반)
트리의 깊이 계산
레벨별 노드 그룹화 출력

전위/중위/후위/레벨 순회 비교표

순회 방식	방문 순서	방식	활용 예시
전위 (Pre-order)	루트 → 왼쪽 → 오른쪽	DFS	트리 복사, 표현식 생성
중위 (In-order)	왼쪽 → 루트 → 오른쪽	DFS	BST에서 정렬된 순서 출력
후위 (Post-order)	왼쪽 → 오른쪽 → 루트	DFS	트리 삭제
레벨 순회 (Level-order)	상위 레벨부터 좌→우	BFS	최단 경로 탐색, 트리 깊이 측정

트리 순회 (Tree Traversal)