第 4 节 二分搜索树的第 2 个操作：元素查找和判断是否包含

• 这一节，我们要实现查找的两个方法：二分查找树的包含 contain（返回 true 或者 false） 和查找 search（返回相应的 vlaue 值），这两个方法同质。还要考虑查找成功和失败这两种情况。
• 1、首先实现 contain 方法。

public boolean contain(int key) {
    return contain(root, key);
}

private boolean contain(Node node, int key) {
    // 先处理递归到底的情况
    if (node == null) {
        return false;
    }
    if (node.key == key) {
        return true;
    } else if (key < node.key) {
        return contain(node.left, key);
    } else {
        return contain(node.right, key);
    }
}

• 2、再实现 search 方法。

public int search(int key) {
    return search(root, key);
}

// 在以 node 为根的二分搜索树中查找 key 所对应的 value
private Integer search(Node node, int key) {
    // 先处理递归到底的情况
    if (node == null) {
        return null;
    }
    if (node.key == key) {
        return node.value;
    } else if (key < node.key) {
        return search(node.left, key);
    } else {
        return search(node.right, key);
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/search-and-contains 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。