C++로 이진 트리의 미러 트리 만들기: 재귀 함수 활용 가이드

이 튜토리얼에서는 주어진 이진 트리를 좌우 반전시킨 미러 트리(Mirror Tree)를 만드는 방법을 알아봅니다. 미러 트리란 원래 트리의 모든 노드에서 왼쪽 자식과 오른쪽 자식의 위치를 서로 바꾼 트리를 의미합니다.

문제 해결 접근 방법

미러 트리를 만드는 과정은 다음 단계로 진행됩니다.

• 노드를 표현하는 구조체(struct)를 정의합니다.

• 더미 데이터로 이진 트리를 생성합니다.

• 재귀 함수를 작성하여 트리를 미러 형태로 변환합니다.

  • 왼쪽과 오른쪽 자식 노드에 대해 각각 재귀 호출을 수행합니다.

  • 왼쪽 노드와 오른쪽 노드의 포인터를 서로 교환(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 = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void convertTreeToItsMirror(struct Node* node) {
    if (node == NULL) {
        return;
    }
    else {
        struct Node* temp;
        convertTreeToItsMirror(node->left);
        convertTreeToItsMirror(node->right);
        temp = node->left;
        node->left = node->right;
        node->right = temp;
    }
}

void printTree(struct Node* node) {
    if (node == NULL) {
        return;
    }
    printTree(node->left);
    cout << node->data << " ";
    printTree(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 << "Tree: ";
    printTree(root);
    cout << endl;

    convertTreeToItsMirror(root);

    cout << "Mirror of the Tree: ";
    printTree(root);
    cout << endl;

    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Tree: 4 2 5 1 3
Mirror of the Tree: 3 1 5 2 4

동작 원리 살펴보기

convertTreeToItsMirror 함수는 후위 순회(post-order traversal) 방식으로 동작합니다. 먼저 왼쪽 서브트리와 오른쪽 서브트리를 각각 재귀적으로 변환한 뒤, 마지막으로 현재 노드의 왼쪽과 오른쪽 자식 포인터를 임시 변수 temp를 사용해 교환합니다. 이렇게 하면 리프 노드부터 루트까지 모든 노드가 순차적으로 반전되어 전체 트리가 미러 형태로 변환됩니다.

중위 순회(in-order traversal)로 출력한 결과를 비교해 보면, 원래 트리는 4 2 5 1 3, 미러 트리는 3 1 5 2 4로 정확히 좌우가 뒤바뀐 것을 확인할 수 있습니다.

마무리

이번 튜토리얼에서는 재귀 함수를 활용해 이진 트리를 미러 트리로 변환하는 방법을 배웠습니다. 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(n)입니다. 궁금한 점이 있다면 댓글로 남겨주세요.