이진 트리 순회와 수식 표기

이진 트리의 순회(traversal)는 모든 노드를 한 번씩 정해진 차례로 방문하는 것이고, 루트를 언제 읽느냐에 따라 전위·중위·후위 순회로 나뉩니다. 한 줄인 선형 구조는 앞에서부터 읽으면 되지만, 트리는 갈림길마다 어느 쪽을 먼저 갈지 정해야 읽는 차례가 하나로 정해집니다. 수식을 트리로 그려 순회하면 연산자를 앞이나 뒤에 두는 전위 식·후위 식이 만들어져, 괄호 없이 계산 차례를 적을 수 있습니다. 아래 그림은 순회 점이 트리를 돌며 방문한 차례대로 글자를 적고, 수식 트리에서 후위 식이 만들어지는 모습을 보입니다.

1세 순회 — 루트를 언제 적나

어떤 노드와 그 아래 노드 전체를 서브트리(subtree)라 합니다. 세 순회는 모두 왼쪽 서브트리를 오른쪽보다 먼저 읽고, 루트를 적는 때만 다릅니다.

서브트리 안에서도 같은 규칙을 되풀이합니다. 중위 순회는 A를 적기 전에 왼쪽 서브트리(B와 D)를 다 읽는데, 그 안에서도 왼쪽 D가 B보다 먼저입니다. 자식이 하나뿐이면 왼쪽인지 오른쪽인지 꼭 봅니다. D가 B의 오른쪽 자식이면 중위 순회는 B D A E C F입니다.

2수식 트리와 세 표기

수식을 트리로 그리면 연산자가 비단말 노드, 피연산자가 단말 노드가 되고, 먼저 계산하는 부분이 아래에 놓입니다. (A + B) * C의 트리는 루트가 *이고, 왼쪽 자식이 +(그 아래 A·B), 오른쪽 자식이 C입니다.

평소의 중위 표기는 트리를 그대로 읽으면 괄호가 빠져 B * C를 먼저 계산하는 식처럼 보여, 괄호가 따로 있어야 합니다. 전위·후위 표기는 괄호 없이도 계산 차례가 하나로 정해집니다. 자료에 따라 전위 표기를 폴란드 표기, 후위 표기를 역폴란드 표기라고도 부릅니다. 후위 식은 스택(스택과 큐)으로 계산합니다. 값은 스택에 넣고, 연산자를 만나면 두 값을 꺼내 계산한 결과를 다시 넣습니다. 먼저 꺼낸 값이 오른쪽이라 A B -는 A − B입니다.

예제

중위 식을 후위·전위 식으로 바꾸기

트리 없이 괄호로 바꾸는 방법을 A + B * C - D로 해 봅니다.

피연산자 A·B·C·D의 차례는 세 표기에서 같고, 연산자의 자리만 바뀝니다. 답을 맞춰 볼 때 이 점을 먼저 봅니다.

Python 이진 트리 후위 순회

노드를 클래스(class)로 만들고, 함수 walk가 자기 자신을 다시 부르는 재귀로 트리를 돕니다. 클래스는 34단원에서 배웁니다.

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


def walk(n):
    if n is None:
        return
    walk(n.left)
    walk(n.right)
    print(n.v, end='')

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.right.left = Node('E')
root.right.right = Node('F')
walk(root)
print()

DBEFCA

13번 줄의 print가 두 재귀 호출(11·12번 줄) 뒤에 있어 루트를 나중에 적는 후위 순회입니다. print를 11번 줄 앞으로 옮기면 전위 순회, 두 호출 사이로 옮기면 중위 순회가 됩니다. 마지막 print()는 줄만 바꿉니다.

시험 포인트

• 필기: 전위(루트 먼저)·중위(루트 가운데)·후위(루트 나중) 순회의 결과를 쓰는 문제와, 중위 식을 전위·후위 식으로 바꾸는 문제가 자주 나옵니다. 세 순회 모두 왼쪽 서브트리를 먼저 읽고, 자식이 하나일 때 왼쪽인지 오른쪽인지가 중위 결과를 바꿉니다. 식 바꾸기는 계산 차례대로 괄호로 묶고 연산자를 괄호 왼쪽 밖(전위)이나 오른쪽 밖(후위)으로 옮깁니다. 피연산자의 차례가 바뀐 보기는 바로 지웁니다.
• 실기: Python·C 이진 트리 순회 코드의 출력을 그대로 씁니다. 출력 줄이 두 재귀 호출의 앞·사이·뒤 어디에 있는지로 순회를 가립니다. 이름은 전위 순회(Preorder Traversal)·중위 순회(Inorder Traversal)·후위 순회(Postorder Traversal)로 씁니다.

확인 문제

1. 다음 표의 이진 트리를 중위 순회한 결과를 고르세요.

• ① 2 4 1 7 5 3 6
• ② 4 2 1 7 5 3 6
• ③ 1 2 4 3 5 7 6
• ④ 4 2 7 5 6 3 1

2. 다음 (가)~(다)처럼 트리를 도는 순회의 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 폴더 크기를 셀 때, 안에 든 하위 폴더들의 크기를 모두 구한 뒤에야 그 폴더의 크기를 정합니다.
• (나) 책 목차를 찍을 때 장 제목을 먼저 찍고, 그 아래 절들을 차례로 찍습니다.
• (다) 수식 트리를 읽어, 연산자가 두 피연산자 사이에 오는 평소 수식 꼴로 적습니다.

3. 예제 코드의 13번 줄을 11번 줄과 12번 줄 사이로 옮겼습니다. 출력을 그대로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

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


def walk(n):
    if n is None:
        return
    walk(n.left)
    print(n.v, end='')
    walk(n.right)

root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.right.left = Node('E')
root.right.right = Node('F')
walk(root)
print()

DBAECF