Java中BST非递归插入与查找均用while循环实现：插入需跟踪parent以挂载新节点，查找只需沿BST性质移动；二者均须前置判空，比较用compareTo避免包装类错误。
在 java 中，用 while 循环实现二叉搜索树（bst）的非递归插入和查找，核心是模拟递归调用栈的行为——通过显式维护当前节点引用并持续向下移动，直到到达空位置或目标值。
非递归插入：逐层定位插入点
插入的关键是找到父节点和正确的子方向（左/右），且需处理树为空的边界情况。不依赖递归，全程用 while 向下遍历：
- 若根为
null，直接新建节点作为根 - 否则初始化
current指向根，用parent记录上一个节点 - 循环中比较
current.data与待插入值：
– 若小于，向左走（current = current.left），同时更新parent
– 若大于，向右走（current = current.right）
– 若相等，通常忽略重复（BST 一般不允许重复键） - 退出循环时
current == null，此时将新节点挂到parent的对应子侧
非递归查找：快速定位目标节点
查找更简单，只需沿 BST 性质一路比较、移动，无需记录父节点：
- 从根开始，
current = root - 进入
while (current != null)循环 - 每次比较：
– 相等 → 返回该节点（或true/ 数据）
– 小于 →current = current.left
– 大于 →current = current.right - 循环结束仍未找到 → 返回
null（或false）
关键细节与常见陷阱
实际编码中容易忽略几个要点：
-
空树判断必须前置：插入和查找都要先检查
root == null，避免空指针 -
插入时 parent 初始值要设对：不能默认为
root，而应在进入循环前设为null，并在第一次移动时才赋值 -
比较逻辑要统一：使用
Integer.compare()或compareTo()支持null安全和自定义类型，避免==或原始对包装类出错 - 不要在循环内新建节点：插入动作只发生在循环外，确保只插一次
简洁可运行示例片段
以下为插入与查找的核心逻辑（假设节点类 TreeNode<t extends comparable>></t>）：
立即学习“Java免费学习笔记（深入）”；
public TreeNode<T> insert(T data) {
TreeNode<T> newNode = new TreeNode<>(data);
if (root == null) {
root = newNode;
return root;
}
TreeNode<T> current = root, parent = null;
while (current != null) {
parent = current;
int cmp = data.compareTo(current.data);
if (cmp < 0) current = current.left;
else if (cmp > 0) current = current.right;
else return current; // 已存在，不插入
}
if (data.compareTo(parent.data) < 0) parent.left = newNode;
else parent.right = newNode;
return newNode;
}
public TreeNode<T> search(T data) {
TreeNode<T> current = root;
while (current != null) {
int cmp = data.compareTo(current.data);
if (cmp == 0) return current;
else if (cmp < 0) current = current.left;
else current = current.right;
}
return null;
}
