Tìm tất cả các cây con trùng lặp trong C ++

Hãy xem xét chúng ta có một cây nhị phân. Chúng ta phải tìm xem có một số cây con trùng lặp trong cây hay không. Giả sử chúng ta có một cây nhị phân như dưới đây -

Có hai cây con giống nhau có kích thước là 2. Trong mỗi cây con D, BD và BE cả hai cũng là cây con trùng lặp Chúng ta có thể giải quyết vấn đề này bằng cách sử dụng quá trình tuần tự hóa và băm cây. Chúng tôi sẽ lưu trữ truyền tải nhỏ hơn của các cây con trong bảng băm. Chúng tôi sẽ chèn dấu ngoặc đơn mở và đóng cho các nút trống.

Ví dụ

#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);
}

Đầu ra

D E B