इस ट्यूटोरियल में, हम एक बाइनरी ट्री को एक सर्कुलर डबल लिंक्ड लिस्ट में बदलने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें एक बाइनरी ट्री प्रदान किया जाएगा। हमारा काम बाएँ और दाएँ नोड्स को क्रमशः बाएँ और दाएँ तत्वों में बदलना होगा। और बाइनरी ट्री के इनऑर्डर को सर्कुलर लिंक्ड लिस्ट का सीक्वेंस ऑर्डर मान लें
उदाहरण
#include<iostream>
using namespace std;
//node structure of the binary tree
struct Node{
struct Node *left, *right;
int data;
};
//appending rightlist to the end of leftlist
Node *concatenate(Node *leftList, Node *rightList){
//if one list is empty return the other list
if (leftList == NULL)
return rightList;
if (rightList == NULL)
return leftList;
Node *leftLast = leftList->left;
Node *rightLast = rightList->left;
//connecting leftlist to rightlist
leftLast->right = rightList;
rightList->left = leftLast;
leftList->left = rightLast;
rightLast->right = leftList;
return leftList;
}
//converting to circular linked list and returning the head
Node *bTreeToCList(Node *root){
if (root == NULL)
return NULL;
Node *left = bTreeToCList(root->left);
Node *right = bTreeToCList(root->right);
root->left = root->right = root;
return concatenate(concatenate(left, root), right);
}
//displaying circular linked list
void print_Clist(Node *head){
cout << "Circular Linked List is :\n";
Node *itr = head;
do{
cout << itr->data <<" ";
itr = itr->right;
}
while (head!=itr);
cout << "\n";
}
//creating new node and returning address
Node *newNode(int data){
Node *temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
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 = bTreeToCList(root);
print_Clist(head);
return 0;
} आउटपुट
Circular Linked List is : 25 12 30 10 36 15