मान लीजिए हमारे पास दो बाइनरी ट्री हैं। हमें दोनों ट्री का पहला पत्ता ढूंढना है, जो मेल नहीं खाता। यदि कोई गैर-मेल खाने वाले पत्ते नहीं हैं, तो कुछ भी प्रदर्शित न करें।
यदि ये दो ट्री हैं, तो पहला गैर-मेल खाने वाले पत्ते 11 और 15 हैं।
यहां हम स्टैक का उपयोग करके दोनों ट्री के पुनरावृत्त प्रीऑर्डर ट्रैवर्सल को एक साथ करेंगे। हम अलग-अलग ट्री के लिए अलग-अलग स्टैक का उपयोग करेंगे। हम नोड्स को स्टैक में तब तक पुश करेंगे जब तक टॉप नोड पत्ता नोड न हो। दो टॉप की तुलना करें, यदि वे समान हैं, तो आगे की जांच करें, अन्यथा दो स्टैक टॉप तत्व दिखाएं।
उदाहरण
#include <iostream> #include <stack> using namespace std; class Node { public: int data; Node *left, *right; }; Node *getNode(int x) { Node * newNode = new Node; newNode->data = x; newNode->left = newNode->right = NULL; return newNode; } bool isLeaf(Node * t) { return ((t->left == NULL) && (t->right == NULL)); } void findUnmatchedNodes(Node *t1, Node *t2) { if (t1 == NULL || t2 == NULL) return; stack<Node*> s1, s2; s1.push(t1); s2.push(t2); while (!s1.empty() || !s2.empty()) { if (s1.empty() || s2.empty() ) return; Node *top1 = s1.top(); s1.pop(); while (top1 && !isLeaf(top1)){ s1.push(top1->right); s1.push(top1->left); top1 = s1.top(); s1.pop(); } Node * top2 = s2.top(); s2.pop(); while (top2 && !isLeaf(top2)){ s2.push(top2->right); s2.push(top2->left); top2 = s2.top(); s2.pop(); } if (top1 != NULL && top2 != NULL ){ if (top1->data != top2->data ){ cout << "First non matching leaves are: "<< top1->data <<" "<< top2->data<< endl; return; } } } } int main() { Node *t1 = getNode(5); t1->left = getNode(2); t1->right = getNode(7); t1->left->left = getNode(10); t1->left->right = getNode(11); Node * t2 = getNode(6); t2->left = getNode(10); t2->right = getNode(15); findUnmatchedNodes(t1,t2); } आउटपुट
First non matching leaves are: 11 15
