이 자습서에서는 이진 트리를 이중 연결 목록으로 변환하는 프로그램에 대해 설명합니다.
이를 위해 이진 트리가 제공됩니다. 우리의 임무는 왼쪽 및 오른쪽 포인터가 이전 및 다음 포인터가 되도록 이중 연결 목록으로 변환하는 것입니다. 또한 이중 연결 목록의 순차 순서는 이진 트리의 중위 순회와 같아야 합니다.
이를 위해 우리는 다른 접근 방식을 취하고 있습니다. 우리는 역순으로 이진 트리를 탐색할 것입니다. 이와 함께 새 노드를 만들고 헤드 포인터를 최신 노드로 이동합니다. 이렇게 하면 끝에서 시작까지 이중 연결 목록이 생성됩니다.
예
#include <stdio.h>
#include <stdlib.h>
//node structure for tree
struct Node{
int data;
Node *left, *right;
};
//converting the binary tree to
//doubly linked list
void binary_todll(Node* root, Node** head_ref){
if (root == NULL)
return;
//converting right subtree
binary_todll(root->right, head_ref);
//inserting the root value to the
//doubly linked list
root->right = *head_ref;
//moving the head pointer
if (*head_ref != NULL)
(*head_ref)->left = root;
*head_ref = root;
//converting left subtree
binary_todll(root->left, head_ref);
}
//allocating new node for doubly linked list
Node* newNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
//printing doubly linked list
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