এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম নিয়ে আলোচনা করব যা একটি বাইনারি ট্রিকে ডাবলি লিংকড লিস্টে রূপান্তর করে।
এখানে আমাদের একটি বাইনারি ট্রি দেওয়া থাকবে। আমাদের কাজ হলো সেটিকে একটি ডাবলি লিংকড লিস্টে রূপান্তর করা যাতে লেফ্ট এবং রাইট পয়েন্টারগুলো প্রিভিয়াস এবং नेक्स্ট পয়েন্টার হয়ে যায়। এছাড়া ডাবলি লিংকড লিস্টের সিকোয়েনশিয়াল অর্ডার বাইনারি ট্রির ইনঅর্ডার ট্রাভার্সালের সমান হতে হবে।
এটি করার জন্য আমরা একটি ভিন্ন পদ্ধতি अपनाয় করব। আমরা বাইনারি ট্রিকে রিভার্স ইনঅর্ডার পদ্ধতিতে ট্রাভার্স করব। সাথে সাথে নতুন নোড তৈরি করব এবং হেড পয়েন্টারকে লেটেস্ট টায় মুভ করব; এতে ডাবলি লিংকড লিস্ট শেষ থেকে শুরু দিকে তৈরি হবে।
উদাহরণ
#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
