如何修改二叉搜索树插入节点方法使其在元素不存在时返回true

你原代码的核心问题是返回值仅携带节点信息，没有插入状态标识，且空节点新建后存在冗余的比较逻辑，调整逻辑如下：

核心判断规则 #

• 遇到空节点新建节点时，说明原树无对应元素，返回插入成功（true）
• 比较结果为0时，说明元素已存在，直接返回插入失败（false）
• 递归子树时直接透传下层的插入状态即可

具体改法 #

方案1：用数组包装节点处理引用传递（Java场景通用） #

Java为值传递，无法直接修改方法外的节点引用，用长度为1的数组包装节点即可解决：

private boolean insertNode(Node[] rootArr, Student student) {
    Node root = rootArr[0];
    if (root == null) {
        rootArr[0] = new Node(student);
        return true;
    }
    int comp;
    if (Comparator != null) {
        comp = Comparator.compare(student, root.value);
    } else {
        comp = student.compareTo(root.value);
    }

    if (comp < 0) {
        Node[] leftArr = {root.left};
        boolean insertRes = insertNode(leftArr, student);
        root.left = leftArr[0];
        return insertRes;
    } else if (comp > 0) {
        Node[] rightArr = {root.right};
        boolean insertRes = insertNode(rightArr, student);
        root.right = rightArr[0];
        return insertRes;
    } else {
        // 元素已存在，插入失败
        return false;
    }
}

调用示例：

Node root = 你的根节点;
Node[] rootWrapper = {root};
boolean isInsertSuccess = insertNode(rootWrapper, student);
root = rootWrapper[0];

方案2：自定义结果类同时携带节点和插入状态 #

不想修改调用入参结构的话可以用这个方案：

// 先定义辅助结果类，也可以直接用Java自带的AbstractMap.SimpleEntry
private static class InsertResult {
    Node root;
    boolean inserted;
    InsertResult(Node root, boolean inserted) {
        this.root = root;
        this.inserted = inserted;
    }
}

private InsertResult insertNode(Node root, Student student) {
    if (root == null) {
        return new InsertResult(new Node(student), true);
    }
    int comp;
    if (Comparator != null) {
        comp = Comparator.compare(student, root.value);
    } else {
        comp = student.compareTo(root.value);
    }

    if (comp < 0) {
        InsertResult leftRes = insertNode(root.left, student);
        root.left = leftRes.root;
        return new InsertResult(root, leftRes.inserted);
    } else if (comp > 0) {
        InsertResult rightRes = insertNode(root.right, student);
        root.right = rightRes.root;
        return new InsertResult(root, rightRes.inserted);
    } else {
        return new InsertResult(root, false);
    }
}

调用示例：

InsertResult res = insertNode(root, student);
root = res.root;
boolean isInsertSuccess = res.inserted;

原代码冗余点提醒 #

你原有代码中空节点新建后没有直接返回，会继续执行后续的比较逻辑，虽然不影响运行结果，但属于无效计算，调整时可以一并优化。

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