已检查关键字的顺序

Question

假设某个二叉搜索树的键为1之间的整数和20，然后我们搜索10。下面的序列不能是序列检查的钥匙？

（a）20、5、15、8、12、9、10

（b）1，12，10，16，14，15

（c）5、13、7、10、8

我不太明白这个问题，我了解的是哪个序列不具有10，但是由于每个序列都包含10，这不意味着可以检查每个序列吗？

Answer 1

如评论中所述，（b）和（c）是否以10为目标没有意义，所以我们将问题更改为仅说“搜索给定数字”。

当深入二进制搜索树时，我们绝不应该遇到超出我们之前比较范围的键。

例如，考虑：

（（我们还可以想象树向下走了很多，例如，节点可以容纳浮点数，而不仅仅是整数）。

假设我们正在寻找7.5，因此已向下钻取到7（并且还有7以下的其他节点，例如7.1、7.3等...。）。

对于其余的搜索，我们永远都不会遇到：

a）任何小于6的密钥（因为我们在6处进行了正确分支）

NOR

b）任何大于8的键（因为我们在8处取得了左分支）

现在考虑我们访问过的键的顺序：8-> 3-> 6-> 7

[请注意，如何从该序列中导出边界（“小于6”，“大于8”）（例如，从8降到3，所以这意味着随后遇到键“大于8”不可能）。

由于这是一项作业，所以我不会直接给出答案，但是我希望这是足够的详细信息，您可以自己动手做：）