C++で重複するすべてのサブツリーを検索する

二分木があると考えてください。ツリーに重複するサブツリーがあるかどうかを確認する必要があります。以下のような二分木があるとします-

サイズ2の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