在 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 中添加元素，新添加的元素都是添加到叶子节点上去的；
