C++ এ দুটি বাইনারি অনুসন্ধান গাছের সমস্ত উপাদান

ধরুন আমাদের দুটি বাইনারি সার্চ ট্রি আছে, আমাদেরকে মানগুলির একটি তালিকা দিতে হবে, যাতে এই গাছগুলিতে সমস্ত উপাদান উপস্থিত রয়েছে এবং তালিকার উপাদানগুলি ক্রমবর্ধমান ক্রমে থাকবে৷ তাই গাছগুলো যদি −

তাহলে আউটপুট হবে [0,1,1,2,3,4]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• উত্তর নামে একটি অ্যারে সংজ্ঞায়িত করুন, দুটি স্ট্যাক st1 এবং st2 সংজ্ঞায়িত করুন
• curr1 :=root1 এবং curr2 :=root2
• st1 তে নোড রুট 1 এবং সমস্ত বাম নোড ঢোকান, নোড রুট 2 এবং সমস্ত বাম নোডগুলি st2 এ ঢোকান
• যদিও st1 খালি নয় বা st2 খালি নয়
  • যদি st1 খালি না হয়, এবং (st2 খালি হয় অথবা st1 এর টপ নোড মান <=st2 এর টপ নোড মান)
    • temp :=st1 এর উপরে, st1 থেকে নোড মুছে দিন
    • উত্তরগুলিতে তাপমাত্রার মান সন্নিবেশ করান
    • টেম্পের ডানদিকে নোড এবং st1-এ এর সমস্ত বাম নোড সন্নিবেশ করুন
  • অন্যথায় -
    • temp :=st2 এর উপরে, st2 থেকে নোড মুছে দিন
    • উত্তরগুলিতে তাপমাত্রার মান সন্নিবেশ করান
    • টেম্পের ডানদিকে নোড এবং এর সমস্ত বাম নোড st2 তে সন্নিবেশ করুন
• উত্তর ফেরত দিন

উদাহরণ(C++)

আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = NULL;
         right = NULL;
      }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   void pushLeft(stack <TreeNode*>& st, TreeNode* root){
      TreeNode* curr = root;
      while(curr){
         st.push(curr);
         curr = curr->left;
      }
   }
   vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
      vector <int> ans;
      stack <TreeNode*> st1, st2;
      TreeNode* curr1 = root1;
      TreeNode* curr2 = root2;
      pushLeft(st1, curr1);
      pushLeft(st2, curr2);
      while(!st1.empty() || !st2.empty()){
         TreeNode* temp;
         if(!st1.empty() && (st2.empty() || st1.top()->val <= st2.top()->val)){
            temp = st1.top();
            st1.pop();
            ans.push_back(temp->val);
            pushLeft(st1, temp->right);
         }
         else{
            temp = st2.top();
            st2.pop();
            ans.push_back(temp->val);
            pushLeft(st2, temp->right);
         }
      }
      return ans;
   }
};
main(){
   vector<int> v = {2,1,4};
   TreeNode *root1 = make_tree(v);
   v = {1,0,3};
   TreeNode *root2 = make_tree(v);
   Solution ob;
   print_vector(ob.getAllElements(root1, root2));
}

ইনপুট

[2,1,4]
[1,0,3]

আউটপুট

[0,1,1,2,3,4]