二叉搜索树（BinarySearchTree）搜索方法返回错误结果求助

我一眼就看出你遇到的异常问题出在哪了——你的递归插入和搜索方法全程都在操作全局的head节点，而不是递归调用时传入的当前节点node！这直接导致你的二叉搜索树（BST）结构完全不符合预期，搜索逻辑自然会混乱，出现匹配相邻值的错误。

具体问题分析 #

1. recursiveInsert方法的致命错误 #

你写的插入递归逻辑完全搞错了处理对象：

• 方法参数里的node本来是当前递归层级要处理的节点，但你全程用this.head来判断、比较和赋值，这意味着所有插入操作都在根节点上打转，根本没有正确构建出左、右子树的层级结构。
• 举个例子：当你插入39之后再插40，代码会错误地把40放到根节点的左子树（因为你一直在比较根节点的key和新key），而不是根节点的右子树，最终树的结构完全混乱。

2. recursiveSearch方法的逻辑错误 #

搜索方法犯了同样的错误：

• 你始终在判断全局head的状态，而不是传入的当前node。这导致搜索时根本没有遍历树的层级，要么直接返回根节点，要么错误地递归根节点的子树，而因为树结构本身就错了，自然会返回相邻的节点值。

修复后的代码 #

修复recursiveInsert方法 #

public Node recursiveInsert(Node node, int key, String string) {
    // 处理当前节点为null的情况，创建新节点返回
    if (node == null) {
        return new SearchTree.Node(key, string);
    }
    // 基于当前节点的key判断插入方向
    if (key < node.key) {
        node.left = recursiveInsert(node.left, key, string);
    } else if (key > node.key) { // 区分大于和等于，避免重复插入相同key的节点
        node.right = recursiveInsert(node.right, key, string);
    }
    // 返回当前节点，维护树的层级结构
    return node;
}

insert方法可以保持不变，它已经正确将递归返回的节点赋值给了head。

修复recursiveSearch方法 #

public Node recursiveSearch(SearchTree.Node node, int key) {
    // 当前节点为null，说明未找到目标key
    if (node == null) {
        return null;
    }
    // 找到目标key，返回当前节点
    if (node.key == key) {
        return node;
    }
    // 根据key大小递归搜索左/右子树
    if (key < node.key) {
        return recursiveSearch(node.left, key);
    } else {
        return recursiveSearch(node.right, key);
    }
}

修复后的效果 #

修复后，插入操作会正确构建符合BST规则的树结构：每个节点的左子树所有节点key都小于当前节点，右子树所有节点key都大于当前节点。搜索时会沿着正确的路径遍历，精准匹配目标key，不会再返回相邻节点的值。

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