如何用二叉搜索树(BST)实现前缀匹配？booksPrefix方法无输出如何解决

• 死循环问题：私有方法booksPrefix中错误使用while (root != null)，循环内未修改root的取值，只要进入循环就会永远卡在当前节点，无法执行后续递归逻辑也无法正常返回，是导致无输出的核心原因之一
• 参数匹配问题：调用处传入的是带*的完整搜索词（如Cor*），没有提前提取*之前的前缀字符串，导致前缀匹配逻辑拿带*的字符串去匹配书名，不可能命中结果
• 方法封装缺失：对外调用的booksPrefix(search)是单参数方法，但你定义的核心逻辑是双参数私有方法，缺少了将BST根节点传入、同时预处理搜索前缀的封装层

首先补充对外暴露的单参数入口方法，完成参数预处理和根节点传递：

// 对外暴露的前缀搜索入口
public void booksPrefix(String search) {
    // 提取*之前的有效前缀
    String prefix = search.split("\\*")[0];
    // 传入BST根节点启动递归搜索
    booksPrefix(root, prefix);
}

修复后的递归搜索逻辑：

private void booksPrefix(Node root, String prefix) {
    // 递归终止条件：节点为空直接返回，替换原有错误的while循环
    if (root == null) {
        return;
    }
    String rootLow = root.key.toLowerCase();
    String prefixLow = prefix.toLowerCase();
    // 先遍历左子树（保证输出结果按字典序排列，可选）
    booksPrefix(root.left, prefix);
    // 当前节点匹配前缀则打印
    if (rootLow.startsWith(prefixLow)) {
        System.out.println(root.data);
    }
    // 遍历右子树
    booksPrefix(root.right, prefix);
}

基于二叉搜索树的有序特性，可以增加剪枝逻辑减少不必要的遍历：

若当前节点key转小写后比前缀小，左子树所有节点值都小于当前节点，不可能匹配前缀，可跳过左子树遍历；若当前节点key转小写后比前缀大，且当前节点key不包含前缀作为前缀，右子树所有节点值都大于当前节点，不可能匹配前缀，可跳过右子树遍历。

内容的提问来源于stack exchange，提问作者lamp-enthusiast