Python 二叉树递归

Question

class Node:
def __init__(self,value):
self.value = value 
self.right = None
self.left = None
class Tree:
def __init__(self,root):
self.root = Node(root) 
def print_tree(self):
return self.preorder_print(self.root,"")
def preorder_print(self,start,traversal):
if start:
print('step 1')
traversal = self.preorder_print(start.left, traversal)
print('step 2')
traversal +=(str(start.value)+"-")
print('step 3')
traversal = self.preorder_print(start.right, traversal)
return traversal

"""
F
B         G
A      D        I
C    E   H 
In- order print: A->B->C->D->E->F->G->H->I
"""

tree = Tree("F")
tree.root.left = Node("B")
tree.root.right = Node("G")
tree.root.right.right = Node("I")
tree.root.right.right.left = Node("H")
tree.root.left.left = Node("A")
tree.root.left.right = Node("D")
tree.root.left.right.left = Node("C")
tree.root.left.right.right = Node("E")
print(tree.print_tree())

我知道"步骤 1"递归位于最左边的 Node("A"(，但是当到达 A 后，

1. func 如何突破这种递归？它是否继续下一行"步骤 2"？

2. "步骤 1"中遍历的返回值是多少？

Answer 1

1. 是的，有很多程序员在可视化递归时遇到了困难。
2. 是的，当递归达到Node A递归确实有帮助。
3. 该函数在if start:语句处脱离递归(基本情况(。

顺便说一下，您的代码在发布时输出以下内容：A-B-C-D-E-F-G-H-I-

数据基本情况的一个示例如下：当代码以start引用Node("A")preorder_print()时，if start:传递，并且traversal = self.preorder_print(start.left, traversal)下一条语句start.left传递到下一级。

现在因为Node("A")已经将left和right都设置为默认None，所以上面的调用是一个nop，只是返回traversal，所以下一条语句就是start.value"A"的traversal += str(start.value) + "-"。

同样，下一个语句traversal = self.preorder_print(start.right, traversal)是一个nop，然后return traversal退出此级别并上升一个级别。

现在我们发现自己回到了刚刚执行traversal = self.preorder_print(start.left, traversal)self.preorder_print()，其中start指的是Node("B")，start.left指的是Node("A")。