二叉搜索树（BST，Binary Search Tree）是一种二叉树数据结构，它具有以下特性：
- 每个节点包含一个键和一个值。
- 任一节点的左子树只包含键小于该节点的键的节点。
- 任一节点的右子树只包含键大于该节点的键的节点。
- 每个左右子树也分别是二叉搜索树。
- 没有键值相等的节点。
下面是一个简单的二叉搜索树的C++实现：
#include <iostream>
template<typename K, typename V>
class BST {
private:
struct Node {
Node(K key, V value) : key(key), value(value), left(nullptr), right(nullptr) {}
K key;
V value;
Node* left;
Node* right;
};
Node* root = nullptr;
Node* insert(Node* node, K key, V value) {
if (node == nullptr) {
return new Node(key, value);
}
if (key < node->key) {
node->left = insert(node->left, key, value);
} else if (key > node->key) {
node->right = insert(node->right, key, value);
} else {
node->value = value; // 键相同则更新值
}
return node;
}
Node* search(Node* node, K key) {
if (node == nullptr || key == node->key) {
return node;
}
if (key < node->key) {
return search(node->left, key);
} else {
return search(node->right, key);
}
}
// 其他二叉搜索树操作，例如删除、中序遍历等
public:
bool insert(K key, V value) {
root = insert(root, key, value);
return true;
}
Node* search(K key) {
return search(root, key);
}
// ...其他公开接口
};
int main() {
BST<int, std::string> bst;
bst.insert(1, "Apple");
bst.insert(2, "Banana");
bst.insert(3, "Cherry");
Node* node = bst.search(2);
if (node) {
std::cout << "Found: " << node->key << " -> " << node->value << std::endl;
} else {
std::cout << "Not found" << std::endl;
}
return 0;
}
这个简单的实现展示了二叉搜索树的插入和搜索操作。在实际应用中，二叉搜索树需要实现更多的操作，如删除节点、最大值和最小值的查找、树的平衡和遍历等。