基于inorder遍历方法的Python生成器如何工作

-1

我对python还很陌生，至今仍在探索。碰到发电机及以下执行序二叉树的遍历使用生成的代码片段：基于inorder遍历方法的Python生成器如何工作

def inorder(t): 
    if t: 
     for x in inorder(t.left): 
      yield x 

     yield t.label 

     for x in inorder(t.right): 
      yield x

现在我知道以下事实有关发电机：他们记得在调用局部变量的值。但是这个函数是递归的。那么它如何记住这些不同的递归调用中的局部变量值呢？

此外，它很容易理解正常的递归inorder程序（不涉及生成器），因为明确指定了明确的递归终止条件。但是，这种发电机的递归是如何工作的？

来源

2016-10-18 Mahesha999

inorder返回一个发生器。那对象是在拨打next的电话之间记得它的本地状态。即使在递归调用时，通过对inorder的单独调用创建的生成器之间没有重叠。

来源

2016-10-18 14:06:41 chepner

我稍微修改了一下代码，以获得执行序列流的概念。基本上我加了一些print()陈述。

class BinaryTreeNode(): 
    def __init__(self, pLeft, pRight, pValue): 
     self.left = pLeft 
     self.right = pRight 
     self.label = pValue 

def inorder(t): 
    print("at the beginning of inorder(t): " + (str(t.label) if t else "None")) 
    if t: 
     for x in inorder(t.left): 
      print("inside inorder(t.left):" + str(t.label)) #delete 
      yield x 

     print("inside inorder(t):" + str(t.label)) #delete 
     yield t.label 

     for x in inorder(t.right): 
      print("inside inorder(t.right):" + str(t.label)) #delete 
      yield x 

node1 = BinaryTreeNode(None,None,1) 
node3 = BinaryTreeNode(None,None,3) 
node2 = BinaryTreeNode(node1,node3,2) 
node5 = BinaryTreeNode(None,None,5) 
node4 = BinaryTreeNode(node2,node5,4) 

root = node4 

for i in inorder(root): 
    print(i)

的输出是：

1 at the beginning of inorder(t): 4 
2 at the beginning of inorder(t): 2 
3 at the beginning of inorder(t): 1 
4 at the beginning of inorder(t): None 
5 inside inorder(t):1 
6 inside inorder(t.left):2 
7 inside inorder(t.left):4 
8 1 
9 at the beginning of inorder(t): None 
10 inside inorder(t):2 
11 inside inorder(t.left):4 
12 2 
13 at the beginning of inorder(t): 3 
14 at the beginning of inorder(t): None 
15 inside inorder(t):3 
16 inside inorder(t.right):2 
17 inside inorder(t.left):4 
18 3 
19 at the beginning of inorder(t): None 
20 inside inorder(t):4 
21 4 
22 at the beginning of inorder(t): 5 
23 at the beginning of inorder(t): None 
24 inside inorder(t):5 
25 inside inorder(t.right):4 
26 5 
27 at the beginning of inorder(t): None

注意，第二呼叫到inorder(node4) didnt打印at the beginning of inorder(t): 4但它印刷at the beginning of inorder(t): None（在输出线9）。这意味着生成器还会记住最后一次执行的行（主要是因为它记住了上次调用中的程序计数器值）。

另外，每个for循环都从函数inorder()中获取生成器实例。这个生成器专用于循环，因此局部范围是分开维护的。

以上遍历这棵树：

当每个递归调用达到其最终也会发生终止。这个结果在下面的递归调用树：

==>inorder(<4>) 
    |---> x in inorder(left<2>) 
       |---> x in inorder(left<1>) 
           |---> x in inorder(left<None>) --> terminate 
            yield 1 (note the indention, it is not yield inside first for-in loop but after it) 
          yield 1 (note the indentation, this is yield inside first for-in loop) 
       yield 1 



inorder(<4>) 
    |---> x in inorder(left<2>) 
       |---> x in inorder(left<1>)   
==============================>|---> x in inorder(right<None>) --> terminate 
         yield 2 
       yield 2 



inorder(<4>) 
    |---> x in inorder(left<2>) 
================>|---> x in inorder(right<3>)              
           |---> x in inorder(left<None>) --> terminate 
            yield 3 
          yield 3 
       yield 3  



inorder(<4>) 
    |---> x in inorder(left<2>) 
       |---> x in inorder(left<1>)   
=============================>|---> x in inorder(right<None>) --> terminate 
         terminate 
      terminate 
     yield 4 



inorder(4) 
==>|---> x in inorder(right<5>) 
       |---> x in inorder(left<None>) --> terminate 
         yield 5 
       yield 5 


inorder(4) 
    |---> x in inorder(right<5>)     
===============>|---> x in inorder(right<None>) --> terminate 
         terminate 
       terminate 
     terminate

（交代：

<i>意味着nodei作为参数调用
left<i>表示第一for-in循环内inorder(t.left)呼叫其中t.left是nodei
right<i>代表inorder(t.right)第二个0123内的呼叫回路，其中t.right是nodei
===>示出了其中执行在那个特定的呼叫开始）

来源

2016-10-18 14:25:20 Mahesha999

基于inorder遍历方法的Python生成器如何工作

回答

相关问题