ধরুন আমাদের দুটি বাইনারি গাছ আছে। আমাদের পরীক্ষা করতে হবে যে ছোট গাছটি অন্য বাইনারি গাছের সাবট্রি কি না। বিবেচনা করুন এই দুটি গাছ দেওয়া হয়.
দুটি গাছ আছে। দ্বিতীয় গাছটি প্রথমটির উপবৃক্ষ। এই বৈশিষ্ট্যটি পরীক্ষা করার জন্য, আমরা পোস্ট-অর্ডার ফ্যাশনে গাছটি অতিক্রম করব, তারপর যদি এই নোডের সাথে মূলযুক্ত সাবট্রিটি দ্বিতীয় গাছের সাথে অভিন্ন হয় তবে এটি সাবট্রি।
উদাহরণ
#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
