আমাদের একটি বাইনারি গাছ আছে বিবেচনা করুন. আমাদের খুঁজে বের করতে হবে যে গাছে 2 বা তার বেশি আকারের কিছু ডুপ্লিকেট সাবট্রি আছে কি না। ধরুন আমাদের নিচের মত একটি বাইনারি গাছ আছে -
2 আকারের দুটি অভিন্ন সাবট্রি রয়েছে। আমরা ট্রি সিরিয়ালাইজেশন এবং হ্যাশিং প্রক্রিয়া ব্যবহার করে এই সমস্যার সমাধান করতে পারি। ধারণাটি সাবট্রিকে স্ট্রিং হিসাবে ক্রমিককরণ করা হয় এবং সেগুলিকে হ্যাশ টেবিলে সংরক্ষণ করে। একবার আমরা একটি ক্রমিক গাছ খুঁজে পাই যেটি পাতা নয়, ইতিমধ্যেই হ্যাশ টেবিলে বিদ্যমান, তারপর সত্য ফিরে আসুন।
উদাহরণ
#include <iostream>
#include <unordered_set>
using namespace std;
const char MARKER = '$';
struct Node {
public:
char key;
Node *left, *right;
};
Node* getNode(char key) {
Node* newNode = new Node;
newNode->key = key;
newNode->left = newNode->right = NULL;
return newNode;
}
unordered_set<string> subtrees;
string duplicateSubtreeFind(Node *root) {
string res = "";
if (root == NULL) // If the current node is NULL, return $
return res + MARKER;
string l_Str = duplicateSubtreeFind(root->left);
if (l_Str.compare(res) == 0)
return res;
string r_Str = duplicateSubtreeFind(root->right);
if (r_Str.compare(res) == 0)
return res;
res = res + root->key + l_Str + r_Str;
if (res.length() > 3 && subtrees.find(res) != subtrees.end()) //if subtree is present, then return blank string return "";
subtrees.insert(res);
return res;
}
int main() {
Node *root = getNode('A');
root->left = getNode('B');
root->right = getNode('C');
root->left->left = getNode('D');
root->left->right = getNode('E');
root->right->right = getNode('B');
root->right->right->right = getNode('E');
root->right->right->left= getNode('D');
string str = duplicateSubtreeFind(root);
if(str.compare("") == 0)
cout << "It has dublicate subtrees of size more than 1";
else
cout << "It has no dublicate subtrees of size more than 1" ;
} আউটপুট
It has dublicate subtrees of size more than 1
