预序二叉树遍历递推法

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的左边没有.这样if start:条件就会失败。

以下是我的问题。

在node2之后是

1. ，左是空，右是空的？(因为如果启动:条件失败)
2. 在node1之后，逻辑如何移动到node5哪个node1

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

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-