C++로 이진 트리를 이중 연결 리스트로 변환하는 방법 (세트 1)

개요

이 튜토리얼에서는 이진 트리(Binary Tree)를 이중 연결 리스트(Doubly Linked List)로 변환하는 C++ 프로그램을 다룹니다.

변환 시 지켜야 할 조건은 다음과 같습니다.

트리의 left 포인터는 리스트의 prev(이전) 포인터 역할을 합니다.
트리의 right 포인터는 리스트의 next(다음) 포인터 역할을 합니다.
완성된 이중 연결 리스트의 노드 순서는 반드시 이진 트리의 중위 순회(Inorder Traversal) 결과와 동일해야 합니다.

접근 방법

이 문제는 매우 직관적인 방법으로 해결할 수 있습니다. 이진 트리를 중위 순회하면서 동시에 이중 연결 리스트의 노드를 연결하고, 최종적으로 왼쪽 포인터는 이전 노드를, 오른쪽 포인터는 다음 노드를 가리키도록 설정하는 것입니다.

알고리즘의 핵심 단계를 정리하면 다음과 같습니다.

먼저 왼쪽 서브트리를 재귀적으로 변환합니다.
현재 노드를 리스트의 마지막 노드와 연결합니다. 이전에 처리한 노드가 없다면 현재 노드가 리스트의 헤드(head)가 됩니다.
마지막으로 오른쪽 서브트리를 재귀적으로 변환합니다.

C++ 구현 예제

#include <iostream>
using namespace std;
// 이진 트리의 노드 구조체
struct node{
    int data;
    node* left;
    node* right;
};
// 중위 순회하며 이중 연결 리스트 노드 생성
void binarytodll(node *root, node **head){
    if (root == NULL)
        return;
    static node* prev = NULL;
    // 왼쪽 서브트리 변환
    binarytodll(root->left, head);
    if (prev == NULL)
        *head = root;
    else {
        root->left = prev;
        prev->right = root;
    }
    prev = root;
    // 오른쪽 서브트리 변환
    binarytodll(root->right, head);
}
// 새 노드 할당
node* newNode(int data) {
    node* new_node = new node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return (new_node);
}
// 이중 연결 리스트 출력
void print_dll(node *node){
    while (node!=NULL) {
        cout << node->data << " ";
        node = node->right;
    }
}
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 = NULL;
    binarytodll(root, &head);
    print_dll(head);
    return 0;
}

실행 결과

25 12 30 10 36 15

동작 원리 설명

예제 트리의 중위 순회 순서는 25 → 12 → 30 → 10 → 36 → 15이며, 실행 결과와 정확히 일치하는 것을 확인할 수 있습니다. 여기서 핵심은 함수 내부의 static 변수 prev입니다. 이 변수는 재귀 호출 사이에도 값이 유지되므로, 직전에 처리한 노드를 기억했다가 현재 노드와 연결하는 역할을 수행합니다. 덕분에 별도의 추가 자료구조 없이 한 번의 순회만으로 트리를 이중 연결 리스트로 변환할 수 있으며, 시간 복잡도는 O(n), 공간 복잡도는 재귀 스택을 제외하면 O(1)입니다.