Java二叉搜索树(BST)递归插入出现StackOverflowError求助

你遇到的栈溢出问题主要来自两个核心错误：BSTNode构造函数的错误初始化和递归插入方法的逻辑偏差，咱们一步步拆解并修复：

错误原因分析 #

1. BSTNode构造函数的不合理初始化 #

在带参数的BSTNode构造函数中，你把left、right、parent都初始化为new BSTNode()而非null：

public BSTNode(int key, String val) {
    this.key = key;
    this.val = val;
    this.left = new BSTNode(); // 错误：应该设为null
    this.right = new BSTNode(); // 错误：应该设为null
    this.parent = new BSTNode(); // 错误：应该设为null
}

这就导致树中不存在真正的“空节点”，递归插入时会一直遍历这些空的BSTNode对象，永远触不到终止条件，最终引发栈溢出。

2. insertRec方法的逻辑错误 #

你的递归插入方法完全误用了root成员变量，没有基于当前遍历的节点进行递归：

• 方法仅接收要插入的节点，没有传入当前遍历的节点，导致每次递归都在和全局的root比较，而非向下遍历子树；
• 第二个条件判断没有用else if，逻辑上不严谨；
• 给右子树赋值后，错误地设置了左子树的parent（明显笔误）。

修正后的完整代码 #

public class BSTNode {
    public int key;
    public String val;
    public BSTNode left, right, parent;

    // 带参数的构造函数：初始化左右孩子和父节点为null
    public BSTNode(int key, String val) {
        this.key = key;
        this.val = val;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    // 空构造函数保留（如果需要的话）
    public BSTNode() {}
}

public class BST {
    private BSTNode root;

    public BST() {
        this.root = null;
    }

    // 对外暴露的插入方法
    public void insert(int key, String val) {
        root = insertRec(root, new BSTNode(key, val));
    }

    // 递归插入的核心方法：接收当前节点和要插入的节点
    private BSTNode insertRec(BSTNode currentNode, BSTNode newNode) {
        // 终止条件：当前节点为空，直接返回新节点作为该位置的节点
        if (currentNode == null) {
            return newNode;
        }

        // 递归插入左子树
        if (newNode.key < currentNode.key) {
            BSTNode leftChild = insertRec(currentNode.left, newNode);
            currentNode.left = leftChild;
            leftChild.parent = currentNode;
        }
        // 递归插入右子树（用else if避免逻辑冲突）
        else if (newNode.key > currentNode.key) {
            BSTNode rightChild = insertRec(currentNode.right, newNode);
            currentNode.right = rightChild;
            rightChild.parent = currentNode;
        }
        // 如果key相等，这里可以处理重复键的逻辑，比如覆盖或者忽略
        else {
            // 可选：比如抛出异常，或者更新值
            // throw new IllegalArgumentException("Key already exists: " + newNode.key);
            currentNode.val = newNode.val;
        }

        return currentNode;
    }

    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(2, "Val_0");
        bst.insert(1, "Val_1");
        bst.insert(3, "Val_2"); // 测试插入更大的键
        System.out.println("插入完成，无栈溢出");
    }
}

关键修正点说明 #

1. BSTNode构造函数：将left、right、parent初始化为null，这样递归时能正确识别空节点，触发终止条件。
2. insertRec方法：
   • 新增currentNode参数，代表当前遍历到的节点，递归时基于该节点向下遍历左/右子树；
   • 终止条件改为currentNode == null，此时直接返回新节点，完成插入；
   • 修正了parent赋值的笔误，确保左/右子节点的父节点指向正确的当前节点；
   • 增加了重复键的处理逻辑（可选），避免插入重复键时出现异常。

现在你测试插入未排序的键（比如2、1、3），就不会再出现栈溢出问题了。

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