একটি বাইনারি সার্চ ট্রি (BST) দেওয়া আছে, এবং আমাদের একটি নির্দিষ্ট কী (key) থেকে এর পথ রিভার্স করতে হবে। উদাহরণস্বরূপ:
সমাধানের পদ্ধতি
এই পদ্ধতিতে, আমরা একটি কিউ তৈরি করব এবং রুট পাওয়া পর্যন্ত সব নোড কিউতে পুশ করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; struct node { int key; struct node *left, *right; }; struct node* newNode(int item){ struct node* temp = new node; temp->key = item; temp->left = temp->right = NULL; return temp; } void inorder(struct node* root){ if (root != NULL) { inorder(root->left); cout << root->key << " "; inorder(root->right); } } void Reversing(struct node** node, int& key, queue<int>& q1){ /* যদি ট্রি খালি হয় তবে ফিরে যান*/ if (node == NULL) return; if ((*node)->key == key){ // যদি কী পাওয়া যায় q1.push((*node)->key); // আমরা কিউতে পুশ করি (*node)->key = q1.front(); // কিউয়ের প্রথম এলিমেন্টে করেন্ট বদলাই q1.pop(); // প্রথম এলিমেন্ট পপ করি } else if (key < (*node)->key){ // যদি কী করেন্ট নোডের মান থেকে ছোট হয় q1.push((*node)->key); // আমরা এলিমেন্টটি কিউতে পুশ করি Reversing(&(*node)->left, key, q1); // রিকারসিভ কল দিয়ে লেফট সাবট্রিতে যাই (*node)->key = q1.front(); // এলিমেন্টগুলো রিভার্স করি q1.pop(); // প্রথম এলিমেন্ট পপ করি } else if (key > (*node)->key){ // যদি কী নোড কী থেকে বড় হয় তবে q1.push((*node)->key);// নোড কী কিউতে পুশ করি Reversing(&(*node)->right, key, q1);// রিকারসিভ কল দিয়ে রাইট সাবট্রিতে যাই (*node)->key = q1.front();// কিউ ফ্রন্টকে নোড কীতে রিপ্লেস করি q1.pop(); // প্রথম এলিমেন্ট পপ করি } return; } struct node* insert_node(struct node* node, // আমাদের BST-এ নোড ইনসার্ট করার ফাংশন int key){ if (node == NULL) return newNode(key); // ট্রি খালি হলে নতুন নোড রিটার্ন if (key < node->key) // অন্যথায় আমরা ট্রিতে পুশ করি node->left = insert_node(node->left, key); else if (key > node->key) node->right = insert_node(node->right, key); return node; // নোড রিটার্ন } int main(){ struct node* root = NULL; queue<int> q1; int k = 80; /****************BST তৈরি*************************/ root = insert_node(root, 50); insert_node(root, 30); insert_node(root, 20); insert_node(root, 40); insert_node(root, 70); insert_node(root, 60); insert_node(root, 80); cout << "Before Reversing :" << "\n"; inorder(root); cout << "\n"; Reversing(&root, k, q1); cout << "After Reversing :" << "\n"; // রিভার্স পথ ট্রির ইনঅর্ডার প্রিন্ট inorder(root); return 0; }
আউটপুট
Before Reversing : 20 30 40 50 60 70 80 After Reversing : 20 30 40 80 60 70 50
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা সিম্পলি দেওয়া কী সার্চ করব। ট্রি ট্রাভার্স করার সময় আমরা সব নোড কিউতে পুশ করি, এবং এখন যখন কী মান সমান একটি নোড পাওয়া যায়, তবে আমরা কিউয়ের ফ্রন্ট দিয়ে পথের সব নোডের মান 스왪 (swap) করি, এবং এই প্রক্রিয়ায় আমাদের পথটি রিভার্স হয়ে যায়।
উপসংহার
আমরা একটি সমস্যা সমাধান করেছি: কিউ এবং রিকারসন ব্যবহার করে BST-এ একটি পথ রিভার্স করা। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই টিউটোরিয়ালটিকে উপকারী পাবেন।
