Kiểm tra xem Cây nhị phân có chứa các cây con trùng lặp có kích thước 2 hoặc nhiều hơn trong C ++ hay không

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 có kích thước từ 2 trở lên 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. 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. Ý tưởng là tuần tự hóa các cây con dưới dạng chuỗi và lưu trữ chúng trong bảng băm. Khi chúng tôi tìm thấy một cây được tuần tự hóa không phải là lá, đã tồn tại trong bảng băm, thì hãy trả về true.

Ví dụ

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

Đầu ra

It has dublicate subtrees of size more than 1