当不满足任何条件时，二进制搜索树中的contains方法如何返回false

Question

我有一个类的方法，该方法使用二进制搜索树数据结构实现整数集。其中一个方法是contains方法，如果集合包含给定的整数，则返回true

下面两种方法的实现都是正确的，但我正在努力理解为什么要这样做：

def contains(x: Int): Boolean =
if (x < elem) left.contains(x)
else if (elem < x) right.contains(x)
else true

与详尽无遗并以这种方式进行相比就足够了：

def contains(x: Int): Boolean =
if (x < elem) left.contains(x)
else if (elem < x) right.contains(x)
else if (elem == x) true
else false

如果整数不属于集合，那么第一种方法中的方法返回false的直观原因是什么？

Answer 1

您的怀疑是正确的，因为结束递归的唯一方法似乎是返回true。

但是，我想您会发现，对于节点元素和叶元素，树有不同的类。您所展示的是节点的contains方法。叶的contains方法将只返回false，从而结束递归。

或者，也可以是left，right是Option[Node]。在这种情况下，如果Option是None，则会得到false，因为None.contains(_)始终是false。

Answer 2

二进制搜索树总是这样构造的，即左分支的元素小于节点值elem，右分支的元素都大于elem。

按照这个逻辑，如果你的x既不小于，也不大于elem，你只有一种可能性：它等于elem。因此，不需要测试相等性，第二个实现的：else false将始终是一个死分支。

这样想：如果你取两个数字，它们都不比另一个小或大，那么它们一定是同一个数字。