这个算法怎么能对in-order树遍历"climb up"树呢？

Question

我看到很多关于树遍历的教程，但我对 in-order 算法究竟如何让我们“爬上”树感到困惑。

例如，在下面的树中，我理解我们一直向左移动直到没有 children 然后我们追加值。但是算法中的什么允许我们“爬回”到值 2 等的节点？[=14=]

我很难理解这一点。我随处可见的 Python 中的算法是这样的：

def printInorder(root):
    if root:
        # First recur on left child
        printInorder(root.left)
        # then print the data of node
        print(root.val),
        # now recur on right child
        printInorder(root.right)

Answer 1

好吧，让我从这个角度解释一下。您知道这样一个事实，即一旦您打印了根节点，那么您需要对以左 child 为根的子树和以右 child 为根节点的子树进行相同的中序遍历。

我们如何向上遍历？只是当我们回到递归调用时。是的，这可能感觉有点奇怪，但这就是函数调用的工作方式，一旦被调用的函数完成，控件就会转到 parent 函数，然后它完成工作，控件就会转到 parent 函数。

现在你问了这个问题，

what "tells the algorithm" that we visited Node 1 and to no longer go to the left

它实际上在 1 的左边，这基本上不再是一个节点了。只是 None 现在函数看到你有一个 if 语句说 do the work only if root is not None。这就是该函数停止进一步调用的地方。完成后，它会返回到它的 parent，即 1。现在在 1 打印 1 之后，我们再次调用遍历 1 的 right child 但同样是 None 所以同样的事情发生。然后在节点 1 处，我们已经完成了我们要求方法在 if 块中执行的所有操作。它返回到节点 2 parent.

这就是它的工作原理。这张图会解释的很清楚：

这个算法怎么能对in-order树遍历"climb up"树呢？

How can this algorithm for in-order tree traversal "climb up" the tree?

python

algorithm

recursion

binary-search-tree