একটি বাইনারি গাছে, প্রতিটি নোডে দুটি শিশু থাকে, যেমন, বাম শিশু এবং ডান শিশু। ধরা যাক আমাদের দুটি বাইনারি গাছ আছে এবং কাজটি হল একটি গাছের বাম দিকে অন্য গাছ উল্টিয়ে একটি গাছ পাওয়া যায় কিনা তা পরীক্ষা করা।
একটি গাছ আইসোমরফিক হয় যদি এটি অন্য গাছটিকে তার বাম পাশে উল্টিয়ে প্রাপ্ত করা যায়।
উদাহরণস্বরূপ
ইনপুট-1
আউটপুট: আইসোমরফিক
ব্যাখ্যা: প্রদত্ত ট্রি-2টি ট্রি-1-কে বাম পাশে উল্টিয়ে প্রাপ্ত করা যেতে পারে, এইভাবে গাছটি আইসোমরফিক।
এই সমস্যা সমাধানের পদ্ধতি
এই বিশেষ সমস্যাটি সমাধান করার জন্য একটি পুনরাবৃত্তিমূলক পদ্ধতি হল যে একটি বুলিয়ান ফাংশন উভয় গাছের রুট নোডের জন্য পরীক্ষা করবে। যদি উভয় গাছের শিকড় খালি বা NULL হয়, তাহলে True ফিরে আসুন এবং উভয় শিকড়ের একই ডেটা আছে কিনা তা বারবার চেক করুন। তারপরে আমরা গাছের বাম এবং ডান নোডগুলির জন্য পুনরাবৃত্তিমূলকভাবে পরীক্ষা করব।
- দুটি বাইনারি গাছের জন্য নোড তৈরি করুন।
- একটি বুলিয়ান ফাংশন isIsomorphicTree(node*r1, node*r2) দুটি গাছের শিকড় নেয় এবং গাছটি আইসোমরফিক বা না হলে ফিরে আসে।
- প্রাথমিকভাবে যদি গাছটি খালি থাকে বা এতে কোনো নোড না থাকে, তাহলে ট্রু রিটার্ন করুন।
- যদি সাবট্রি রুটেড ফ্লিপ করা না হয় এবং যদি দুটোই ফ্লিপ করা হয়, তাহলে 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
ব্যাখ্যা: প্রদত্ত গাছটি অন্য গাছটিকে তার বাম পাশে উল্টিয়ে প্রাপ্ত করা যেতে পারে, এইভাবে এটি আইসোমরফিক।
