时间戳

首页 > 解决方案 > python二叉树递归

python - python二叉树递归

问题描述

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 步”递归到最左边，节点（“A”），但是当到达 A 之后，

  1. func 是如何摆脱这种递归的？它是否进入下一行，“第 2 步”？

  2. “第 1 步”中遍历的返回值是多少？

标签： pythonrecursionbinary-tree

解决方案

  1. 是的，有很多程序员在可视化递归方面遇到了麻烦。
  2. 是的，当递归到达Node A递归确实有帮助。
  3. 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")has both leftandright设置为默认值None，上面的调用是 anop并且只是返回traversal，所以下一条语句是traversal += str(start.value) + "-"where start.valueis "A"。

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

现在我们发现自己回到了self.preorder_print()刚刚执行traversal = self.preorder_print(start.left, traversal)wherestart引用Node("B")和start.left引用的状态Node("A")。

推荐阅读