python-3.x - 这个递归函数是如何工作的，是关于计算结构的吗？

我正在使用树遍历代码，我已经获得了伪代码，并且我在 python 中实现了它，但我仍然无法弄清楚它是如何工作的

InOrderTraversal(tree):
  if tree = nil:
     return
  InOrderTraversal(tree.left)
  Print(tree.key)
  InOrderTraversal(tree.right)

伪代码如上所示： InOrderTraversal(tree.left)：这段代码找到树的最左边的节点，我以为它会停在那里。但是它怎么能回到它的父母那里呢？并遍历树的所有节点。它可以返回节点，这就是我所困惑的，是关于计算机的一些内部结构

标签： python-3.xrecursiontree

上面的伪代码迭代了Tree，它是一种数据结构。

递归函数是在满足终止条件之前调用自身的函数。

在树中，有一个根节点，它将有一个左孩子和一个右孩子，每个孩子可能有一个相似的左右孩子（或者可能没有或没有左孩子或右孩子）。

如果假设任何孩子（或根）没有右孩子，那么右孩子将为空，左孩子也是如此。

所以上面的代码调用了自己两次，一次迭代左分支，第二次迭代右分支。

我会尽量用简单的语言来解释，而不是使用大量的技术术语和令人困惑的概念，（保持简单）：

让我们谈谈仅左分支（例如），

假设它就像 ABCDE

现在，A is root第一个函数调用将使用调用A as ref，因为它的左孩子不等于 null（即有孩子），它现在将InOrderTraversal使用 A 的孩子 ieB as ref调用，同时我们使用 A 的 ref 调用的函数存储在call-stack,

再一次，B的孩子是C，它也不是空的，所以函数InOrderTraversal被再次调用C's ref，并将call-stack引用存储到B的函数调用中，

此时调用堆栈看起来像这样

 InOrderTraversal(C)
 InOrderTraversal(B)
 InOrderTraversal(A)

这样一直持续到E，现在E没有child，所以它会返回调用他的函数，即用D的ref进行函数调用，然后再次返回，最后我们将进入main函数调用，它生成了所有函数调用。

右分支也是如此。

所以这是可能的call-stack。

我试图解释让你感到困惑的部分。

我希望这可以帮助您理解它。