C++二叉搜索树查找操作详解（从零开始掌握BST查找算法）

BST查找操作的原理

由于BST具有有序性，查找一个值的时间复杂度平均为 O(log n)，比普通线性查找快得多。查找过程如下：

1. 从根节点开始比较；
2. 如果目标值等于当前节点值，查找成功；
3. 如果目标值小于当前节点值，进入左子树继续查找；
4. 如果目标值大于当前节点值，进入右子树继续查找；
5. 如果到达空节点仍未找到，则说明值不存在。

C++实现BST查找操作

下面我们一步步用C++实现BST的查找功能。

1. 定义节点结构

struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;        // 构造函数    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};  

2. 实现递归查找函数

递归是最直观的实现方式：

TreeNode* searchBST(TreeNode* root, int target) {    // 基本情况：节点为空或找到目标    if (root == nullptr || root->val == target) {        return root;    }        // 如果目标值小于当前节点值，搜索左子树    if (target < root->val) {        return searchBST(root->left, target);    }        // 否则搜索右子树    return searchBST(root->right, target);}  

3. 实现迭代查找函数（更节省栈空间）

TreeNode* searchBSTIterative(TreeNode* root, int target) {    TreeNode* current = root;    while (current != nullptr) {        if (current->val == target) {            return current;  // 找到目标        }        if (target < current->val) {            current = current->left;  // 进入左子树        } else {            current = current->right; // 进入右子树        }    }    return nullptr;  // 未找到}  

完整示例代码

下面是一个完整的可运行示例，包含插入和查找操作：

#include <iostream>using namespace std;struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};// 插入节点（用于构建BST）TreeNode* insert(TreeNode* root, int val) {    if (!root) return new TreeNode(val);    if (val < root->val)        root->left = insert(root->left, val);    else        root->right = insert(root->right, val);    return root;}// 递归查找TreeNode* searchBST(TreeNode* root, int target) {    if (!root || root->val == target) return root;    if (target < root->val)        return searchBST(root->left, target);    return searchBST(root->right, target);}int main() {    TreeNode* root = nullptr;    // 构建BST: 5, 3, 7, 2, 4    root = insert(root, 5);    root = insert(root, 3);    root = insert(root, 7);    root = insert(root, 2);    root = insert(root, 4);    int target = 3;    TreeNode* result = searchBST(root, target);        if (result) {        cout << "找到了！值为: " << result->val << endl;    } else {        cout << "未找到值: " << target << endl;    }    return 0;}  

总结

通过本教程，你已经学会了如何在C++中实现二叉搜索树（BST）的查找操作。无论是递归还是迭代方式，核心思想都是利用BST的有序特性进行高效查找。掌握这一基础操作，是深入学习高级数据结构如AVL树、红黑树的重要一步。

希望这篇关于C++ BST查找的教程对你有帮助！如果你正在学习C++数据结构教程，不妨动手实践一下上面的代码，加深理解。