트리 순회와 수식의 표현

트리의 모든 정점을 한 번씩 방문하는 것을 순회(traversal)라고 합니다. 리스트는 앞에서부터 읽으면 되지만, 트리에는 갈래가 있어서 어느 쪽을 먼저 읽을지 정해야 합니다. 같은 트리라도 읽는 순서를 바꾸면 전혀 다른 나열이 나오고, 수식 트리에서는 그 나열이 수식을 적는 서로 다른 표기법이 됩니다. 이 글에서는 트리와 이진 트리의 구조의 이진 트리를 네 가지 순서로 순회하고, 수식을 적고 계산하는 데 어떻게 쓰이는지 살펴봅니다.

현재 정점을 언제 처리하는가

이진 트리는 비어 있거나, 루트 하나와 왼쪽 부분 트리, 오른쪽 부분 트리로 이루어진다고 정의할 수 있습니다. 순회도 이 정의를 따라 재귀로 정합니다. 현재 정점을 두 부분 트리보다 먼저 처리하면 전위 순회(preorder), 왼쪽 부분 트리와 오른쪽 부분 트리 사이에 처리하면 중위 순회(inorder), 두 부분 트리를 모두 처리한 뒤에 처리하면 후위 순회(postorder)입니다. 세 순회 모두 왼쪽 부분 트리를 오른쪽보다 먼저 읽고, 빈 부분 트리에서는 아무것도 하지 않고 돌아옵니다. 루트에서 가까운 층부터 차례로 읽는 레벨 순회(level-order)는 재귀 대신 너비 우선 탐색처럼 큐를 씁니다.

수식 $(a+b)\times c$는 루트가 곱셈이고, 왼쪽 부분 트리가 덧셈 $a+b$, 오른쪽 부분 트리가 c인 트리로 나타낼 수 있습니다. 연산자는 내부 정점에, 피연산자는 잎에 놓이고, 뺄셈처럼 순서가 중요한 연산이 있으므로 왼쪽과 오른쪽을 바꾸면 다른 수식이 됩니다.

from collections import deque


def preorder(node):
    if node is None:
        return []
    value, left, right = node
    return [value] + preorder(left) + preorder(right)


def inorder(node):
    if node is None:
        return []
    value, left, right = node
    return inorder(left) + [value] + inorder(right)


def postorder(node):
    if node is None:
        return []
    value, left, right = node
    return postorder(left) + postorder(right) + [value]


def level_order(node):
    order, queue = [], deque([node])
    while queue:
        value, left, right = queue.popleft()
        order.append(value)
        queue.extend(child for child in (left, right) if child is not None)
    return order


def infix(node):
    value, left, right = node
    if left is None:
        return value
    return f"({infix(left)} {value} {infix(right)})"


def leaf(value):
    return (value, None, None)


expression = ("*", ("+", leaf("a"), leaf("b")), leaf("c"))
for visit in (preorder, inorder, postorder, level_order):
    print(f"{visit.__name__:11}", " ".join(visit(expression)))
print(infix(expression))

preorder    * + a b c
inorder     a + b * c
postorder   a b + c *
level_order * + c a b
((a + b) * c)

정점은 (값, 왼쪽, 오른쪽) 튜플이고 빈 부분 트리는 None입니다. 세 재귀 함수는 [value]를 붙이는 위치만 다릅니다. f"{visit.__name__:11}"은 함수 이름을 11칸에 맞추어 출력을 정렬합니다. 재귀 함수가 모든 트리에서 맞는다는 것은 수학적 귀납법을 트리의 구조에 적용해 보일 수 있습니다. 빈 트리에서 맞고, 두 부분 트리에서 맞는다고 가정하면 그 둘을 붙인 트리에서도 맞기 때문입니다.

전위 순회의 결과 * + a b c를 전위 표기(prefix notation), 후위 순회의 결과 a b + c *를 후위 표기(postfix notation)라고 합니다. 두 표기는 괄호가 없어도 계산 순서가 하나로 정해집니다. 반면 중위 순회의 결과 a + b * c는 우리가 평소에 쓰는 순서이지만, 곱셈을 먼저 하는 관례에 따라 읽으면 $a+(b\times c)$라는 다른 수식이 됩니다. 그래서 중위 표기로 적을 때는 infix처럼 부분 트리마다 괄호를 둘러야 원래 트리를 잃지 않습니다.

후위 표기는 스택으로 계산한다

후위 표기는 연산자가 두 피연산자 뒤에 오므로, 왼쪽부터 읽으면서 수를 쌓아 두었다가 연산자를 만날 때 바로 계산할 수 있습니다. 이때 연산자는 가장 나중에 쌓은 두 수를 꺼내 씁니다. 이렇게 가장 나중에 넣은 것을 가장 먼저 꺼내는 구조를 스택(stack)이라고 하며, 자료구조·알고리즘 교재의 스택과 깊이 우선 탐색 DFS에서 자세히 다룹니다. a = 2, b = 3, c = 4로 두고 2 3 + 4 *를 계산하는 과정을 단계별로 보겠습니다.

2와 3을 스택에 쌓은 뒤 +를 만나면 두 수를 꺼내 더한 5를 다시 쌓습니다. 4를 쌓고 *를 만나면 5와 4를 꺼내 곱한 20을 쌓고, 입력이 끝났을 때 스택에 남은 하나가 답입니다. 이것은 수식 트리를 후위 순회하면서 각 연산자 정점에서 두 자식의 값을 받아 계산하는 것과 같습니다.

def evaluate_postfix(tokens):
    stack = []
    for token in tokens:
        if token not in ("+", "-", "*"):
            stack.append(int(token))
            continue
        if len(stack) < 2:
            raise ValueError(f"{token} 앞에 피연산자가 부족합니다")
        right = stack.pop()
        left = stack.pop()
        if token == "+":
            stack.append(left + right)
        elif token == "-":
            stack.append(left - right)
        else:
            stack.append(left * right)
    if len(stack) != 1:
        raise ValueError("연산자가 부족해 값이 하나로 모이지 않습니다")
    return stack[0]


for text in ("2 3 + 4 *", "8 2 -", "1 +", "1 2"):
    try:
        print(text, "=", evaluate_postfix(text.split()))
    except ValueError as error:
        print(text, "오류:", error)

2 3 + 4 * = 20
8 2 - = 6
1 + 오류: + 앞에 피연산자가 부족합니다
1 2 오류: 연산자가 부족해 값이 하나로 모이지 않습니다

스택에서 먼저 꺼낸 값이 오른쪽 피연산자이고, 두 번째로 꺼낸 값이 왼쪽 피연산자입니다. 8 2 -에서 2를 먼저 꺼내므로 결과는 8 − 2 = 6이며, 꺼낸 순서대로 계산해 2 − 8을 만들면 틀립니다. 연산자를 만났는데 수가 둘보다 적거나, 다 읽었는데 수가 둘 이상 남으면 올바른 후위 표기가 아니므로 오류를 냅니다. 이 계산기는 정수와 +, −, *만 다루는 작은 예이며, 실제 프로그래밍 언어의 수식 해석기는 우선순위와 괄호가 있는 중위 표기를 먼저 트리나 후위 표기로 바꾼 뒤 계산합니다.

순회 결과로 트리를 되찾을 수 있을까

순회는 트리를 나열로 바꾸는데, 거꾸로 나열에서 트리를 되찾을 수 있는지도 물을 수 있습니다. 정점의 값이 모두 다르면 전위 순회와 중위 순회를 함께 알 때 트리가 하나로 정해집니다. 전위 순회의 첫 값이 루트이고, 중위 순회에서 그 루트의 왼쪽에 있는 값들이 왼쪽 부분 트리, 오른쪽에 있는 값들이 오른쪽 부분 트리이므로, 같은 일을 부분 트리마다 되풀이하면 되기 때문입니다.

수식 트리는 이것보다 더 쉽습니다. 연산자의 자식이 언제나 둘이고 피연산자는 잎이므로, 전위 표기나 후위 표기 하나만으로 트리가 정해집니다. 앞의 계산기가 후위 표기만 보고 계산 순서를 정할 수 있었던 이유입니다.

더 깊이: 중위 순회 하나로는 왜 부족한가

정점이 n개인 이진 트리의 모양이 몇 가지인지 세어 보면, 중위 순회 하나만으로 트리를 되찾을 수 없는 이유가 분명해집니다. 모양의 수를 $C_n$이라 하면, 빈 트리 하나뿐인 $C_0=1$에서 시작해 루트를 하나 두고 나머지 n개를 왼쪽 부분 트리에 k개, 오른쪽 부분 트리에 $n-k$개로 나누는 경우를 모두 더하면 됩니다. 그래서 $C_{n+1}=\sum_{k=0}^{n}C_kC_{n-k}$이고, 차례로 계산하면 $C_1=1$, $C_2=2$, $C_3=1\cdot2+1\cdot1+2\cdot1=5$, $C_4=14$입니다.

이 값들은 카탈랑 수(Catalan number)라는 수열로, OEIS의 A000108이 적어 둔 대로 $C_n=\binom{2n}{n}/(n+1)$이라는 닫힌 식도 있습니다. $n=3$이면 $\binom63/4=20/4=5$로 위의 계산과 같습니다. 괄호를 짝지어 여는 방법, 볼록 다각형을 대각선으로 삼각형으로 나누는 방법처럼 겉보기에 다른 여러 문제의 답이 같은 수열로 나옵니다.

정점의 값을 1, 2, 3으로 두고 중위 순회가 1, 2, 3이 되도록 값을 놓으면, 이렇게 센 다섯 모양 모두에 값을 놓을 수 있습니다. 중위 순회가 같은 트리가 다섯 개나 되는 셈이므로 중위 순회 하나로는 트리가 정해지지 않고, 전위 순회처럼 루트를 알려 주는 정보가 함께 있어야 합니다. 같은 이유로 1부터 n까지의 키로 만들 수 있는 이진 탐색 트리의 모양도 $C_n$가지입니다.

정리

• 전위, 중위, 후위 순회는 현재 정점을 두 부분 트리보다 먼저, 사이에, 나중에 처리하는 것만 다르고, 레벨 순회는 큐로 얕은 층부터 읽습니다.
• 수식 트리를 전위, 후위 순회하면 괄호 없이도 계산 순서가 정해지는 전위, 후위 표기가 나오고, 중위 표기는 괄호를 붙여야 원래 수식을 지킵니다.
• 후위 표기는 스택으로 계산하며, 먼저 꺼낸 값이 오른쪽 피연산자입니다.
• 값이 모두 다르면 전위 순회와 중위 순회로 트리를 되찾을 수 있고, 수식 트리는 전위나 후위 표기 하나로 정해집니다.

연습 문제

1. 네 가지 순회

앞 글의 트리, 곧 루트 8의 자식이 3과 10이고 3의 자식이 1과 6인 트리의 전위, 중위, 후위, 레벨 순회 결과를 쓰세요.

2. 후위 표기를 중위 표기로

후위 표기 7 2 3 + -의 값을 구하고, 괄호를 넣은 중위 표기로 바꾸세요.

3. 되찾을 수 없는 트리

전위 순회와 후위 순회를 모두 알아도 트리가 하나로 정해지지 않는 예를 드세요.

순회 결과가 예상과 다르면 현재 정점을 기록하는 줄이 재귀 호출의 앞, 사이, 뒤 가운데 어디에 있는지 확인해 보세요. 다음 글 이진 탐색 트리의 검색과 수정에서는 중위 순회가 언제나 정렬된 순서를 내도록 값을 배치한 트리를 다룹니다.