recursion - 有人可以解释递归如何用于中序 BST 遍历吗？

Question

我意识到中序遍历的代码看起来像

  if left[x] != NULL
    recurse left
    process
  right[x] !=NULL
    recurse right

我把所有东西都编码了，工作正常。然后我开始思考更多并且过度考虑了这个过程，现在迷失在递归的实际工作方式中。因为我认为一路离开，递归将结束，因为两个节点都是空的。

如果我一路向左，左右节点都为NULL，递归调用如何让我回到父节点继续遍历？

Answer 1

像所有递归*一样，调用堆栈包含您的操作控制，因为递归调用开始返回 - 程序控制返回到您的current_node指针设置为您在进行递归调用之前检查的父级的点。

（* 所有递归，除非正在进行尾调用优化，在这种情况下它只是一个循环）。