JAVA BST return BST节点的节点实例？

Question

我正在做一个 BST 项目，它在 BST 中搜索一个值，如果找到，return。我用了一个测试方法来检查代码，它工作正常。问题出在我猜的 return 类型上。

public BSTNode contains(BSTNode root, String needle) {
     BSTNode current = root;
     while (current != null) {
         if (current.getData().compareTo(needle) > 0)
            current=current.getLeft();
        else if (current.getData().compareTo(needle) < 0)
            current=current.getRight();
        else if (current.getData().compareTo(needle) == 0)
            return current;
        else current=null;
    }
    return current;
}

结果：

BSTNode node = bst.contains(root, "delta");
    Assertions.assertTrue(node instanceof BSTNode);

错误；

BSTNode node = bst.contains(root, "delta");
    Assertions.assertTrue(true);

正确；

根据我的理解，我相信代码可以正常工作并且值 return 是正确的。我只是不明白“BSTNode 的节点实例”为什么它是错误的，我该如何解决它？

先谢谢你

Answer 1

你写的方法只能return null。只有在 current 为 null 时才退出 while 循环，然后 return current。 null instanceof Anything 始终为假。

行current=current;如果找到值也会导致无限循环。

这两个问题都可以同时解决：当比较为 0 时，您应该 return current。

Answer 2

由于您已经知道您实际上错了，我将通过修改您现有的代码来添加一个约束。

如果是BST，会有3分：

当前节点等于关键节点
当前节点大于关键节点
当前节点小于关键节点

因此您需要迭代，直到找到您正在寻找的键或您遍历了所有可能的键。无论哪种情况，您都需要停止迭代。

   public BSTNode contains(BSTNode root, String needle) {
     BSTNode current = root;
    /* the variable you will return at the end */

     BSTNode result = null;
    /* iterate the loop until current becomes null or result becomes not null */

     while (current != null && result == null) {
         /* when you found what you were looking for */
         if (current.getData().compareTo(needle) == 0){
            result = current;
         }else if (current.getData().compareTo(needle) > 0){
            current=current.getLeft();
         }else{
            current=current.getRight();
         }
    }       
    /* return the result at the end, it will be either null or the value you were looking */
    return result;

   }

JAVA BST return BST节点的节点实例？

JAVA BST return node instance of BST node?

java

binary-search-tree