前序二叉树遍历递归方法

Question

我试图理解二叉树遍历（PreOrder）的实现。非递归方法很好，但我在试图理解递归方法时完全迷失了方向。

代码：

def preorder_print(self, start, traversal): """Root->Left->Right"""
if start:
    traversal += (str(start.value) + "-")
    traversal = self.preorder_print(start.left, traversal)
    traversal = self.preorder_print(start.right, traversal)
return traversal

二叉树

    8
   / \
  4   5
 / \   \
2   1   6

我的理解是，当到达节点2（8-4-2）时，节点2的左边没有。所以如果启动：条件将失败。

下面是我的问题。

1. 点头之后。左无，右无。右边是横穿的？（因为如果启动：条件失败）
2. 在节点1之后，逻辑如何移动到节点5哪个根节点。对吧?

我对递归的理解很差，请帮助！

Answer 1

看这个，看看这是否有帮助：

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    def addleft(self,value):
        self.left = Node(value)
    def addright(self,value):
        self.right = Node(value)
    def preorder_print(self, start, traversal='', depth=0): 
        print( " "*depth, start.value if start else "None" )
        if start:
            traversal += (str(start.value) + "-")
            print(' '*depth, "check left")
            traversal = self.preorder_print(start.left, traversal, depth+1)
            print(' '*depth, "check right")
            traversal = self.preorder_print(start.right, traversal, depth+1)
        return traversal

base = Node(8)
base.addleft(4)
base.left.addleft(2)
base.left.addright(1)
base.addright(5)
base.right.addright(6)

print( base.preorder_print( base ) )

输出：

 8
 check left
  4
  check left
   2
   check left
    None
   check right
    None
  check right
   1
   check left
    None
   check right
    None
 check right
  5
  check left
   None
  check right
   6
   check left
    None
   check right
    None
8-4-2-1-5-6-