इस ट्यूटोरियल में, हम बाइनरी ट्री को डबल लिंक्ड लिस्ट में बदलने के लिए प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें एक बाइनरी ट्री प्रदान किया जाएगा। हमारा काम इसे एक डबल लिंक्ड लिस्ट में बदलना है जैसे कि बाएँ और दाएँ पॉइंटर्स पिछले और अगले पॉइंटर्स बन जाते हैं। साथ ही डबल लिंक्ड लिस्ट का अनुक्रमिक क्रम बाइनरी ट्री के इनऑर्डर ट्रैवर्सल के बराबर होना चाहिए।
इसके लिए हम अलग तरीका अपना रहे हैं। हम बाइनरी ट्री को रिवर्स इनऑर्डर तरीके से ट्रेस करेंगे। साथ ही हम नए नोड्स बनाएंगे और हेड पॉइंटर को नवीनतम में ले जाएंगे; यह अंत से शुरू तक दोहरी लिंक की गई सूची बनाएगा।
उदाहरण
#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