इस ट्यूटोरियल में, हम बाइनरी ट्री को डबल लिंक्ड लिस्ट में बदलने के लिए प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें एक बाइनरी ट्री प्रदान किया जाएगा। हमारा काम इसे एक डबल लिंक्ड लिस्ट में बदलना है जैसे कि बाएँ और दाएँ पॉइंटर्स पिछले और अगले पॉइंटर्स बन जाते हैं। साथ ही डबल लिंक्ड लिस्ट का अनुक्रमिक क्रम बाइनरी ट्री के इनऑर्डर ट्रैवर्सल के बराबर होना चाहिए।
इसके लिए हम बहुत सीधे तौर पर आगे बढ़ रहे हैं। हम डबल लिंक्ड लिस्ट के नोड्स बनाने के क्रम में बाइनरी ट्री को ट्रैवर्स करेंगे और अंत में बाएँ और दाएँ को क्रमशः पिछले और अगले नोड बनाएँगे।
उदाहरण
#include <iostream>
using namespace std;
//node structure of binary tree
struct node{
int data;
node* left;
node* right;
};
//traversing and making nodes for
//doubly linked list
void binarytodll(node *root, node **head){
if (root == NULL)
return;
static node* prev = NULL;
//converting left subtree
binarytodll(root->left, head);
if (prev == NULL)
*head = root;
else {
root->left = prev;
prev->right = root;
}
prev = root;
//converting right subtree
binarytodll(root->right, head);
}
//allocating a new node
node* newNode(int data) {
node* new_node = new node;
new_node->data = data;
new_node->left = new_node->right = NULL;
return (new_node);
}
//printing nodes of doubly linked list
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