C++如何实现二叉搜索树的非递归查找算法-C++-PHP中文网

非递归查找bst的核心逻辑是利用bst性质，通过循环迭代更新当前节点指针，根据目标值与当前节点值的大小关系决定向左或右子树移动，直至找到目标或到达空节点；需在入口检查root是否为空，时间复杂度o(h)，空间复杂度o(1)。

c++如何实现二叉搜索树的非递归查找算法

非递归查找的核心逻辑是什么

二叉搜索树（BST）的查找依赖于左子树值

查找从 root 开始，只要 current != nullptr 就继续循环
若 current->val == target，直接返回该节点指针
若 target val，更新 current = current->left
否则（target > current->val），更新 current = current->right
循环结束仍未找到，返回 nullptr

这比递归少了一次函数调用开销，也避免了深度过大时的栈溢出风险，尤其适合嵌入式或深度不可控的场景。

代码里最容易漏掉的空指针检查

很多人写完循环体就以为结束了，但忘了入口处对 root 的判空——如果传入空树，不检查就直接进循环会崩溃。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

TreeNode* searchBST(TreeNode* root, int target) {
    TreeNode* current = root;
    while (current != nullptr) {
        if (current->val == target) {
            return current;
        } else if (target val) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    return nullptr;
}

注意：这里只用了 current != nullptr 作为循环条件，没在循环体内重复判空，因为每次赋值 current->left 或 current->right 后，下一轮循环开头自然会拦截 nullptr。这是简洁且安全的写法。