Java中二叉搜索树(BST)插入方法的问题排查与修复求助

你的BST插入方法的核心问题是插入根节点后没有终止方法执行，导致后续代码继续运行，错误地给根节点的右子节点也绑定同一个新节点，这就是你看到部分值同时出现在左右两侧的原因。

具体问题点 #

当树为空时，你设置了root = newNode，但没有添加return语句跳出方法。这会导致代码继续执行到current = root，然后进入while(true)循环：

• parent被赋值为刚创建的根节点
• 因为current.data等于number，会进入else分支
• current被赋值为current.right（此时为null）
• 执行parent.right = newNode，让根节点的右子节点指向自身
  这就给后续的插入操作埋下了隐患，导致节点关系混乱。

修复后的代码 #

public void insert(int number) {
    Node newNode = new Node(number);
    if (isEmpty()) {
        root = newNode;
        return; // 添加这行，终止方法，避免后续代码执行
    }
    Node current = root;
    Node parent;
    while (true) {
        parent = current;
        if (current.data > number) {
            current = current.left;
            if (current == null){
                parent.left = newNode;
                return;
            }
        } else {
            current = current.right;
            if(current == null){
                parent.right = newNode;
                return;
            }
        }
    }
}

额外说明 #

另外，BST通常需要处理重复值的情况（比如插入和当前节点相同的数值），如果你的需求是不允许重复，可以在else分支前添加一个判断：

if (current.data == number) {
    // 可以选择抛出异常、直接return或者做其他处理
    return;
}

这样能避免重复节点被插入到树中。

内容的提问来源于stack exchange，提问作者Ezana