java - 如何在二叉搜索树中查找节点

Question

我正在阅读有关 java 中的二叉树的内容。我找到了这段代码:

public BSTNode findNode(Comparable val){
        int delta = val.compareTo(value);
        // the value is less than this.value
        if(delta < 0){
            // if there is a leftChild, return left.findNode(val)
            // there is no leftChild, so the val does not exist
            // in the node, so return null
            return (left!= null)? left.findNode(val): null;
        }
        // else if the value is greater than this.value
        else if (delta > 0){
            // if there is a rightChild, then return right.findNode(val)
            // else, there is no rightChild, return null
            return (right != null)? right.findNode(val): null;
        }
        // else, dela == 0, so we have found the node with that
        // val, return the node
        return this;
    }

我不明白这是如何工作的:

return (left!= null)? left.findNode(val): null;
return (right != null)? right.findNode(val): null;

你能用另一种方式重写它吗？

谢谢

Answer 1

好的，我们一步步来。首先，我将重点关注算法本身。

class Node<T> {
    T value;
    Node left;
    Node right;
}

保证左边的所有值都小于或等于value，并且右边的所有值都大于或等于值。这使得搜索更加容易。如果您要查找元素val，只需将其与当前Node 中的value 进行比较即可。如果所需元素与当前元素相同，则您已找到它。如果它更大，它只能位于树的右侧部分。否则在左侧。

该元素可能不在这里。如果您发现它应该位于当前节点的左侧/右侧，但那里什么也没有 (null)，就会发生这种情况。

所以 BinaryTreeSearch 是:

T search(Node tree, T val) {
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        return search(tree.getRight(), val);
    } else {
        return search(tree.getLeft(), val);
    }
}

但是等等...如果该项目不在这里，这会导致 NPE。我们来修改一下:

T search(Node tree, T val) {
    if (tree == null)
         return null;
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        return search(tree.getRight(), val);
    } else {
        return search(tree.getLeft(), val);
    }
}

这也可以这样重写:

T search(Node tree, T val) {
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        if (tree.getRight() == null) 
            return null;
        return search(tree.getRight(), val);
    } else {
        if (tree.getLeft() == null)
            return null;
        return search(tree.getLeft(), val);
    }
}

但是这里出现了三元运算符，它被缩短和简化了if-else。

result = testCondition ? value1 : value2

与

相同

if (testCondition) {
    result = value1;
} else {
    result = value2;
}

Another conditional operator is ?:, which can be thought of as shorthand for an if-then-else statement (discussed in the Control Flow Statements section of this lesson). This operator is also known as the ternary operator because it uses three operands. In the following example, this operator should be read as: "If someCondition is true, assign the value of value1 to result. Otherwise, assign the value of value2 to result."

所以我们最终收到:

T search(Node tree, T val) {
    int delta = tree.getValue.compareTo(val);
    if (delta == 0) {
        return tree.getValue;
    } else if (delta > 0) {
        return (tree.getRight() == null) ? null : search(tree.getRight(), val);
    } else {
        return (tree.getLeft() == null) ? null : search(tree.getLeft(), val);
    }
}