트리의 중위 순회(inorder)와 전위 순회(preorder) 결과가 주어졌을 때, 이를 이용해 후위 순회(postorder)를 계산하고 출력하는 프로그램을 만들어 보겠습니다.
입력:
중위 순회 in[] = {4, 2, 5, 1, 3, 6}
전위 순회 pre[] = {1, 2, 4, 5, 3, 6}
출력:
후위 순회 post[] = {4, 5, 2, 6, 3, 1}
동작 원리
이 문제는 재귀적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 전위 순회의 첫 번째 원소는 항상 현재 서브트리의 루트(root)입니다.
- 중위 순회에서 루트 값을 찾으면, 그 위치를 기준으로 왼쪽 부분은 왼쪽 서브트리, 오른쪽 부분은 오른쪽 서브트리에 해당합니다.
- 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각 재귀 호출을 수행한 뒤, 마지막에 루트를 출력하면 후위 순회 순서가 됩니다.
알고리즘
시작
1단계 → find_value(int p, int in_order[], int n) 함수 선언
i=0부터 i<n까지 반복 (++i)
만약 in_order[i] == p 라면
i 반환
반복 종료
2단계 → postorder(int pre_order[], int in_order[], int n) 함수 선언
int root = find_value(pre_order[0], in_order, n)
만약 root != 0 이라면
postorder(pre_order+1, in_order, root) 재귀 호출
만약 root != n-1 이라면
postorder(pre_order+root+1, in_order+root+1, n-root-1) 재귀 호출
pre_order[0] 출력
3단계 → main() 함수 실행
int pre_order[] = {1, 2, 4, 5, 3, 6} 선언
int in_order[] = {4, 2, 5, 1, 3, 6} 선언
int size = sizeof(pre_order)/sizeof(pre_order[0])
postorder(pre_order, in_order, size) 호출
종료
C 언어 구현 예제
#include <stdio.h>
// 중위 순회 배열에서 특정 값의 위치를 찾는 함수
int find_value(int p, int in_order[], int n) {
for (int i = 0; i < n; ++i) {
if (in_order[i] == p) {
return i;
}
}
return -1;
}
// 후위 순회를 재귀적으로 출력하는 함수
int postorder(int pre_order[], int in_order[], int n) {
int root = find_value(pre_order[0], in_order, n);
if (root != 0)
postorder(pre_order + 1, in_order, root); // 왼쪽 서브트리 처리
if (root != n - 1)
postorder(pre_order + root + 1, in_order + root + 1, n - root - 1); // 오른쪽 서브트리 처리
printf("%d ", pre_order[0]); // 루트 출력
}
int main(int argc, char const *argv[]) {
int pre_order[] = {1, 2, 4, 5, 3, 6};
int in_order[] = {4, 2, 5, 1, 3, 6};
int size = sizeof(pre_order) / sizeof(pre_order[0]);
postorder(pre_order, in_order, size);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
4 5 2 6 3 1
복잡도 분석
find_value 함수가 매번 중위 순회 배열을 선형 탐색하므로, 최악의 경우 시간 복잡도는 O(n²)입니다. 해시 맵(hash map)을 사용해 값의 인덱스를 미리 저장하면 시간 복잡도를 O(n)까지 개선할 수 있습니다. 공간 복잡도는 재귀 호출 스택 때문에 트리의 높이에 비례하여 최대 O(n)입니다.