Wie diese Python-Generatoren basierte inorder traversal Methode funktioniert

Question

Ich bin ziemlich neu zu Python und noch zu erkunden. Stieß auf Generatoren und unter Code-Schnipsel Inorder Binärbaum Traversal mit Generatoren Implementierung:

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

     yield t.label 

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

Jetzt weiß ich folgende Tatsache über Generatoren: sie erinnern sich an die lokalen Variablenwerte über Anrufe. Diese Funktion ist jedoch rekursiv. Wie speichert es die lokalen Variablenwerte über diese verschiedenen rekursiven Aufrufe hinweg?

Auch war es einfach zu normalen rekursiven Inorder-Programm zu verstehen (nicht mit Generatoren), da klare Rekursion Terminationsbedingungen explizit angegeben wurden. Aber wie funktioniert diese Rekursion mit Generatoren?

Answer 1

inorder gibt einen Generator zurück. Das Objekt ist, was seinen lokalen Status zwischen den Anrufen an next erinnert. Es gibt keine Überschneidung zwischen Generatoren, die durch separate Aufrufe an inorder erstellt wurden, selbst wenn sie rekursiv aufgerufen werden.

Answer 2

Ich modifizierte den Code etwas, um die Idee des Ablaufs der Ausführungssequenz zu bekommen. Grundsätzlich habe ich einige print() Aussagen hinzugefügt.

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) 

Der Ausgang ist:

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 

Hinweis, dass der zweite Anruf inorder(node4) didnt Druck at the beginning of inorder(t): 4 aber es at the beginning of inorder(t): None gedruckt (Linie 9 in Ausgang). Das bedeutet, dass sich die Generatoren auch an die zuletzt ausgeführte Zeile erinnern (vor allem, weil sie den Zählerwert des Programms beim letzten Aufruf speichert).

Auch jede for-Schleife bezieht die Generatorinstanz von der Funktion inorder(). Dieser Generator ist spezifisch für eine for-Schleife und daher wird der lokale Bereich separat aufrechterhalten.

Above quert diesen Baum:

4 
/\ 
    2 5 
/\ 
1 3 

Auch die Kündigung tritt auf, wenn jede der rekursiven Aufrufe zu Ende erreichen. Dieses Ergebnis in folgenden rekursiven Aufrufbaum:

==>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 

(explaination:

• <i> bedeutet Anruf mit nodei als Parameter
• left<i> repräsentiert inorder(t.left) Anruf innerhalb der ersten for-in Schleife, wo t.left ist nodei
• right<i> repräsentiert inorder(t.right) Anruf innerhalb Sekunde for-in Schleife, wo t.right ist nodei
• ===> zeigt, wo die Ausführung in diesem bestimmten Anruf beginnt)