二叉树遍历 - 预购 - 访问 parent

Question

我正在尝试理解前序遍历的递归实现，如此 link http://interactivepython.org/runestone/static/pythonds/Trees/TreeTraversals.html

def preorder(tree): 
    if tree:  
        print(tree.getRootVal())  
        preorder(tree.getLefChild())  
        preorder(tree.getRightChild())

我明白 pre-order 是如何工作的，但是让我感到困惑的是上面显示的递归实现。我仍然无法弄清楚在遍历所有左侧 children 之后算法如何返回到最近的祖先（parent）。我试过在纸上解决这个问题，但仍然没有成功。

Answer 1

preorder(tree.getLefChild()) 遍历当前树的所有左子节点。该方法然后 returns，就像所有其他方法一样，然后继续处理父项的右子项。

快速可视化

def preorder(tree): 
    if tree:  
        print(tree.getRootVal())  
        preorder(tree.getLefChild())  # Expand this
        preorder(tree.getRightChild())

变成...

def preorder(tree): 
    if tree:  
        print(tree.getRootVal())  
        # Entering recursion ... 
        if (tree.getLefChild()):
            print(tree.getLefChild().getRootVal())  
            preorder(tree.getLefChild().getLefChild())  # And so on...            
            preorder(tree.getLefChild().getRightChild())  
        # Exiting recursion...
        preorder(tree.getRightChild())

二叉树遍历 - 预购 - 访问 parent

Binary Tree Traversal - Preorder - visit to parent

python

recursion

binary-tree