C++ সারি ব্যবহার করে বিএসটি-তে একটি পথ বিপরীত করুন

একটি বাইনারি সার্চ ট্রি দেওয়া হয়েছে, এবং আমাদেরকে একটি নির্দিষ্ট কী থেকে এর পথ উল্টাতে হবে, উদাহরণস্বরূপ।

সমাধান খোঁজার পদ্ধতি

এই পদ্ধতিতে, আমরা একটি সারি তৈরি করব এবং রুট না পাওয়া পর্যন্ত সমস্ত নোডগুলিকে ঠেলে দেব।

উদাহরণ

 #include নেমস্পেস ব্যবহার করে std;struct node {int key; struct node *left, *right;};struct node* newNode(int item){struct node*temp =new node; temp->কী =আইটেম; temp->left =temp->right =NULL; রিটার্ন temp;}void inorder(struct node* root){ if (root !=NULL) { inorder(root->left); cout <কী <<" "; inorder(root->ডান); }} void Reversing(struct node** node, int&key, queue&q1){ /* যদি ট্রি খালি থাকে তাহলে রিটার্ন*/ যদি (নোড ==NULL) রিটার্ন করুন; যদি ((*নোড)->কী ==কী){// যদি আমরা q1.push((*node)->কী) খুঁজে পাই; // আমরা এটিকে আমাদের সারিতে ঠেলে দিই (*নোড)->কী =q1.front(); // আমরা বর্তমান q1.pop() দিয়ে প্রথম সারির উপাদান পরিবর্তন করি; // আমরা প্রথম উপাদানটি পপ করি } অন্যথায় যদি (কী <(*নোড)->কী){ // যদি কী বর্তমান নোডের মানের থেকে কম হয় q1.push((*node)->key); // আমরা উপাদানটিকে আমাদের সারিতে পুশ করি বিপরীতমুখী(&(*নোড)->বাম, কী, q1); // আমরা একটি রিকার্সিভ কল ব্যবহার করে বাম সাবট্রিতে যাই (*নোড)->কী =q1.front(); //আমরা উপাদানগুলি q1.pop(); // আমরা প্রথম উপাদান পপ করি } অন্যথায় যদি (কী> (*নোড)->কী){ // যদি কী নোড কী থেকে বড় হয় তাহলে q1.push((*node)->key);// আমরা নোড কী পুশ করি। কিউ রিভার্সিং(&(*নোড)->ডান, কী, q1);// আমরা রিকার্সিভ কল (*নোড)->কী =q1.front();// কিউ ফ্রন্ট নোডে প্রতিস্থাপন করে ডান সাবট্রিতে যাই কী q1.pop(); // আমরা প্রথম এলিমেন্ট পপ করি } return;}struct node* insert_node(struct node* node, // function to insert node node to insert in our BST int key){ if (node ​​==NULL) রিটার্ন newNode(key); // গাছ খালি থাকলে আমরা একটি নতুন নোড ফেরত দিই যদি (কী <নোড->কী) // অন্যথায় আমরা সেটিকে আমাদের ট্রি নোডে->বাম =সন্নিবেশ_নোড(নোড->বাম, কী) এ পুশ করি; else if (key> node->key) node->right =insert_node(node->right, key); রিটার্ন নোড; // নোড ফেরানো হচ্ছে}int main(){ struct node* root =NULL; সারি 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 <<"বিপরীত করার আগে :" <<"\n"; inorder(root); cout <<"\n"; বিপরীত করা (&root, k, q1); cout <<"আফটার রিভার্সিং :" <<"\n"; // প্রিন্ট ইনঅর্ডার রিভার্স পাথ ট্রি ইনঅর্ডার(রুট); রিটার্ন 0;

আউটপুট

উপরের কোডের ব্যাখ্যা

এই পদ্ধতিতে, আমরা কেবল প্রদত্ত কীটি অনুসন্ধান করতে যাচ্ছি। আমরা গাছের মধ্য দিয়ে যাওয়ার সময়, আমরা সমস্ত নোডগুলিকে একটি সারিতে ঠেলে দিই, এবং এখন যখন আমরা কী-এর একটি মান সহ নোডটি খুঁজে পাই, তখন আমরা সমস্ত পাথ নোডের মানগুলিকে অদলবদল করি যারা সামনে সারিবদ্ধ, এবং এই প্রক্রিয়ায়, আমাদের পথ বিপরীত হয়ে যায়।

উপসংহার

আমরা একটি সারি ব্যবহার করে এবং পুনরাবৃত্তি ব্যবহার করে বিএসটি-তে একটি পথ বিপরীত করার জন্য একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷