15. 【C++】详解搜索二叉树 | KV模型

#include <iostream>
#include <string>
#include <vector>
 
// 定义节点结构体
struct Node {
    std::string key;
    std::string value;
    Node* left;
    Node* right;
 
    Node(const std::string& k, const std::string& v) : key(k), value(v), left(nullptr), right(nullptr) {}
};
 
// 插入节点
void insert(Node*& node, const std::string& key, const std::string& value) {
    if (node == nullptr) {
        node = new Node(key, value);
    } else if (key < node->key) {
        insert(node->left, key, value);
    } else if (key > node->key) {
        insert(node->right, key, value);
    } else {
        node->value = value; // 更新值
    }
}
 
// 查找节点
bool search(Node* node, const std::string& key, std::string& value) {
    if (node == nullptr) {
        return false;
    } else if (key < node->key) {
        return search(node->left, key, value);
    } else if (key > node->key) {
        return search(node->right, key, value);
    } else {
        value = node->value;
        return true;
    }
}
 
// 中序遍历
void inorder(Node* node, std::vector<std::string>& output) {
    if (node == nullptr) {
        return;
    }
    inorder(node->left, output);
    output.push_back(node->key + " " + node->value);
    inorder(node->right, output);
}
 
int main() {
    Node* root = nullptr;
 
    insert(root, "apple", "fruit");
    insert(root, "banana", "fruit");
    insert(root, "pear", "fruit");
    insert(root, "carrot", "vegetable");
    insert(root, "lettuce", "vegetable");
 
    std::string search_value;
    if (search(root, "banana", search_value)) {
        std::cout << "Found: " << search_value << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
 
    std::vector<std::string> inorder_traversal;
    inorder(root, inorder_traversal);
    for (const auto& kv : inorder_traversal) {
        std::cout << kv << std::endl;
    }
 
    // 清理内存
    // ...
 
    return 0;
}

这段代码实现了二叉搜索树的插入、查找以及中序遍历功能。它使用了KV模型，其中每个节点包含一个键值对，并且在插入时如果键已存在则更新值。代码中包含了递归的搜索和中序遍历方法，以及对应的递归结束条件。这个例子简单易懂，适合作为二叉搜索树和递归算法的入门教程。