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())

我理解 'step 1' 递归到最左边，Node("A")，但是当到达 A 后，

func 是如何跳出那个递归的？它是否移动到下一行，"step 2"?
'step 1'中那个遍历的return值是多少？

Answer 1

是的，有很多程序员在可视化递归时遇到困难。
是的，当递归达到 Node A 时，递归确实有帮助。
函数在 if start: 语句处跳出递归（基本情况）。

顺便说一句，您发布的代码输出如下：A-B-C-D-E-F-G-H-I-

数据的基本情况示例如下：当代码输入 preorder_print() 且 start 引用 Node("A") 时，然后 if start: 通过，然后下一个语句是 traversal = self.preorder_print(start.left, traversal) 它将 start.left 传递到下一个级别。

现在因为 Node("A") 将 left 和 right 都设置为默认值 None，上面的调用是 nop 而只是 returns traversal，所以下一条语句是 traversal += str(start.value) + "-" 其中 start.value 是 "A".

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

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

python 二叉树递归

python binary tree recursion

python

recursion

binary-tree