19 疑犯的二叉搜索树（第2/4页）

“好，”Socks说道，“这需要一些时间，我只习惯用buttons来建树，现实中真正存在的buttons。我还从来没有用它来整理过信息。我需要更改一下我的咒语。”

Socks趴在Frank的桌上，在一张羊皮纸上写着更改后的咒语，这时Notation直截了当地问Frank道：“到底发生什么了？”

“没什么。”Frank说道。

“你就算了吧，”Notation生气地说道，“自从去了监狱之后，你就在隐瞒着什么。为什么我们需要查调职记录？你为什么之前从来没有提到过这个？你们到底发现什么了？”

“我都说了，只是我的直觉。”

“我不信。你在对我隐瞒什么？”

Frank没有回答。

“改好了，”Socks说道，“至少我觉得改好了。我们过一会儿就知道了。”

Socks转向了那一摞本子，开始念咒语。他对着那堆纸夸张地挥舞着手臂。突然一下，一个巨大的二叉搜索树出现在了空中。每个节点都写着一次调职申请的日期距离目前的天数。那些节点都浮在空中，之间被蓝色的线连着。

“现在我们来进行区间搜索。”Frank说道。

“我之前说过，我不会……”Socks说道。但Frank挥手制止了他。

“我们用一个改编版本的深度优先搜索，”Frank解释道，“从最上面的节点开始，由上到下地查找。”

“怎么查找？”Socks问道。

“对每一个节点都进行三个步骤的操作。首先，你看这个节点本身是不是在区间里面。如果是，比如这里的55天在区间里，我们就将它加入到我们的结果中。否则我们就忽略它。”

“等等，”Socks说道，“我给我们找到的结果标上另一种颜色好了。深绿色怎么样？”

“好。随便你，”Frank回复道，“在检查完当前节点后，再看看我们是否需要往两个子节点里面探索。如果需要就递归探索左右两个子节点。当然，只有在一个子节点里面的范围可能和我们要找的范围重合时才需要递归探索那个子节点。”

“递归探索？”Socks问道。

Frank等着，想看看Notation会说出什么样的学术定义。但她却异常地沉默。Frank叹了口气，解释道：“递归的意思是将同样的算法作用于一个子问题上。在我们的问题中，我们将同样的搜索算法作用于子节点上，就是以同样的方法去检查它们。

“我们只需要检查一下我们需不需要探索子节点。如果需要的话，就用同样的算法去检查它们。我们可以很容易地比较当前点的值是否在我们要找的区间里。如果当前点的值比我们要找的区间中的最小值还要小的话，就可以知道所有在其左子树中的值都不在我们要找的区间里。因此可以跳过那一个子树。反过来，如果当前节点的值比我们要找的区间中的最小值要大的话，我们就需要继续在其左子树里面搜索。

“对于右子树也是同样的道理。如果当前点的值比我们要找的区间中的最大值还大的话，我们就可以跳过右子树。否则，就需要继续向右子树里面搜索。

“现在我们要找的区间是50到70。对于这个节点55，由于其左子树中的值最大可能是55，所以其中的点可能会落在我们要找的区间中，所以我们需要去探索左子树。右子树里面的值可能会大于55，这也和我们要找的区间有重叠，所以我们也需要探索右子树。我们先从左子树开始。

“现在的节点上显示的是22天，”Frank继续说道，“我们不需要将它放进结果列表。并且，因为所有在它左子树里面的值都会比22小，因此我们也不需要去检查它的左子树了。”