이 튜토리얼에서는 C++을 사용하여 이진 트리(Binary Tree)를 이중 연결 리스트(Doubly Linked List)로 변환하는 프로그램을 다룹니다.
이진 트리가 주어졌을 때, 트리의 왼쪽(left)과 오른쪽(right) 포인터를 각각 이중 연결 리스트의 이전(prev) 포인터와 다음(next) 포인터로 변환해야 합니다. 또한 변환된 이중 연결 리스트의 순서는 반드시 원본 이진 트리의 중위 순회(Inorder Traversal) 결과와 동일해야 합니다.
접근 방식
이 문제는 여러 가지 방법으로 해결할 수 있지만, 여기서는 역방향 중위 순회(Reverse Inorder Traversal)를 활용한 접근법을 소개합니다.
핵심 아이디어는 다음과 같습니다.
- 트리를 역방향 중위 순회(오른쪽 → 루트 → 왼쪽 순서)로 탐색합니다.
- 탐색하면서 각 노드를 새로운 이중 연결 리스트의 앞부분에 삽입합니다.
- 헤드(head) 포인터를 항상 가장 최근에 삽입된 노드로 이동시킵니다.
이렇게 하면 리스트가 뒤에서부터 앞으로 만들어지며, 최종적으로 중위 순회 순서와 일치하는 이중 연결 리스트가 완성됩니다.
C++ 구현 예제
#include <stdio.h>
#include <stdlib.h>
// 트리 노드 구조체
struct Node{
int data;
Node *left, *right;
};
// 이진 트리를 이중 연결 리스트로 변환
void binary_todll(Node* root, Node** head_ref){
if (root == NULL)
return;
// 오른쪽 서브트리 먼저 변환
binary_todll(root->right, head_ref);
// 현재 노드(루트)를 리스트 앞에 삽입
root->right = *head_ref;
// 헤드 포인터 이동
if (*head_ref != NULL)
(*head_ref)->left = root;
*head_ref = root;
// 왼쪽 서브트리 변환
binary_todll(root->left, head_ref);
}
// 새 노드 생성 함수
Node* newNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
// 이중 연결 리스트 출력
void print_dll(Node* head){
printf("Doubly Linked list:\n");
while (head) {
printf("%d ", head->data);
head = head->right;
}
}
int main(){
Node* root = newNode(5);
root->left = newNode(3);
root->right = newNode(6);
root->left->left = newNode(1);
root->left->right = newNode(4);
root->right->right = newNode(8);
root->left->left->left = newNode(0);
root->left->left->right = newNode(2);
root->right->right->left = newNode(7);
root->right->right->right = newNode(9);
Node* head = NULL;
binary_todll(root, &head);
print_dll(head);
return 0;
}실행 결과
Doubly Linked list: 0 1 2 3 4 5 6 7 8 9
동작 원리 정리
위 코드는 재귀적으로 오른쪽 서브트리를 먼저 처리한 뒤, 현재 노드를 리스트의 맨 앞에 연결하고 마지막으로 왼쪽 서브트리를 처리합니다. 이 과정 덕분에 가장 큰 값부터 처리되어 결과적으로 오름차순으로 정렬된 이중 연결 리스트가 만들어집니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 재귀 호출 스택으로 인한 공간 복잡도는 트리의 높이에 비례하여 O(h)입니다.