이진 트리의 중위 순회(Inorder)와 전위 순회(Preorder) 결과가 주어졌을 때, 두 순회 정보를 바탕으로 원래의 트리를 다시 구성하는 것이 이 글의 목표입니다.
중위 순회(Inorder Traversal)란?
중위 순회는 왼쪽 서브트리 → 루트 노드 → 오른쪽 서브트리 순서로 방문하는 순회 방식입니다.
Inorder(tree root)
- 루트가 가리키는 노드의 왼쪽 서브트리를 먼저 순회합니다. → inorder(root→left) 호출
- 루트 노드 자신을 방문합니다.
- 마지막으로 오른쪽 서브트리를 순회합니다. → inorder(root→right) 호출
전위 순회(Preorder Traversal)란?
전위 순회는 루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문하는 순회 방식입니다.
Preorder(tree root)
- 루트 노드 자신을 가장 먼저 방문합니다.
- 그다음 왼쪽 서브트리를 순회합니다. → preorder(root→left) 호출
- 마지막으로 오른쪽 서브트리를 순회합니다. → preorder(root→right) 호출
아래 트리에 대한 두 순회 결과는 다음과 같습니다.
중위 순회
2-3-4-5-6-8-10
전위 순회
5-3-2-4-8-6-10
이제 주어진 전위 순회와 중위 순회 결과로 위 트리를 단계별로 다시 구성해 보겠습니다.
1단계: 루트 찾기
- 전위 순회에서는 루트 노드가 항상 가장 먼저 방문되므로, 시퀀스의 첫 번째 값이 곧 트리의 루트입니다. 위 시퀀스에서 루트는 5입니다.
2단계: 중위 순회 분할하기
- 중위 순회에서는 어떤 노드의 왼쪽 서브트리가 노드보다 먼저 순회되고, 오른쪽 서브트리가 그다음에 순회됩니다. 따라서 중위 순회에서 5의 왼쪽에 있는 값들은 모두 왼쪽 서브트리에 속하고, 오른쪽에 있는 값들은 모두 오른쪽 서브트리에 속합니다.
중위 순회
2-3-4 ← 5 → 6-8-10
3단계: 왼쪽 서브트리 구성
- 왼쪽 서브트리에 대해서도 동일한 과정을 반복합니다.
왼쪽 서브트리의 전위 순회는 3-2-4이므로, 첫 값인 3이 루트가 됩니다.
중위 순회는 다시 2 ← 3 → 4로 나뉩니다.
4단계: 오른쪽 서브트리 구성
- 오른쪽 서브트리에 대해서도 같은 방식을 적용합니다.
오른쪽 서브트리의 전위 순회는 8-6-10이므로, 첫 값인 8이 루트가 됩니다.
중위 순회는 다시 6 ← 8 → 10으로 나뉩니다.
이처럼 전위 순회로 루트를 결정하고, 중위 순회로 왼쪽·오른쪽 서브트리의 범위를 나누는 과정을 재귀적으로 반복하면 주어진 순회 결과로부터 원래의 트리를 완벽하게 재구성할 수 있습니다.
C++ 구현 예시
위 알고리즘을 C++로 구현하면 다음과 같습니다.
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
// 중위 순회 배열에서 값의 위치를 찾는 함수
int search(vector<int>& inorder, int start, int end, int value) {
for (int i = start; i <= end; i++)
if (inorder[i] == value) return i;
return -1;
}
// 트리를 재귀적으로 구성하는 함수
Node* buildTree(vector<int>& inorder, vector<int>& preorder,
int inStart, int inEnd, int& preIndex) {
if (inStart > inEnd) return nullptr;
// 전위 순회의 현재 값으로 루트 노드 생성
Node* node = new Node(preorder[preIndex++]);
if (inStart == inEnd) return node;
// 중위 순회에서 루트의 위치를 찾아 좌우 분할
int inIndex = search(inorder, inStart, inEnd, node->data);
node->left = buildTree(inorder, preorder, inStart, inIndex - 1, preIndex);
node->right = buildTree(inorder, preorder, inIndex + 1, inEnd, preIndex);
return node;
}
매번 위치를 선형 탐색으로 찾는 위 구현의 시간 복잡도는 O(n²)입니다. 해시 맵(unordered_map)을 사용해 각 값의 인덱스를 미리 저장하면 O(n)까지 최적화할 수 있습니다.