二叉树遍历预序访问paren

Question

我试图理解如链接http://interactivepython.org/runestone/static/pythonds/Trees/TreeTraversals.html所示的前序遍历的递归实现

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

我理解预订单是如何工作的，但是我对上面显示的递归实现感到慌乱。我仍然不知道在遍历所有剩余的子代之后，算法如何返回到最近的祖先（父代）。我试过在纸上解决这个问题，但还是不成功。你知道吗

Answer 1

preorder(tree.getLefChild())遍历当前树的所有剩余子级。然后该方法返回，就像所有其他方法一样，然后继续处理父对象的正确子对象。你知道吗

快速可视化

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())