基於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生成器如何工作

回答

相關問題