এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম নিয়ে আলোচনা করব যা একটি বাইনারি ট্রিকে ডাবলি লিংকড লিস্টে রূপান্তর করে।
এখানে আমাদের একটি বাইনারি ট্রি দেওয়া থাকবে। আমাদের কাজ হলো সেটিকে একটি ডাবলি লিংকড লিস্টে রূপান্তর করা যাতে লেফ্ট এবং রাইট পয়েন্টারগুলো প্রিভিয়াস এবং নেক্স্ট পয়েন্টার হয়ে যায়। এছাড়া ডাবলি লিংকড লিস্টের সিকোয়েনশিয়াল অর্ডার বাইনারি ট্রির ইনঅর্ডার ট্রাভার্সালের সমান হতে হবে।
এটি করার জন্য আমরা একটি সরল পদ্ধতি अपनाয় করব। আমরা বাইনারি ট্রিকে ইনঅর্ডার পদ্ধতিতে ট্রাভার্স করব এবং সাথে সাথে ডাবলি লিংকড লিস্টের নোডগুলো তৈরি করব এবং শেষে লেফ্ট এবং রাইট কে প্রিভিয়াস এবং নেক্স্ট নোড বানাব।
উদাহরণ
#include <iostream> using namespace std; //বাইনারি ট্রির নোড স্ট্রাকচার struct node{ int data; node* left; node* right; }; //ট্রাভার্স করে ডাবলি লিংকড লিস্টের //নোড তৈরি করা void binarytodll(node *root, node **head){ if (root == NULL) return; static node* prev = NULL; //বাম সাবট্রি রূপান্তর binarytodll(root->left, head); if (prev == NULL) *head = root; else { root->left = prev; prev->right = root; } prev = root; //ডান সাবট্রি রূপান্তর binarytodll(root->right, head); } //নতুন নোড অ্যালোকেট করা node* newNode(int data) { node* new_node = new node; new_node->data = data; new_node->left = new_node->right = NULL; return (new_node); } //ডাবলি লিংকড লিস্টের নোড প্রিন্ট করা 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
