আমাদের একটি বাইনারি গাছ আছে বিবেচনা করুন. গাছে কিছু সদৃশ সাবট্রি আছে কিনা তা আমাদের খুঁজে বের করতে হবে। ধরুন আমাদের নিচের মত একটি বাইনারি গাছ আছে -
2 আকারের দুটি অভিন্ন সাবট্রি রয়েছে। প্রতিটি সাবট্রিতে D, BD এবং BE উভয়ই ডুপ্লিকেট সাবট্রিস আমরা ট্রি সিরিয়ালাইজেশন এবং হ্যাশিং প্রক্রিয়া ব্যবহার করে এই সমস্যার সমাধান করতে পারি। আমরা হ্যাশ টেবিলে সাবট্রিসের ইনঅর্ডার ট্রাভার্সাল সংরক্ষণ করব। আমরা খালি নোডের জন্য খোলা এবং বন্ধ বন্ধনী সন্নিবেশ করব।
উদাহরণ
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
const char MARKER = '$';
struct Node {
public:
char data;
Node *left, *right;
};
Node* getNode(char key) {
Node* newNode = new Node;
newNode->data = key;
newNode->left = newNode->right = NULL;
return newNode;
}
unordered_set<string> subtrees;
string inorder(Node* node, unordered_map<string, int>& map) {
if (!node)
return "";
string str = "(";
str += inorder(node->left, map);
str += to_string(node->data);
str += inorder(node->right, map);
str += ")";
if (map[str] == 1)
cout << node->data << " ";
map[str]++;
return str;
}
void duplicateSubtreeFind(Node *root) {
unordered_map<string, int> map;
inorder(root, map);
}
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');
duplicateSubtreeFind(root);
} আউটপুট
D E B
