이번 튜토리얼에서는 이진 트리(binary tree)를 미러 트리(mirror tree)로 변환하는 프로그램을 C++로 구현하는 방법을 알아보겠습니다.
미러 트리란 주어진 이진 트리의 좌우 서브트리를 완전히 뒤집은 형태로, 마치 거울에 비친 모습과 같습니다. 즉, 모든 노드에서 왼쪽 자식과 오른쪽 자식의 위치를 서로 교환하면 미러 트리가 됩니다.
접근 방법
미러 트리 변환은 재귀(recursion)를 활용하면 매우 간단하게 구현할 수 있습니다.
- 현재 노드가 NULL이면 그대로 반환합니다.
- 왼쪽 서브트리와 오른쪽 서브트리를 각각 재귀적으로 미러링합니다.
- 현재 노드의 왼쪽 자식과 오른쪽 자식을 임시 변수(temp)를 사용하여 서로 교환(swap)합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
// 이진 트리 노드 구조체
struct Node{
int data;
struct Node* left;
struct Node* right;
};
// 자식 노드가 없는 새로운 노드 생성
struct Node* newNode(int data){
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// 트리를 미러 트리로 변환하는 함수
void mirror(struct Node* node){
if (node == NULL)
return;
else{
struct Node* temp;
// 좌우 서브트리를 재귀적으로 변환 후 스왑
mirror(node->left);
mirror(node->right);
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
// 중위 순회(inorder traversal) 결과 출력
void print_tree(struct Node* node){
if (node == NULL)
return;
print_tree(node->left);
cout << node->data << " ";
print_tree(node->right);
}
int main(){
struct Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// 원본 트리 출력
cout << "Inorder traversal of the constructed" << endl;
print_tree(root);
mirror(root);
// 미러 트리 출력
cout << "\nInorder traversal of the mirror tree" << endl;
print_tree(root);
return 0;
}실행 결과
Inorder traversal of the constructed 4 2 5 1 3 Inorder traversal of the mirror tree 3 1 5 2 4
동작 원리 설명
위 코드에서 mirror() 함수가 핵심입니다. 재귀 호출을 통해 가장 깊은 리프 노드부터 차례대로 좌우 자식을 교환하고, 다시 위쪽으로 올라오면서 각 노드의 자식 위치를 바꿉니다. 결과적으로 전체 트리가 좌우 대칭으로 뒤집힌 미러 트리가 완성됩니다.
변환이 제대로 되었는지 확인하기 위해 중위 순회(inorder traversal) 결과를 비교했습니다. 원본 트리의 중위 순회 결과인 4 2 5 1 3이 미러 트리에서는 정확히 반대 순서인 3 1 5 2 4로 출력되는 것을 확인할 수 있습니다.
시간 및 공간 복잡도
- 시간 복잡도: O(N) — 트리의 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: O(H) — 재귀 호출 스택이 트리의 높이(H)만큼 사용됩니다. 편향된 트리의 경우 최악에 O(N)까지 증가할 수 있습니다.