【深入C++】二叉搜索树

二叉搜索树（BST，Binary Search Tree）是一种二叉树数据结构，它具有以下特性：

1. 每个节点包含一个键和一个值。
2. 任一节点的左子树只包含键小于该节点的键的节点。
3. 任一节点的右子树只包含键大于该节点的键的节点。
4. 每个左右子树也分别是二叉搜索树。
5. 没有键值相等的节点。

下面是一个简单的二叉搜索树的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;
}

这个简单的实现展示了二叉搜索树的插入和搜索操作。在实际应用中，二叉搜索树需要实现更多的操作，如删除节点、最大值和最小值的查找、树的平衡和遍历等。