এই টিউটোরিয়ালে, আমরা একটি বাইনারি ট্রিকে দ্বিগুণ লিঙ্কযুক্ত তালিকায় রূপান্তর করার একটি প্রোগ্রাম নিয়ে আলোচনা করব৷
এর জন্য আমাদের একটি বাইনারি গাছ দেওয়া হবে। আমাদের কাজ হল এটিকে দ্বিগুণ লিঙ্কযুক্ত তালিকায় রূপান্তর করা যাতে বাম এবং ডান পয়েন্টারগুলি আগের এবং পরবর্তী পয়েন্টার হয়ে যায়। এছাড়াও দ্বিগুণ লিঙ্কযুক্ত তালিকার অনুক্রমিক ক্রম অবশ্যই বাইনারি ট্রির ইনঅর্ডার ট্রাভার্সালের সমান হতে হবে।
এই জন্য আমরা একটি খুব সোজা এগিয়ে পদ্ধতি আছে. আমরা দ্বিগুণ লিঙ্কযুক্ত তালিকার নোডগুলিকে ক্রমানুসারে বাইনারি ট্রিটি অতিক্রম করব এবং অবশেষে বাম এবং ডানকে যথাক্রমে পূর্ববর্তী এবং পরবর্তী নোড হিসাবে তৈরি করব৷
উদাহরণ
#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
