พิจารณาว่าเรามีต้นไม้ไบนารี เราต้องค้นหาว่ามีต้นไม้ย่อยที่ซ้ำกันในต้นไม้หรือไม่ สมมติว่าเรามีไบนารีทรีด้านล่าง -
มีต้นไม้ย่อยขนาด 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
