मान लीजिए कि हमारे पास दो बाइनरी ट्री हैं। हमें यह जांचना होगा कि छोटा पेड़ दूसरे बाइनरी ट्री का सबट्री है या नहीं। गौर कीजिए कि ये दो पेड़ दिए गए हैं।
दो पेड़ हैं। दूसरा वृक्ष पहले वाले का उपवृक्ष है। इस संपत्ति की जांच करने के लिए, हम पेड़ को पोस्ट-ऑर्डर फैशन में पार करेंगे, फिर यदि इस नोड के साथ रूट किया गया सबट्री दूसरे पेड़ के समान है, तो यह सबट्री है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class node {
public:
int data;
node *left, *right;
};
bool areTwoTreeSame(node * t1, node *t2) {
if (t1 == NULL && t2 == NULL)
return true;
if (t1 == NULL || t2 == NULL)
return false;
return (t1->data == t2->data && areTwoTreeSame(t1->left, t2->left) && areTwoTreeSame(t1->right, t2->right) );
}
bool isSubtree(node *tree, node *sub_tree) {
if (sub_tree == NULL)
return true;
if (tree == NULL)
return false;
if (areTwoTreeSame(tree, sub_tree))
return true;
return isSubtree(tree->left, sub_tree) || isSubtree(tree->right, sub_tree);
}
node* getNode(int data) {
node* newNode = new node();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
int main() {
node *real_tree = getNode(26);
real_tree->right = getNode(3);
real_tree->right->right = getNode(3);
real_tree->left = getNode(10);
real_tree->left->left = getNode(4);
real_tree->left->left->right = getNode(30);
real_tree->left->right = getNode(6);
node *sub_tree = getNode(10);
sub_tree->right = getNode(6);
sub_tree->left = getNode(4);
sub_tree->left->right = getNode(30);
if (isSubtree(real_tree, sub_tree))
cout << "Second tree is subtree of the first tree";
else
cout << "Second tree is not a subtree of the first tree";
} आउटपुट
Second tree is subtree of the first tree