C++如何实现二叉搜索树的非递归查找与有序中序遍历-C++-PHP中文网

非递归查找用while循环沿bst性质单向下降，比较后只更新current为left或right；中序遍历则需stack模拟递归栈，先左链压栈、再弹栈访问、最后转向right，二者控制流本质不同。

c++如何实现二叉搜索树的非递归查找与有序中序遍历

非递归查找：用 while 循环模拟递归路径

二叉搜索树（BST）的查找本质是沿 left 或 right 单向下降，完全不需要递归栈。关键在于每次比较后只保留一个子节点方向，用 while 持续推进即可。

常见错误是提前返回或漏判空指针——比如在进入循环前没检查 root == nullptr，或循环体内未更新当前节点导致死循环。

起始节点设为 root，循环条件是 current != nullptr
若 current->val == target，直接返回该节点指针
若 target val，转向 current = current->left
否则转向 current = current->right
循环结束仍未找到，返回 nullptr

Node* searchIterative(Node* root, int target) {
    Node* current = root;
    while (current != nullptr) {
        if (target == current->val) return current;
        current = (target val) ? current->left : current->right;
    }
    return nullptr;
}

非递归中序遍历：用 stack 显式维护调用栈

中序遍历「左→根→右」的非递归实现，核心是模拟递归时系统栈的行为：先一路压入左子节点，到底后弹出并访问，再转向右子树。最容易错的是对右子树的处理时机——不能在弹出后立刻压入其右子节点，而应把右子节点作为下一轮「新起点」继续走左链。

性能上，空间复杂度仍是 O(h)（h 为树高），和递归一致；但避免了函数调用开销，对极深树更安全。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

用 std::stack<node></node> 存待访问节点
外层 while 控制整体流程：栈非空或当前节点非空
内层 while 负责「沿左链压栈」，直到 current == nullptr
弹出栈顶，访问其值，然后令 current = popped->right

void inorderIterative(Node* root) {
    std::stack<node> stk;
    Node* current = root;
    while (!stk.empty() || current != nullptr) {
        while (current != nullptr) {
            stk.push(current);
            current = current->left;
        }
        current = stk.top();
        stk.pop();
        std::cout val right;
    }
}</node>