파이썬에서 트리 계층 구조를 순환?

Question

저는 여기에서 새롭고 파이썬에 꽤 새로운 것입니다!

우리는 숙제를 가지고, 나는 이미 그 나머지를 할 수 있었다,하지만 한 가지 문제가 남아있다 :이 같은 트리 계층이있는 경우 을 :

root = [ 
    parent1 = [ 
     child1, 
     child2 = [ 
      sub_child 
     ] 
     child3 
    ], 
    parent2 = [ 
     child1, 
     child2 
    ] 
] 

을 그리고 그들은 하나 개의 클래스의 모든 인스턴스 TreeHierarchyClass으로 이름이 지정되어 있으며 모두 이름 속성이 있습니다. 입력 한 이름으로 어떻게 찾을 수 있습니까?

루프를 사용하려고했지만 얼마나 많이 필요합니까? 이름을 알아내는 것은 쉽습니다.

name = input("Enter name: ") 
if name == TreeHierarchyObject.name: 
    print("Found it!") 

어떻게 객체를 반복합니까?

Answer 1

간단한 재귀를 사용해야합니다. 이 메서드는 자식 개체가 부모 개체에 어떻게 첨부되는지에 따라 조금씩 다릅니다.

목록에있는 경우 self.children 인 경우이 방법을 사용하는 것이 좋습니다.

def findObjectByName(self, name): 
    if self.name == name: 
     return self 
    else: 
     for child in self.children: 
      match = child.findObjectByName(name) 
      if match: 
       return match 

편집 : 대신 getattr()를 사용뿐만 아니라 이름, 모든 속성이 작품을 만들기 위해 :

def findObject(self, attr, value): 
    if getattr(self, attr) == value: 
     return self 
    else: 
     for child in self.children: 
      match = child.findObject(attr, value) 
      if match: 
       return match 

를 그리고 단순히 root.findObjectByName("Sub Child!") 전화를 걸거나 그냥 클래스 내부에 다음과 같은 방법을 정의 두 번째 방법을 사용하려면 root.findObject("name", "Sub Child!")

Answer 2

recursion을 사용하거나를 사용할 수 있습니다.. 어쨌든 상관 없습니다. 그러나 나무를 검색하는 전략이 필요합니다. 여기

그래프를 통해 이동하는 몇 가지 strategry 있습니다

• http://en.wikipedia.org/wiki/Breadth-first_search
• http://en.wikipedia.org/wiki/Depth-first_search

주요 아이디어에 대한 사소한 두 번 같은 노드/잎, 통과하지 않는 것입니다 그래프에는 coloring이 필요합니다.

• http://en.wikipedia.org/wiki/Graph_coloring

사용할 수있는 디자인 패턴이 몇 가지 있습니다. visitor 패턴을 사용하고 .visit() 메서드를 TreeHierarchyClass에 추가하면 해당 하위 노드를 방문하고 다른 하나는 이름으로 노드를 찾습니다.

• http://en.wikipedia.org/wiki/Visitor_pattern

예 :

:의은 샘플 트리 구조를 구축 할 수

def visit(tree): 
    visited = set() 
    nonvisited = set() 
    nonvisited.update(tree.children) 
    while nonvisited: 
     item = nonvisited.pop() 
     # already seen 
     if item in visited: 
      continue 
     # mark item 
     visited.add(item) 
     yield item 
     # add children 
     nonvisited.update(item.children) 

: 당신은 모든 노드를 방문 할 수 있습니다

# imagine we got this class 
class TreeHierarchyClass(object): 
    def __init__(self, value): 
     self.children = [] 
     self.value = value 
     if self.value == 13: 
      self.name = 'the lucky one.' 
    def add(self, value): 
     self.children.append(type(self)(value)) 

지금의이 일부 항목을 찾을 수 있습니다 :

def find(name): 
    for item in visit(root): 
     print 'checking item with value %d' % item.value, 
     if getattr(item, 'name', None) == name: 
      print '- found it.' 
      break 
     else: 
      print '- nope, keep searching.' 
    else: 
     print 'Sorry, not found.' 

find('the lucky one.') 
find('the lost one.') 

이 예제가 인쇄됩니다 :

>>> find('the lucky one.') 
checking item with value 7 - nope, keep searching. 
checking item with value 0 - nope, keep searching. 
checking item with value 1 - nope, keep searching. 
checking item with value 12 - nope, keep searching. 
checking item with value 2 - nope, keep searching. 
checking item with value 9 - nope, keep searching. 
checking item with value 19 - nope, keep searching. 
checking item with value 3 - nope, keep searching. 
checking item with value 11 - nope, keep searching. 
checking item with value 4 - nope, keep searching. 
checking item with value 14 - nope, keep searching. 
checking item with value 5 - nope, keep searching. 
checking item with value 6 - nope, keep searching. 
checking item with value 15 - nope, keep searching. 
checking item with value 8 - nope, keep searching. 
checking item with value 16 - nope, keep searching. 
checking item with value 13 - found it. 
>>> find('the lost one.') 
checking item with value 7 - nope, keep searching. 
checking item with value 0 - nope, keep searching. 
checking item with value 1 - nope, keep searching. 
checking item with value 12 - nope, keep searching. 
checking item with value 2 - nope, keep searching. 
checking item with value 9 - nope, keep searching. 
checking item with value 19 - nope, keep searching. 
checking item with value 3 - nope, keep searching. 
checking item with value 11 - nope, keep searching. 
checking item with value 4 - nope, keep searching. 
checking item with value 14 - nope, keep searching. 
checking item with value 5 - nope, keep searching. 
checking item with value 6 - nope, keep searching. 
checking item with value 15 - nope, keep searching. 
checking item with value 8 - nope, keep searching. 
checking item with value 16 - nope, keep searching. 
checking item with value 13 - nope, keep searching. 
checking item with value 17 - nope, keep searching. 
checking item with value 10 - nope, keep searching. 
checking item with value 18 - nope, keep searching. 
Sorry, not found.