이진 트리 순회 — 전위·중위·후위

이진 트리는 정처기 자료구조 파트에서 스택·큐 다음으로 자주 나오는 주제다. 자료구조 자체보다 그것을 순회하는 방법과 수식 트리 변환 문제가 시험에 반복해서 나온다.

트리와 이진 트리

트리(tree)는 노드와 간선으로 이루어진 계층 구조로, 사이클이 없고 루트에서 모든 노드로 가는 경로가 유일하다. 각 노드가 자식을 최대 2개까지만 가지면 이진 트리(binary tree)라 부른다. 이진 트리는 재귀적으로 정의된다 — 이진 트리는 (1) 빈 트리이거나 (2) 루트 노드 하나와 왼쪽 서브트리, 오른쪽 서브트리로 이루어지며, 두 서브트리도 각각 이진 트리다.

순회: 전위·중위·후위

트리 순회(traversal)는 모든 노드를 한 번씩 방문하는 순서를 정하는 규칙이다. 이진 트리에서는 루트(root)·왼쪽(left)·오른쪽(right)을 어떤 순서로 방문하느냐로 세 가지가 갈린다.

전위 순회(preorder): 루트 → 왼쪽 → 오른쪽
중위 순회(inorder): 왼쪽 → 루트 → 오른쪽
후위 순회(postorder): 왼쪽 → 오른쪽 → 루트

이름의 “전·중·후”는 루트를 방문하는 시점을 가리킨다. 왼쪽과 오른쪽 서브트리 자체도 같은 규칙을 재귀적으로 적용받으므로, 순회는 항상 재귀(또는 스택)로 구현한다.

예시

다음 트리를 예로 든다.

전위: 1 2 4 5 3 — 루트를 먼저 적고, 왼쪽 서브트리 전체를 전위로, 그다음 오른쪽 서브트리를 전위로 적는다.
중위: 4 2 5 1 3
후위: 4 5 2 3 1

노드 2의 서브트리(2, 4, 5)만 떼어 봐도 규칙은 같다 — 전위는 2 4 5, 중위는 4 2 5, 후위는 4 5 2. 이 재귀 구조가 트리 순회 문제를 손으로 쪼개어 풀 때의 핵심이다.

시험에 자주 나오는 포인트

수식 트리와 표기법 변환. 산술 수식을 트리로 만들면 연산자가 내부 노드, 피연산자가 리프가 된다. 이 트리를 세 방식으로 순회한 결과가 각각 전위 표기법(prefix, 폴란드 표기법), 중위 표기법(infix, 일반적으로 쓰는 수식), 후위 표기법(postfix, 역폴란드 표기법)이 된다. 예를 들어 (A+B)*C를 트리로 그리면 전위 순회 결과는 *+ABC, 후위 순회 결과는 AB+C*가 된다. 정처기에서는 중위 표기 수식을 주고 전위·후위로 바꾸라는 문제, 반대로 전위·후위 표기를 보고 원래 수식을 복원하라는 문제가 자주 나온다.

순회 결과만으로 트리를 복원하려면. 전위 순회 결과 하나만으로는 원래 트리를 유일하게 복원할 수 없다 — 루트는 알 수 있어도 왼쪽·오른쪽 서브트리의 경계가 정해지지 않기 때문이다. 중위 순회 결과와 전위(또는 후위) 순회 결과를 함께 줘야 트리가 유일하게 복원된다. 중위 순회에서 루트를 기준으로 왼쪽에 있는 노드는 전부 왼쪽 서브트리, 오른쪽은 전부 오른쪽 서브트리이므로, 전위 순회의 첫 노드(루트)를 중위 순회에서 찾아 좌우로 쪼개는 방식으로 복원한다.

레벨 순회(level-order)와의 구분. 전위·중위·후위는 모두 깊이 우선(DFS) 방식이고 재귀나 스택으로 구현한다. 이와 달리 레벨 순회는 같은 깊이의 노드를 왼쪽에서 오른쪽으로 훑는 너비 우선(BFS) 방식이며 큐로 구현한다. 위 예시 트리의 레벨 순회 결과는 1 2 3 4 5다. 정처기 문제에서 “너비 우선으로 순회하라”는 조건이 있으면 큐 기반 레벨 순회를 의미한다.