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

Question

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

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

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

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

Answer 1

与所有递归*一样，调用堆栈包含对您的操作的控制，因为递归调用开始 return - 程序控制 returned 到您的 current_node指针设置为您在进行递归调用之前正在检查的父项。

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