代码之家 › 专栏 › 技术社区 › Jimmy

这种算法怎么能按顺序遍历树“爬上”树呢?

binary-search-tree recursion algorithm python

Jimmy · 技术社区 · 2 年前

我看到了很多关于树遍历的教程,我对顺序算法如何允许我们“爬上”树感到困惑。

例如,在下面的树中,我知道我们一直向左走,直到没有子对象,然后我们附加值。但算法中的什么允许我们“爬回”值为2的节点,等等。?

我很难理解这一点。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)

1 回复 | 直到 2 年前

mkrieger1 2 年前

让我从这个角度来解释一下。您知道这样一个事实,即一旦打印了根节点,就需要对以左child作为根的子树和以右child作为根节点的子树执行相同的顺序遍历。

我们如何向上移动?这只是当我们回到递归调用时。是的,这可能感觉有点奇怪,但函数调用就是这样工作的,一旦被调用的函数完成,控件就会转到父函数,然后它完成工作,控件就会转到父函数。

现在你问了这个问题,

什么“告诉算法”我们访问了节点1,不再去了左边

它实际上是在左边 1 它基本上不再是一个节点了。只是 None 现在,函数会显示 if 声明说 do the work only if root is not None .这就是这个函数停止进一步调用的地方。一旦完成,它就会回到它的父对象,也就是 1. . 现在 1. 印后 1. 然后,我们再次调用 right 孩子 1. 但又是这样 没有一个 所以同样的事情也发生了。然后在节点 1. 我们已经完成了我们要求该方法在 如果 块它返回到node 2 父母。