非递归插入更值得优先考虑，因其避免栈溢出、内存稳定O(1)，且便于调试与扩展；需显式维护parent指针以正确挂载新节点，并明确空树和重复值处理策略。
为什么非递归插入比递归更值得优先考虑
递归插入写起来简洁，但实际项目里容易栈溢出——尤其树退化成链表时，深度可能达到十万级。非递归版本用显式 while 循环 + 指针遍历，内存开销稳定在 O(1)，且更容易嵌入带调试钩子或日志的工业级代码中。
核心逻辑：用 parent 指针定位插入位置
递归靠函数调用栈隐式记住父节点，非递归必须显式维护 parent。关键不是“找到空位”，而是“找到该空位的父节点”——因为只有父节点才能修改它的 left 或 right 指针。
常见错误是只用 current 遍历到底，结果发现 current 是 nullptr，没法赋值。正确做法：
- 初始化
current = root，parent = nullptr -
while (current != nullptr)内更新parent = current，再按值大小决定走向左/右子树 - 循环结束后，
parent必然非空（除非原树为空），此时根据新节点值决定挂到parent->left还是parent->right
示例片段：
立即学习“C++免费学习笔记（深入）”；
Node* insert(Node* root, int val) {
Node* newNode = new Node(val);
if (!root) return newNode;
<pre class='brush:php;toolbar:false;'>Node* current = root;
Node* parent = nullptr;
while (current != nullptr) {
parent = current;
if (val < current->val) {
current = current->left;
} else {
current = current->right;
}
}
if (val < parent->val) {
parent->left = newNode;
} else {
parent->right = newNode;
}
return root;}
边界情况：空树和重复值怎么处理
空树最简单：直接返回新节点，不用进循环。但要注意函数签名是否允许修改 root ——如果传的是 Node*& root 引用，空树时直接赋值即可；若传值，则必须返回新根并由调用方更新。
重复值是 BST 定义分歧点。标准定义不允许重复，遇到相等应忽略；但有些业务要求存计数或链表。实操建议：
- 明确接口契约：文档或注释写清“重复值被丢弃”或“重复值触发计数器+1”
- 比较时用
val val还是val val直接影响重复值走向——前者会挤到左子树，后者挤到右子树，都不符合 BST 语义，除非你主动支持重复 - 如果需支持重复，推荐在节点内加
int count字段，相等时只++count，不新建节点
性能与可维护性提醒
非递归插入看似只是把栈换成了指针，但实际影响深远：
- 调试时能单步看到每一步的
parent和current状态，递归则要反复进进出出栈帧 - 后续扩展（如插入时记录路径、触发旋转、写 WAL 日志）都依赖对遍历过程的完全控制，递归会增加封装成本
- 注意指针赋值顺序：必须先判断
parent是否为空（空树已提前处理，这里安全），再比较val和parent->val，否则可能解引用空指针
真正难的不是写出来，是想清楚 parent 在哪、什么时候更新、以及相等时到底想干什么——这三件事没定准，代码跑得再快也没用。
