जाँच करें कि कोई ट्री आइसोमॉर्फिक है या नहीं C++ में

एक बाइनरी ट्री में, प्रत्येक नोड में दो बच्चे होते हैं, अर्थात, बायाँ बच्चा और दायाँ बच्चा। मान लें कि हमारे पास दो बाइनरी ट्री हैं और कार्य यह जांचना है कि क्या एक पेड़ के बाईं ओर से दूसरे पेड़ को फ़्लिप करके प्राप्त किया जा सकता है या नहीं।

एक पेड़ आइसोमॉर्फिक होता है अगर इसे दूसरे पेड़ के बाईं ओर फ़्लिप करके प्राप्त किया जा सकता है।

उदाहरण के लिए

इनपुट-1

<मजबूत>

आउटपुट: आइसोमॉर्फिक

स्पष्टीकरण: दिए गए ट्री -2 को ट्री -1 को बाईं ओर फ़्लिप करके प्राप्त किया जा सकता है, इस प्रकार ट्री आइसोमॉर्फिक है।

इस समस्या को हल करने का तरीका

इस विशेष समस्या को हल करने के लिए एक पुनरावर्ती दृष्टिकोण यह है कि एक बूलियन फ़ंक्शन दोनों पेड़ों के रूट नोड्स की जांच करेगा। यदि दोनों पेड़ों की जड़ें खाली या NULL हैं, तो सही लौटें और दोबारा जांचें कि क्या दोनों जड़ों का डेटा समान है। फिर हम पेड़ के बाएँ और दाएँ नोड्स के लिए पुनरावर्ती रूप से जाँच करेंगे।

• दो बाइनरी ट्री के लिए नोड बनाएं।
• एक बूलियन फ़ंक्शन isIsomorphicTree(node*r1, node*r2) दो पेड़ों की जड़ें लेता है और अगर पेड़ आइसोमॉर्फिक है या नहीं तो वापस लौटता है।
• शुरुआत में अगर पेड़ खाली है या उसमें कोई नोड नहीं है, तो ट्रू लौटाएं।
• यदि रूट किए गए सबट्री फ़्लिप नहीं किए गए हैं और यदि दोनों फ़्लिप किए गए हैं, तो ट्रू वापस आएं।

उदाहरण

#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 &amp;&amp; ((isIsomorphicTree(r1 -> left, r2 -> right) &amp;&amp;       isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) &amp;&amp; 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

स्पष्टीकरण: दिए गए पेड़ को दूसरे पेड़ को उसके बाईं ओर घुमाकर प्राप्त किया जा सकता है, इस प्रकार यह आइसोमॉर्फिक है।