Hãy xem xét chúng ta có một cây nhị phân, cây nhị phân này không phải là một BST. Chúng ta phải kiểm tra xem cây nhị phân có chứa cùng một phần tử nhiều hơn một lần hay không. Để giải quyết điều này, chúng tôi sẽ sử dụng băm. Chúng tôi sẽ duyệt qua cây đã cho, đối với mỗi nút, chúng tôi sẽ kiểm tra xem nút đó có trong bảng hay không, nếu nút đó đã có thì trả về false, nếu không thì trả về true.
Ví dụ
#include <iostream>
#include <unordered_set>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
};
Node* getNode(int data){
Node *newNode = new Node;
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
bool hasDuplicateHelper(Node *root, unordered_set<int> &s){
if(root == NULL)
return false;
if (s.find(root->data) != s.end())
return true;
s.insert(root->data);
return hasDuplicateHelper(root->left, s) || hasDuplicateHelper(root->right, s);
}
bool hasDuplicate(Node *root){
unordered_set<int> s;
return hasDuplicateHelper(root, s);
}
int main() {
Node *root = getNode(10);
root->left = getNode(20);
root->right = getNode(20);
root->left->left = getNode(30);
if (hasDuplicate(root))
cout << "The tree has duplicate elements.";
else
cout << "The tree has no duplicate elements.";
} Đầu ra
The tree has duplicate elements.