19 疑犯的二叉搜索树（第2/3页）
“现在我们来进行区间搜索。”Frank说道。
“我之前说过，我不会……”Socks说道。但Frank挥手制止了他。
“我们用一个改编版本的深度优先搜索，”Frank解释道，“从最上面的节点开始，由上到下地查找。”
“怎么查找？”Socks问道。
“对每一个节点都进行三个步骤的操作。首先，你看这个节点本身是不是在区间里面。如果是，比如这里的55天在区间里，我们就将它加入到我们的结果中。否则我们就忽略它。”
“等等，”Socks说道，“我给我们找到的结果标上另一种颜色好了。深绿色怎么样？”
“好。随便你，”Frank回复道，“在检查完当前节点后，再看看我们是否需要往两个子节点里面探索。如果需要就递归探索左右两个子节点。当然，只有在一个子节点里面的范围可能和我们要找的范围重合时才需要递归探索那个子节点。”
“递归探索？”Socks问道。
Frank等着，想看看Notation会说出什么样的学术定义。但她却异常地沉默。Frank叹了口气，解释道：“递归的意思是将同样的算法作用于一个子问题上。在我们的问题中，我们将同样的搜索算法作用于子节点上，就是以同样的方法去检查它们。
“我们只需要检查一下我们需不需要探索子节点。如果需要的话，就用同样的算法去检查它们。我们可以很容易地比较当前点的值是否在我们要找的区间里。如果当前点的值比我们要找的区间中的最小值还要小的话，就可以知道所有在其左子树中的值都不在我们要找的区间里。因此可以跳过那一个子树。反过来，如果当前节点的值比我们要找的区间中的最小值要大的话，我们就需要继续在其左子树里面搜索。
“对于右子树也是同样的道理。如果当前点的值比我们要找的区间中的最大值还大的话，我们就可以跳过右子树。否则，就需要继续向右子树里面搜索。
“现在我们要找的区间是50到70。对于这个节点55，由于其左子树中的值最大可能是55，所以其中的点可能会落在我们要找的区间中，所以我们需要去探索左子树。右子树里面的值可能会大于55，这也和我们要找的区间有重叠，所以我们也需要探索右子树。我们先从左子树开始。
“现在的节点上显示的是22天，”Frank继续说道，“我们不需要将它放进结果列表。并且，因为所有在它左子树里面的值都会比22小，因此我们也不需要去检查它的左子树了。”
“我们把这种情况叫作搜索中的剪枝
，”Notation补充道，“因为这就像从一棵树上面砍下了一个分支一样。”
当Frank看向她的时候，她想起来她不应该和Frank说话，便又沉默了。
“所以我们只要探索右边的分支就好。”Frank说道。
“递归着探索！”Socks补充道，听起来他简直太欢乐了。
“对，递归着探索，”Frank冷淡地同意道，“现在的节点上是38天。同样的，我们不需要将它加到结果列表中，并且我们也可以跳过它的左子树。”
“但我们需要递归探索它的右子树。”Socks说道。看起来他挺享受这个新的算法。
Frank点了点头。
下一个点没有子节点了。它已经是一条死路了。
“现在呢？”Socks问道。
“和深度优先搜索一样，”Frank说道，“我们倒退，并且选择之前还没有探索过的路线，直到我们将整棵树都搜索过了为止。因为我们一路上剪掉了很多分支，所以我们需要一直倒退到根节点。”
搜索接着在根节点的右子树里开始了。被找到的新记录被加入了结果列表，不合适的分支被一个个剪掉，而合适的分支则被递归地探索着。
最后他们找到了几条符合条件的调职记录。Frank仔细地研究了找到的结果，试图找出任何可疑的地方。
“什么都没有，”他难以置信地低吼了一声，“这里面什么都没有！”
警用算法导论：二叉搜索树Ⅲ
节选自Drecker教授讲义
在二叉搜索树上进行区间查找和查找一个元素类似。算法从最顶端的根节点开始，一路递归着搜索整棵树。它根据以下三个条件来对在每一个节点做决定：
1.当前节点应该被算在结果中吗？如果当前节点在要找的区间内，我们就应该将它加到结果列表中。