在 BST 中查询某个元素 - boolean contains(E e)

• BST 中暴露出来的接口不是个递归的方法，但是可以把问题转换成递归的方式解决；
• 转化成的递归的方法是：在以 node 为根的 BST 中查找某个元素；
• 规模更小的同一个问题是：在 node 的左子树或右子树中查询元素 e 是否存在；
• 不能再缩小的基本问题是：对 node 节点及 node 节点和 e 关系的处理；
  • 如果 node == null，则以 node 为根的 BST 中不存在 e；
  • 如果 node.e 和 e 是相等的，则以 node 为根的 BST 中存在 e；

// 看二分搜索树中是否包含元素e
public boolean contains(E e){
    return contains(root, e);
}

// 看以node为根的二分搜索树中是否包含元素e, 递归算法
private boolean contains(Node node, E e){
    if(node == null)
        return false;

    if(e.compareTo(node.e) == 0) {
        return true;
    } else if (e.compareTo(node.e) < 0) {
        return contains(node.left, e);
    }  else { // e.compareTo(node.e) > 0
        return contains(node.right, e);
    }
}

特别说明

• 在二叉树中查找的时候，如果要往下一层走，要么走左边，要么走右边，被排除的方向在这次查找中，再也不会被访问到，也就是说，查找的路径是唯一的，这也是 BST 快的原因，排出了很多错误答案；
• 在 BST 中查找，不是非要找到叶子节点的，往下找的某一个节点就找到了，就不必接着往下找了，这一点和在 BST 中添加元素是不一样的，在 BST 中添加元素，新添加的元素都是添加到叶子节点上去的；