এই সমস্যায়, আমাদের দুটি বাইনারি অনুসন্ধান গাছ দেওয়া হয়েছে এবং আমাদের সাধারণ নোডগুলি খুঁজে বের করতে হবে৷
বাইনারি ট্রি একটি বিশেষ গাছ যার প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড নোড থাকে। সুতরাং, প্রতিটি নোড হয় একটি লিফ নোড বা একটি বা দুটি চাইল্ড নোড রয়েছে৷
উদাহরণ,
এখানে, আমাদের দুটি বাইনারি গাছ রয়েছে এবং আমাদের সমস্ত নোড প্রিন্ট করতে হবে যা উভয় গাছের জন্য একই।
আসুন একটি প্রোগ্রাম তৈরি করি যা এই সমস্যার সমাধান খুঁজতে একটি সহায়ক স্ট্যাক ব্যবহার করে। এটি পপিং উপাদান দ্বারা কাজ করে যখন দুটি একই মান দেখা দেয়।
উদাহরণ
#include<iostream>
#include<stack>
using namespace std;
struct Node{
int key;
struct Node *left, *right;
};
Node *newNode(int ele){
Node *temp = new Node;
temp->key = ele;
temp->left = temp->right = NULL;
return temp;
}
void printCommon(Node *tree1, Node *tree2){
stack<Node *> stack1, s1, s2;
while (1){
if (tree1){
s1.push(tree1);
tree1 = tree1->left;
}
else if (tree2){
s2.push(tree2);
tree2 = tree2->left;
}
else if (!s1.empty() && !s2.empty()){
tree1 = s1.top();
tree2 = s2.top();
if (tree1->key == tree2->key){
cout << tree1->key << " ";
s1.pop();
s2.pop();
tree1 = tree1->right;
tree2 = tree2->right;
}
else if (tree1->key < tree2->key){
s1.pop();
tree1 = tree1->right;
tree2 = NULL;
}
else if (tree1->key > tree2->key){
s2.pop();
tree2 = tree2->right;
tree1 = NULL;
}
}
else break;
}
}
void inorderTraversal(struct Node *root){
if (root){
inorderTraversal(root->left);
cout<<root->key<<" ";
inorderTraversal(root->right);
}
}
struct Node* insertNode(struct Node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
int main(){
Node *tree1 = NULL;
tree1=insertNode(tree1, 45);
tree1=insertNode(tree1, 87);
tree1=insertNode(tree1, 12);
tree1=insertNode(tree1, 54);
tree1=insertNode(tree1, 89);
tree1=insertNode(tree1, 19);
tree1=insertNode(tree1, 72);
cout<<"Binary Tree 1 : ";
inorderTraversal(tree1);
cout<<endl;
Node *tree2=NULL;
tree2=insertNode(tree2, 72);
tree2=insertNode(tree2, 23);
tree2=insertNode(tree2, 13);
tree2=insertNode(tree2, 1);
tree2=insertNode(tree2, 19);
cout<<"Binary Tree 2 : ";
inorderTraversal(tree2);
cout<<endl;
cout<<"Common Nodes between the two trees : ";
printCommon(tree1, tree2);
return 0;
} আউটপুট
Binary Tree 1 : 12 19 45 54 72 87 89 Binary Tree 2 : 1 13 19 23 72 Common Nodes between the two trees : 19 72
