C++로 구현하는 더블 트리(Double Tree): 예제 코드와 단계별 설명

이번 튜토리얼에서는 주어진 이진 트리를 더블 트리(Double Tree)로 변환하는 방법을 알아보겠습니다.

더블 트리란?

더블 트리는 기존 트리의 각 노드 왼쪽에 자신과 같은 값을 가진 새로운 노드를 하나씩 추가하여 만든 트리입니다. 즉, 모든 원래 노드가 복제되어 왼쪽 자식 자리에 삽입된 형태가 됩니다.

문제 해결 절차

다음 순서대로 문제를 해결할 수 있습니다.

• 노드(node) 클래스를 생성합니다.
• 더미 데이터로 트리를 초기화합니다.
• 트리를 두 배로 만드는 재귀 함수를 작성합니다.
  • 트리를 재귀적으로 순회합니다.
  • 왼쪽 자식 노드를 변수에 임시 저장합니다.
  • 순회 후 현재 노드의 데이터로 새 노드를 생성합니다.
  • 새로 생성한 노드의 왼쪽 자식으로 기존 왼쪽 노드를 연결합니다.
• 변환된 트리를 출력합니다.

C++ 예제 코드

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

class node {
    public:
    int data;
    node* left;
    node* right;
};

node* newNode(int data) {
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return Node;
}

void doubleTree(node* Node) {
    node* oldLeft;
    if (Node == NULL) return;
    doubleTree(Node->left);
    doubleTree(Node->right);
    oldLeft = Node->left;
    Node->left = newNode(Node->data);
    Node->left->left = oldLeft;
}

void printTree(node* node) {
    if (node == NULL) {
        return;
    }
    printTree(node->left);
    cout << node->data << " ";
    printTree(node->right);
}

int main() {
    node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);

    cout << "Original Tree" << endl;
    printTree(root);
    cout << endl;

    doubleTree(root);

    cout << "Double Tree" << endl;
    printTree(root);
    cout << endl;

    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

Original Tree
2 1 3
Double Tree
2 2 1 1 3 3

동작 원리 살펴보기

doubleTree 함수는 후위 순회(postorder traversal) 방식으로 동작합니다. 먼저 왼쪽과 오른쪽 서브트리를 각각 재귀적으로 처리한 뒤, 현재 노드의 데이터를 복제한 새 노드를 만들어 왼쪽 자식으로 삽입하고, 원래의 왼쪽 자식은 새 노드의 왼쪽 자식으로 연결합니다. 이 과정을 통해 중위 순회 시 각 값이 연속해서 두 번 나타나는 것을 확인할 수 있습니다.

마무리

이번 튜토리얼에서는 C++ 재귀 함수를 활용해 이진 트리를 더블 트리로 변환하는 방법을 배웠습니다. 코드 진행에 대해 궁금한 점이 있다면 댓글로 남겨주세요.