java - 在二叉搜索树中搜索节点时如何处理空检查

Question

我有以下代码来搜索 BST 中的节点:

private Node<AnyType> searchAndGetNode(AnyType value) {
        Node<AnyType> currentNode = root; 
        while(currentNode != null && currentNode.getData() != null) {
            if (value.compareTo(currentNode.getData()) == 0) {
                return currentNode;
            } else if (value.compareTo(currentNode.getData()) < 0) {
                currentNode = currentNode.getLeft();
            } else {
                currentNode = currentNode.getRight();
            }
        }
        return null;
    }

我知道 Optional.ofNullable() 可以获取 Optional 对象，然后使用 isPresent() 来避免 null 检查。但是我想不出任何巧妙的方法来避免在上述方法的 while 循环中进行空检查比较。我正在使用 Java 8。请提出建议。

Answer 1

您应该删除条件的 && currentNode.getData() != null 部分，因为在二叉树中存在空值是没有意义的(您不能调用 compareTo 为 null，那么你会把它插入到树的什么地方？)。除此之外，您的空检查没有任何问题。

但是，为了性能，您不应该为每个值调用两次 compareTo，而是调用一次并检查结果:

int cmp = value.compareTo(currentNode.getData());
if (cmp == 0) {
    return currentNode;
} else if (cmp < 0) {
    currentNode = currentNode.getLeft();
} else { // cmp > 0
    currentNode = currentNode.getRight();
}