时间戳

首页 > 解决方案 > 方法进入第二次返回，导致错误输出

java - 方法进入第二次返回，导致错误输出

问题描述

我正在尝试使用 Java 在二叉树中查找特定节点。我查找节点的方法返回包含所搜索数据的节点。

我的代码如下所示：

    public BinNode find(Comparable item) throws NullPointerException {
        if (item == null) {
            throw new NullPointerException("item is NULL");
        } else if (root == null) {
            throw new NullPointerException("tree is empty");
        }
        return find(root, item);
    }

    public static boolean found = false;
    public BinNode find(BinNode k, Comparable item) throws NullPointerException {
        if (k.getData().equals(item)) {
            found = true;
            return k;
        }
        if (!found && k.getChildLeft() != null) {
            find(k.getChildLeft(), item);
        }
        if (!found && k.getChildRight() != null) {
            find(k.getChildRight(), item);
        }
        return k;
    }

运行调试器我可以看到，当我搜索树中存在的项目时，它将找到正确的节点并在“found”设置为 true 后转到第一个返回语句。但是，编译器不会将该节点返回给方法调用，而是继续执行第二个返回语句，返回根。所以无论 Node 位于何处，该方法将始终返回根。

我究竟做错了什么？

标签： javabinary-treebinary-search-treenodestree-traversal

解决方案

您的方法永远不会返回“未找到”，这从根本上是错误的，因为大多数时候项目不在数据中。这是你的主要问题。您需要在底部语句中返回null/ 一个空。然后你需要在向下遍历树时正确处理“未找到”的返回值，即在你调用左右孩子的地方。Optionalreturnfind

您的逻辑必须始终是：

  • 使当前节点具有正确的值
    • 如果是，则返回当前节点
  • 左节点是否包含值
    • 如果是，则从左侧返回相应的节点
  • 右节点是否包含值
    • 如果是，则从右侧返回相应的节点
  • 返回“未找到”（因为当前节点不正确，左右都不包含值）

您当前跳过/尚未实现两个嵌套的“如果是，则从左/右返回相应的节点”代码路径。

（当然删除found评论中提到的变量）

public BinNode find(BinNode k, Comparable item) throws NullPointerException {
    if (k.getData().equals(item)) {
        return k;
    }
    if (k.getChildLeft() != null) {
        BinNode node = find(k.getChildLeft(), item);
        if (node != null) return node;
    }
    if (k.getChildRight() != null) {
        BinNode node = find(k.getChildRight(), item);
        if (node != null) return node;
    }
    return null;
}

推荐阅读