트리에서 노드 찾기

Question

임의의 분기 요인이있는 트리에서 노드를 찾는 데 문제가 있습니다. 각 노드는 데이터를 전달하며 0 이상의 자식을가집니다. 검색 방법은 Node 클래스 내에 있으며 은 노드가 데이터를 전달하는지 확인한 다음 해당 노드의 모든 자식을 검사합니다. 나는 재귀 적 방법으로 무한 루프로 끝나고있다.

def find(self, x): 

    _level = [self] 
    _nextlevel = [] 

    if _level == []: 
     return None 
    else: 
     for node in _level: 
      if node.data is x: 
       return node 
      _nextlevel += node.children 
     _level = _nextlevel 
    return self.find(x) + _level 

find 메소드는 Node 클래스에 있으며 데이터 x가 메소드가 호출 된 노드에 있는지 검사 한 다음 해당 노드 children을 모두 검사합니다. 나는 무한 루프를 계속하고 있으며,이 시점에서 정말로 통찰력을 얻었습니다.

Answer 1

이 코드에는 몇 가지 문제가 있습니다. 먼저 2 행에 _level = [self]이 있다는 것을 유의하십시오. 즉, 라인 5의 if _level == []은 항상 false가됩니다. 위에서 언급 한 바와 같이

2 차 문제 때문에 항상 라인 2

3 번째 문제는 반환 진술에 [self] 될 것이다, 당신의 for 루프가 _level 모든 것을 넘어 것입니다,하지만. return self.find(x) + _level이 있습니다. 2 부분으로 평가됩니다. 먼저 self.find(x)을 호출 한 다음 반환되는 내용을 _level의 내용으로 연결합니다. 그러나 self.find(x)을 호출하면 동일한 인수를 사용하여 동일한 메소드를 호출하고 차례로 동일한 return self.find(x) + _level 행을 다시 호출하여 동일한 메소드를 다시 호출하고 영원히 계속합니다.

Answer 2

재귀 검색의 간단한 패턴은 생성기를 사용하는 것입니다. 따라서 재귀 상태를 직접 관리하지 않고도 호출 코드에 대한 응답을 쉽게 전달할 수 있습니다.

class Example(object): 
    def __init__(self, datum, *children): 
     self.Children = list(children) # < assumed to be of the same or duck-similar class 
     self.Datum = datum 

    def GetChildren(self): 
     for item in self.Children: 
      for subitem in item.GetChildren(): 
       yield subitem 
      yield item 

    def FindInChildren(self, query): # where query is an expression that is true for desired data 
     for item in self.GetChildren(): 
      if query(item): 
       yield item