এই টিউটোরিয়ালে, আমরা একটি বাইনারি ট্রিকে দ্বিগুণ লিঙ্কযুক্ত তালিকায় রূপান্তর করার একটি প্রোগ্রাম নিয়ে আলোচনা করব৷
এর জন্য আমাদের একটি বাইনারি গাছ দেওয়া হবে। আমাদের কাজ হল এটিকে দ্বিগুণ লিঙ্কযুক্ত তালিকায় রূপান্তর করা যাতে বাম এবং ডান পয়েন্টারগুলি আগের এবং পরবর্তী পয়েন্টার হয়ে যায়। এছাড়াও দ্বিগুণ লিঙ্কযুক্ত তালিকার অনুক্রমিক ক্রম অবশ্যই বাইনারি ট্রির ইনঅর্ডার ট্রাভার্সালের সমান হতে হবে।
এ জন্য আমরা ভিন্ন পন্থা অবলম্বন করছি। আমরা বাইনারি ট্রিকে বিপরীত ক্রমানুসারে অতিক্রম করব। পাশাপাশি আমরা নতুন নোড তৈরি করব এবং হেড পয়েন্টারটিকে সর্বশেষে নিয়ে যাব; এটি শেষ থেকে শুরু পর্যন্ত দ্বিগুণ লিঙ্কযুক্ত তালিকা তৈরি করবে।
উদাহরণ
#include <stdio.h>
#include <stdlib.h>
//node structure for tree
struct Node{
int data;
Node *left, *right;
};
//converting the binary tree to
//doubly linked list
void binary_todll(Node* root, Node** head_ref){
if (root == NULL)
return;
//converting right subtree
binary_todll(root->right, head_ref);
//inserting the root value to the
//doubly linked list
root->right = *head_ref;
//moving the head pointer
if (*head_ref != NULL)
(*head_ref)->left = root;
*head_ref = root;
//converting left subtree
binary_todll(root->left, head_ref);
}
//allocating new node for doubly linked list
Node* newNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
//printing doubly linked list
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
