बाइनरी ट्री में, प्रत्येक नोड में दो बच्चे होते हैं, यानी बायां बच्चा और दायां बच्चा। मान लीजिए हमारे पास दो बाइनरी ट्री हैं और कार्य यह जांचना है कि क्या एक ट्री को दूसरे ट्री को उसके बाएं तरफ फ्लिप करके प्राप्त किया जा सकता है या नहीं।
एक ट्री आइसोमॉर्फिक है यदि इसे दूसरे ट्री को उसकी बाईं तरफ फ्लिप करके प्राप्त किया जा सकता है।
उदाहरण के लिए
इनपुट-1
आउटपुट: आइसोमॉर्फिक
व्याख्या: दिया गया ट्री-2 ट्री-1 को बाईं तरफ फ्लिप करके प्राप्त किया जा सकता है, इस प्रकार ट्री आइसोमॉर्फिक है।
इस समस्या को हल करने का दृष्टिकोण
इस विशेष समस्या को हल करने का रिकर्सिव दृष्टिकोण यह है कि एक बूलियन फ़ंक्शन दोनों ट्री के रूट नोड्स की जांच करेगा। यदि दोनों ट्री के रूट खाली या NULL हैं, तो True लौटाएं और पुनरावर्ती रूप से जांचें कि क्या दोनों रूट का डेटा समान है। फिर हम ट्री के बाएं और दाएं नोड्स के लिए पुनरावर्ती रूप से जांचेंगे।
- दो बाइनरी ट्री के लिए नोड्स बनाएं।
- एक बूलियन फ़ंक्शन isIsomorphicTree(node*r1, node*r2) दो ट्री के रूट लेता है और लौटाता है कि ट्री आइसोमॉर्फिक है या नहीं।
- प्रारंभ में यदि ट्री खाली है या इसमें कोई नोड नहीं है, तो True लौटाएं।
- यदि सबट्री रूटेड फ्लिप नहीं है और यदि दोनों फ्लिप हैं, तो True लौटाएं।
उदाहरण
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
bool isIsomorphicTree(treenode * r1, treenode * r2) {
if (r1 == NULL and r2 == NULL) {
return true;
}
if (r1 == NULL or r2 == NULL) {
return false;
}
return (r1 -> data == r2 -> data && ((isIsomorphicTree(r1 -> left, r2 -> right) && isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) && isIsomorphicTree(r1 -> right, r2 -> right))));
}
int main() {
struct treenode * r1 = createNode(1);
r1 -> left = createNode(2);
r1 -> right = createNode(3);
r1 -> left -> left = createNode(4);
r1 -> left -> right = createNode(5);
r1 -> right -> left = createNode(6);
r1 -> left -> right -> left = createNode(7);
r1 -> left -> right -> right = createNode(8);
struct treenode * r2 = createNode(1);
r2 -> left = createNode(3);
r2 -> right = createNode(2);
r2 -> right -> left = createNode(4);
r2 -> right -> right = createNode(5);
r2 -> left -> right = createNode(6);
r2 -> right -> right -> left = createNode(8);
r2 -> right -> right -> right = createNode(7);
if (isIsomorphicTree(r1, r2)) {
cout << "Isomorphic" << endl;
} else {
cout << "Not an Isomorphic" << endl;
}
return 0;
}
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
Isomorphic
व्याख्या: दिया गया ट्री दूसरे ट्री को उसकी बाईं तरफ फ्लिप करके प्राप्त किया जा सकता है, इस प्रकार यह आइसोमॉर्फिक है।
