이진 트리 순회란? 전위, 중위, 후위, 레벨 순회

순회 순서가 중요한 이유

트리에는 하나의 자연스러운 순서가 없으므로 알고리즘은 작업에 맞는 순서를 고릅니다. 이진 탐색 트리를 중위 순회하면 키가 정렬된 순서로 나옵니다. 전위 순회는 부모를 자식보다 먼저 방문하므로 트리를 복사하거나, 나중에 다시 만들 수 있도록 저장할 때 필요합니다. 후위 순회는 자식을 부모보다 먼저 방문하므로 트리를 삭제하거나, 폴더 크기를 계산하거나, 수식 트리를 계산할 때 필요합니다. 레벨 순회는 가장 얕은 노드를 먼저 찾고 트리를 행 단위로 출력합니다.

하나의 예제로 보는 네 가지 순서

다음 트리를 사용합니다. 루트 1의 자식은 2와 3이고, 노드 2의 자식은 4와 5이며, 노드 3은 오른쪽 자식 6을 가집니다.

        1
       / \
      2   3
     / \   \
    4   5   6

앞의 세 가지를 쉽게 기억하는 방법은 이름이 노드의 위치를 알려 준다는 것입니다. 전(pre)은 두 서브트리보다 앞, 중(in)은 두 서브트리 사이, 후(post)는 두 서브트리 뒤입니다. 왼쪽 서브트리는 항상 오른쪽 서브트리보다 먼저 방문합니다.

재귀 구현

재귀 버전은 정의를 그대로 옮긴 것입니다. 각 함수는 서로 다른 줄에서 노드를 방문합니다.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right
def preorder(node, out):
    if node:
        out.append(node.val)
        preorder(node.left, out)
        preorder(node.right, out)
    return out
def inorder(node, out):
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    return out
def postorder(node, out):
    if node:
        postorder(node.left, out)
        postorder(node.right, out)
        out.append(node.val)
    return out
root = Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
print(preorder(root, []))   # [1, 2, 4, 5, 3, 6]
print(inorder(root, []))    # [4, 2, 5, 1, 3, 6]
print(postorder(root, []))  # [4, 5, 2, 6, 3, 1]

스택을 사용한 반복식 전위·중위 순회

재귀는 호출 스택을 사용합니다. 깊은 트리에서 재귀 한도에 걸리지 않으려면 스택을 직접 관리하세요. 전위 순회에서는 노드를 pop해 방문한 뒤, 왼쪽 자식이 먼저 처리되도록 오른쪽 자식을 왼쪽 자식보다 먼저 push합니다.

중위 순회에서는 가능한 한 왼쪽으로 내려가면서 지나온 노드를 push합니다. 더 이상 왼쪽으로 갈 수 없으면 노드를 pop해 방문하고 그 오른쪽 자식으로 이동합니다.

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return out
def inorder_iter(root):
    out, stack, node = [], [], root
    while stack or node:
        while node:              # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out
print(preorder_iter(root))  # [1, 2, 4, 5, 3, 6]
print(inorder_iter(root))   # [4, 2, 5, 1, 3, 6]

반복식 후위 순회와 레벨 순회

반복식 후위 순회가 가장 까다롭습니다. 깔끔한 방법 하나는 플래그를 쓰는 것입니다. 각 노드를 두 번 push하되, 두 번째는 자식을 모두 처리한 뒤 방문할 준비가 되었다는 표시를 붙입니다. 레벨 순회는 스택 대신 큐를 사용하며, 큐를 한 레벨씩 처리하면 각 노드의 깊이도 알 수 있습니다.

from collections import deque
def postorder_iter(root):
    out, stack = [], [(root, False)] if root else []
    while stack:
        node, children_done = stack.pop()
        if children_done:
            out.append(node.val)
        else:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    return out
def level_order(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):   # nodes of the current level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(level)
    return levels
print(postorder_iter(root))  # [4, 5, 2, 6, 3, 1]
print(level_order(root))     # [[1], [2, 3], [4, 5, 6]]

후위 순회의 또 다른 흔한 요령은 변형한 전위 순회(노드, 오른쪽, 왼쪽)를 실행한 뒤 결과를 뒤집는 것입니다.

시간 복잡도와 공간 복잡도

여기서 n은 노드 수, h는 높이, w는 최대 너비입니다. 균형 트리에서는 h가 약 log2(n)이고 w는 약 n/2가 될 수 있으며, 체인 모양 트리에서는 h가 n이고 w가 1입니다.

흔한 실수

• 반복식 전위 순회에서 왼쪽 자식을 오른쪽 자식보다 먼저 push하는 실수. 스택은 LIFO이므로 먼저 처리할 자식을 나중에 push해야 합니다.
• 빈 트리를 잊는 실수: 모든 함수는 root is None일 때 빈 결과를 반환해야 합니다.
• 레벨 순회에서 pop(0)을 쓰는 list를 큐로 사용하는 실수. pop마다 O(n)이므로 collections.deque를 쓰세요.
• 매우 깊은 트리에서 재귀에 의존하는 실수. 파이썬은 재귀 한도(기본 약 1000)에서 RecursionError를 내며 멈춥니다.
• 순회 하나로 트리를 특정할 수 있다고 기대하는 실수. 전위 순회만으로는 모호하고, 값이 서로 다르다면 전위와 중위 순회를 함께 써야 트리를 복원할 수 있습니다.

어떤 순회를 언제 쓰는가

전위, 중위, 후위 순회는 모두 깊이 우선 탐색의 한 형태이고, 레벨 순회는 트리에 적용한 너비 우선 탐색입니다. 같은 아이디어를 일반 그래프로 확장할 수 있으며, 이때는 방문한 노드의 집합도 필요합니다.