非递归查找用while循环沿BST性质单向下降，比较后只更新current为left或right；中序遍历则需stack模拟递归栈，先左链压栈、再弹栈访问、最后转向right，二者控制流本质不同。
非递归查找：用 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 < current->val) ? current->left : current->right;
}
return nullptr;
}非递归中序遍历：用 stack 显式维护调用栈
中序遍历「左→根→右」的非递归实现，核心是模拟递归时系统栈的行为：先一路压入左子节点，到底后弹出并访问，再转向右子树。最容易错的是对右子树的处理时机——不能在弹出后立刻压入其右子节点，而应把右子节点作为下一轮「新起点」继续走左链。
性能上，空间复杂度仍是 O(h)（h 为树高），和递归一致；但避免了函数调用开销，对极深树更安全。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 用
std::stack<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 << current->val << " ";
current = current->right;
}
}为什么不能直接复用查找的 while 结构做中序遍历
查找是单路径决策，中序是「回溯+分支切换」过程。有人试图用一个指针加几个标志位硬套查找结构，结果逻辑缠绕、边界难控——比如在访问完某节点后，无法自然知道该回退到父节点还是跳去右子树。
根本区别在于控制流模型：searchIterative 是纯线性状态机，而中序需要显式保存「已走过但未访问」的祖先节点，stack 是最直白且不易出错的载体。
- 强行不用栈，可用线索化（threaded BST），但需改造节点结构，不通用
- 用
vector模拟栈可行，但语义不如stack清晰，且无必要 - 某些面试题要求「O(1) 额外空间」，那必须用 Morris 遍历——但它会临时修改树结构，用完要恢复，属于特例而非通解
实际使用时容易忽略的细节
写完代码别急着提交，这几个点常被跳过：
-
Node结构体里指针成员是否初始化为nullptr？构造函数里漏写会导致野指针 - 遍历函数传参用
Node*还是const Node*？如果只是读取，加上const更安全 - 查找函数返回
Node*，但调用方可能直接解引用而不检查是否为空，建议配合断言或文档注明 - 测试时至少覆盖三种 case：空树、查不到的值、查叶子节点——尤其后者容易因循环终止条件写错而崩溃
中序遍历输出顺序是否真有序，光看样例不够；拿插入序列反推期望输出，再比对实际打印结果，才是靠谱验证方式。
