Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 트리를 원형 이중 연결 리스트로 변환하는 방법

이번 튜토리얼에서는 이진 트리(Binary Tree)를 원형 이중 연결 리스트(Circular Doubly Linked List)로 변환하는 프로그램을 C++로 구현해 보겠습니다.

변환 규칙은 다음과 같습니다.

  • 트리 노드의 왼쪽(left) 자식은 연결 리스트의 이전(prev) 포인터에 대응됩니다.
  • 오른쪽(right) 자식은 다음(next) 포인터에 대응됩니다.
  • 연결 리스트의 순서는 이진 트리의 중위 순회(Inorder Traversal) 결과와 동일하게 유지합니다.

즉, 중위 순회 순서대로 노드가 배치되고, 마지막 노드가 다시 첫 번째 노드를 가리키는 원형 구조를 만드는 것이 목표입니다.

접근 방법

이 문제는 재귀적으로 해결할 수 있습니다. 각 서브트리를 독립적인 원형 연결 리스트로 변환한 뒤, 이들을 하나씩 합치는(concatenate) 방식입니다.

  1. 왼쪽 서브트리를 원형 연결 리스트로 변환합니다.
  2. 오른쪽 서브트리를 원형 연결 리스트로 변환합니다.
  3. 루트 노드 자신을 스스로를 가리키는 작은 원형 리스트로 만듭니다.
  4. 세 개의 리스트(왼쪽 리스트 + 루트 + 오른쪽 리스트)를 순서대로 연결하여 하나의 원형 리스트로 병합합니다.

두 원형 리스트를 연결할 때는 각 리스트의 마지막 노드(left 포인터가 가리키는 노드)를 활용하면 O(1) 시간에 연결이 가능합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

// 이진 트리 노드 구조체
struct Node {
    struct Node *left, *right;
    int data;
};

// leftList 뒤에 rightList를 연결하는 함수
Node *concatenate(Node *leftList, Node *rightList) {
    // 한쪽 리스트가 비어 있으면 다른 쪽을 반환
    if (leftList == NULL)
        return rightList;
    if (rightList == NULL)
        return leftList;

    // 각 리스트의 마지막 노드 찾기 (head->left가 tail)
    Node *leftLast = leftList->left;
    Node *rightLast = rightList->left;

    // 두 리스트를 서로 연결
    leftLast->right = rightList;
    rightList->left = leftLast;
    leftList->left = rightLast;
    rightLast->right = leftList;

    return leftList;
}

// 이진 트리를 원형 연결 리스트로 변환하고 헤드 반환
Node *bTreeToCList(Node *root) {
    if (root == NULL)
        return NULL;

    // 왼쪽, 오른쪽 서브트리를 재귀적으로 변환
    Node *left = bTreeToCList(root->left);
    Node *right = bTreeToCList(root->right);

    // 루트 노드를 단독 원형 리스트로 만듦
    root->left = root->right = root;

    // (왼쪽 리스트 + 루트) + 오른쪽 리스트 순으로 병합
    return concatenate(concatenate(left, root), right);
}

// 원형 연결 리스트 출력 함수
void print_Clist(Node *head) {
    cout << "Circular Linked List is :\n";
    Node *itr = head;
    do {
        cout << itr->data << " ";
        itr = itr->right;
    } while (head != itr);
    cout << "\n";
}

// 새 노드 생성 후 주소 반환
Node *newNode(int data) {
    Node *temp = new Node();
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int main() {
    Node *root = newNode(10);
    root->left = newNode(12);
    root->right = newNode(15);
    root->left->left = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);

    Node *head = bTreeToCList(root);
    print_Clist(head);

    return 0;
}

실행 결과

Circular Linked List is :
25 12 30 10 36 15

출력을 보면 트리를 중위 순회한 결과인 25 12 30 10 36 15와 정확히 일치하는 것을 확인할 수 있습니다.

동작 원리 상세 설명

1. concatenate 함수

두 개의 원형 연결 리스트를 받아 하나로 합치는 역할을 합니다. 핵심 아이디어는 원형 리스트에서 head->left가 항상 마지막(tail) 노드를 가리킨다는 점입니다. 이를 이용하면 전체 리스트를 순회하지 않고도 양쪽 끝을 O(1)에 연결할 수 있습니다.

2. bTreeToCList 함수

후위 순회(Postorder) 방식으로 동작합니다. 먼저 왼쪽과 오른쪽 서브트리를 재귀적으로 변환한 후, 현재 루트 노드의 좌우 포인터를 자기 자신에게 연결하여 독립적인 원형 리스트로 만듭니다. 마지막으로 세 개의 리스트를 중위 순회 순서(왼쪽 → 루트 → 오른쪽)에 맞게 병합합니다.

3. print_Clist 함수

원형 리스트는 끝이 없으므로 do-while문을 사용하여 시작 노드로 다시 돌아올 때까지 순회하며 값을 출력합니다.

시간 및 공간 복잡도

  • 시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다.
  • 공간 복잡도: O(h) — 재귀 호출 스택이 트리의 높이(h)만큼 사용됩니다. 편향된 트리의 경우 최악 O(n)까지 증가할 수 있습니다.

이 알고리즘은 추가 노드를 생성하지 않고 기존 트리 노드의 포인터만 재배열하므로 메모리 측면에서도 매우 효율적이라는 장점이 있습니다.