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