Xét chúng ta có một cây nhị phân. Chúng ta phải tìm xem có cây con trùng lặp nào trong cây hay không. Giả sử chúng ta có một cây nhị phân như sau:
Có hai cây con trùng lặp kích thước 2. Trong mỗi cây con D, BD và BE cũng đều là cây con trùng lặp. Chúng ta có thể giải quyết bài toán này bằng cách sử dụng tuần tự hóa cây (tree serialization) và quy trình hashing. Chúng ta sẽ lưu trữ thứ tự inorder của các cây con trong bảng băm. Chúng ta sẽ chèn dấu ngoặc mở và đóng cho các nút rỗ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); }
Kết quả
D E B