前序二叉树遍历递归方法

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

二叉树

我的理解是到达节点 2(8-4-2) 时，节点 2 的左侧是 None。所以 if start: 条件会失败。

以下是我的问题。

node2.left后是None，node2.right如何遍历？（因为如果开始：条件失败）
在node1之后，逻辑如何移动到rootNode.right的node5？

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

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-

前序二叉树遍历递归方法

Preorder Binary Tree traversal Recursive method

python

preorder