이 파이썬 생성기 기반의 순회 방식이 작동하는 방식

Question

저는 파이썬에 대해 아직 익숙하지 않고 여전히 탐구하고 있습니다.

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를 구현하는 코드 아래에 온 그들은 통화에서 로컬 변수 값을 기억한다. 그러나이 함수는 재귀 적입니다. 그렇다면이 재귀 호출을 통해 지역 변수 값을 기억하는 방법은 무엇입니까?

명확한 재귀 종료 조건이 명시 적으로 지정되었으므로 일반 재귀 적 inorder 프로그램 (생성자는 포함하지 않음)을 쉽게 이해할 수있었습니다. 그러나 발전기로이 재귀가 어떻게 작동합니까?

Answer 1

inorder은 생성기를 반환합니다. 개체는 next으로 전화하는 사이에 로컬 상태를 기억합니다. 재귀 적으로 호출 된 경우에도 inorder에 대한 별도의 호출로 생성 된 생성자 간에는 중복이 없습니다.

Answer 2

실행 순서의 흐름을 알기 위해 코드를 다소 수정했습니다. 기본적으로 일부 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) 

출력은 : 제 호출 inorder(node4) didnt 한 인쇄 at the beginning of inorder(t): 4로하지만 at the beginning of inorder(t): None 인쇄 것을

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 

통지 (출력 라인 (9)). 즉, 발전기는 최종 실행 라인을 기억합니다 (대부분 마지막 호출에서 프로그램 카운터 값을 기억하기 때문입니다).

또한 모든 for 루프는 inorder() 함수에서 생성자 인스턴스를 가져옵니다. 이 생성자는 for 루프에만 해당되므로 로컬 범위가 별도로 유지 관리됩니다. 재귀 호출의 각각의 끝에 도달했을 때

4 
/\ 
    2 5 
/\ 
1 3 

이 또한 종료가 발생

위는이 나무를 통과. 재귀 호출 트리 다음이 결과 :

==>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>는 t.left가 nodei
• right<i>이다
• left<i> 먼저 for-in 루프 내부 inorder(t.left) 호출을 나타내는 파라미터로서 nodei와 통화를 의미 inorder(t.right)을 두 번째로 호출합니다.실행) 특정 통화가 시작되는 t.rightnodei
• ===>이다루프 도시