Python의 트리에서 노드를 찾아서 반환합니다.

Question

class WNode(object): 
    def __init__(self,w): 
     self._w=w 
     self._content=[] 
    def find(self, x): 
     if self._w is x: 
      return self 
     else: 
      for i in self._content: 
       return i.find(x) 
     return None 

안녕하세요. x가있는 경우 재귀를 사용하여 tree에 이름 x가있는 노드를 반환하는 메서드 tree.find (self, x)를 만드는 데 문제가 있습니다. 내가 작성한 것은 특정 경우에만 작동하는 것처럼 보이지만 다른 노드에서는 (특히 큰 나무에서는) 노드가있는 경우에도 None을 반환합니다. 누군가가 x 노드를 반환하는 작동 find (self, x) 메서드를 만드는 방법을 알고 있습니까?

Answer 1

다른 답변입니다. 당신과 Todd Tao의 솔루션과 유사하게 DFS를 구현합니다. 그러나 분기를 성공적으로 탐색하지 못하면 다음 분기로 계속 진행합니다. 귀하의 코드는 가장 왼쪽에있는 지점만을 검색했습니다.

class WNode(object): 

    def __init__(self,w): 
     self._w=w 
     self._content=[] 

    def find(self, x): 
     if self._w == x: 
      return self 
     else: 
      y = None 
      for i in self._content: 
       y = i.find(x) 
       if y: 
        break 
      return y 
     return None 

if __name__ == '__main__': 
    r = WNode(1) 
    r._content = [WNode(2), WNode(3), WNode(4)] 
    for i in xrange(1, 6): 
     print('find({}) = {}'.format(i, r.find(i))) 

Answer 2

find 함수는 가장 왼쪽 분기의 노드 만 찾았 기 때문입니다. 아래 나무의 예를 생각 : 당신이 노드 C. 찾고있는

 A 
    / \ 
    B  C 
/\ 
D E 

을 감안할 때 귀하의 find 기능은 다음이 for 루프를 종료하고, 그래서 D. D에 아이가없는 확인, 먼저 지점 B를 찾습니다 None을 반환하십시오. 반환 된 것이 있기 때문에 다른 지점을 검색하지 않습니다.

실제로 트리에서 노드를 찾으려면 BFS 또는 DFS 알고리즘을 구현하여 트리를 탐색해야합니다. 당신의 find 기능은 DFS를하기 때문에, 나는 당신을 위해 DFS를 코딩합니다 : find 확인해야 모든 노드를 기록하는 검색 경로로

def find(self,x): 
    s_list = [] 
    if self._w is x: 
    return self 
    else: 
    s_list.extend(self._content) 
    while s_list: 
     node = s_list.pop() 
     if node._w is x: 
     return node 
     else: 
     s_list.extend(node._content) 
    return None 

s_list 작품. 모든 노드가 검사 된 경우 None을 반환합니다.