使用递归解释进行二叉树遍历（python）

Question

我目前正在研究二叉树。我遇到了这个非常高效的遍历树的代码（在本例中，这是一个按顺序遍历）。它使用递归，这是我理解的一个概念。然而，我似乎无法理解这到底是如何工作的。最让我困惑的是，它是如何在每次列表中上升的，这样才能开始。左并不总是相同的数字。请有人一步一步地告诉我这是如何沿树向上移动的。提前谢谢

编辑以增加问题的清晰度：

1. 我明白如果开始不是无，那么开始。left被添加到同一函数的递归调用中

我的困惑之处在于，我似乎找不到代码的位置，“知道”它被遍历到4，现在下一个返回的元素是2。机制在哪里，现在停在2并返回它，等等？

class Node():

def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    
    
def __str__(self):
    return str(self.data)
    

class BinaryTree(object):
def __init__(self, root):
    self.root = Node(root)          
                    
                        
def inorder_print(self, start, traversal):
    """Left -> root -> right"""
    if start:
        traversal = self.inorder_print(start.left, traversal)
        traversal += (str(start.data) + "-")
        traversal = self.inorder_print(start.right, traversal)
        

    return traversal
    
    
    
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3) 
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)
tree.root.right.left = Node(6)
tree.root.right.right = Node(7)
tree.root.right.right.right = Node(8)

print(tree.inorder_print(tree.root, ""))

Answer 1

好吧，再坐一会儿，想清楚了。思想我张贴我的思想，这样这个问题就可以标记为已回答。

1. inorderfunc是用root和空字符串调用的。
2. start的值为tree.root，而start的值在遍历=self.inorder_print（start.left，遍历）时不断递归
3. 需要注意的是，每次递归发生时，你都会进一步深入树。start.data=1。递归，start.data=2递归，start.data=4。由于事实上，4没有左孩子。函数最终可以返回。start.data现在=4，下一行traveral=str（start.data ) "-") 可以运行，添加到字符串。但是请记住，该函数仍然是2递归深。我们的start.data回到2。作为该函数已经完成执行，2被添加到遍历通过线traveral=str（start.data ) "-")/ #递归发生start.right.start.data现在=5start.right没有值，所以函数可以返回5。这个过程在整个树中继续，直到所有已经执行的函数都完成。诀窍对于undertanding（至少对我来说）来说，当你返回到递归的更高级别时，函数从它离开的地方开始，并从一开始就开始启动函数。

Answer 2

理解算法路径的一个有用工具是向其添加日志记录。

    def inorder_print(self, start, traversal, indent=""):
        """Left -> root -> right"""
        if start:
            print(f"{indent} {start.data} <- '{traversal}'")
            traversal = self.inorder_print(start.left, traversal, indent+" ")
            traversal += (str(start.data) + "-")
            print(f"{indent} {start.data} -- '{traversal}'")
            traversal = self.inorder_print(start.right, traversal, indent+" ")
            print(f"{indent} {start.data} -> '{traversal}'")

        return traversal

允许我们可视化树以及每个节点添加到遍历中的顺序：

 1 <- ''
  2 <- ''
   4 <- ''
   4 -- '4-'
   4 -> '4-'
  2 -- '4-2-'
   5 <- '4-2-'
   5 -- '4-2-5-'
   5 -> '4-2-5-'
  2 -> '4-2-5-'
 1 -- '4-2-5-1-'
  3 <- '4-2-5-1-'
   6 <- '4-2-5-1-'
   6 -- '4-2-5-1-6-'
   6 -> '4-2-5-1-6-'
  3 -- '4-2-5-1-6-3-'
   7 <- '4-2-5-1-6-3-'
   7 -- '4-2-5-1-6-3-7-'
    8 <- '4-2-5-1-6-3-7-'
    8 -- '4-2-5-1-6-3-7-8-'
    8 -> '4-2-5-1-6-3-7-8-'
   7 -> '4-2-5-1-6-3-7-8-'
  3 -> '4-2-5-1-6-3-7-8-'
 1 -> '4-2-5-1-6-3-7-8-'

缩进显示堆栈的深度。每个单独的递归调用有三个部分——左边的孩子、self.data和右边的孩子。

代码“知道”2在4之后，因为4发生在2调用的开始处，字符串'2-'紧跟其后：

  2 <- ''          # start of 2's call.  2 starts by calling 4
   4 <- ''             # start of 4's call
   4 -- '4-'           # 4 appends self.data
   4 -> '4-'           # end of 4's call, returning to 2
  2 -- '4-2-'      # 2 appends self.data to what it got from 4, and calls 5
   5 <- '4-2-'         # start of 5's call
   5 -- '4-2-5-'       # 5 appends self.data
   5 -> '4-2-5-'       # end of 5's call, returning to 2
  2 -> '4-2-5-'    # end of 2's call