二叉搜索树递归混淆

当你递归到下一个级别时,基本上需要拍下你所在位置的快照,然后去做其他事情。一旦“其他东西”完成,您将返回快照并继续。

这和打电话很相似 不 -递归函数。当函数调用 xyzzy() ,它确切地知道呼叫返回时从何处继续。递归函数是相同的,除了它们都通过 相同的 一段段代码正在下降和上升。

所以,当你回来的时候 向上的 一个级别(例如,处理了左侧的节点),然后将打印当前节点,然后在子树的右侧向下。

考虑示例树:

  2
 / \
1   4
   / \
  3   5
       \
        6

要处理此树,对于每个节点(从2开始),处理左节点,打印当前节点值,然后处理右节点。

但是,您需要理解“处理左/右节点”是在其中一个子节点上重复的整个“处理左、打印当前、处理右”步骤集。从这个意义上说 不 处理根节点和处理任何其他节点之间的差异。

“处理”是按顺序打印出给定点(包括该点)下的所有节点。如果从根节点开始,就会得到整个树,这是一个很好的效果:-)

因此,就实际发生的情况而言,它基本上遵循递归路径:

  2, has a left node 1, process it:
  |  1, has no left node.
> |  1, print 1.
  |  1, has no right node.
  |  1, done.
> 2, print 2.
  2, has a right node 4, process it.
  |  4, has a left node 3, process it.
  |  |  3, has no left node.
> |  |  3, print 3.
  |  |  3, has no right node.
  |  |  3, done.
> |  4, print 4.
  |  4, has a right node 5, process it.
  |  |  5, has no left node.
> |  |  5, print 5.
  |  |  5, has a right node 6, process it.
  |  |  |  6, has no left node.
> |  |  |  6, print 6.
  |  |  |  6, has no right node.
  |  |  |  6, done.
  |  |  5, done.
  |  4, done.
  2, done.

如果检查每个打印行(请参阅 > 标记),您将看到它们以所需的顺序出现。