इस समस्या में, हमें दो बाइनरी सर्च ट्री दिए गए हैं और हमें उन नोड्स को ढूंढना है जो सामान्य हैं।
बाइनरी ट्री एक विशेष ट्री है जिसका प्रत्येक नोड अधिकतम दो चाइल्ड नोड रख सकता है। तो, प्रत्येक नोड या तो एक लीफ नोड होता है या उसके एक या दो चाइल्ड नोड होते हैं।
उदाहरण,
यहां, हमारे पास दो बाइनरी ट्री हैं और हमें उन सभी नोड्स को प्रिंट करना है जो दोनों ट्री के लिए समान हैं।
आइए एक प्रोग्राम बनाते हैं जो इस समस्या का समाधान खोजने के लिए एक सहायक स्टैक का उपयोग करता है। यह तब काम करता है जब दो समान मान उत्पन्न होते हैं तो तत्वों को पॉप करता है।
उदाहरण
#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
