在python中循环遍历树形结构？

Question

我在这里很新，很新的python！

我们得到了一个功课，我已经能够做的是休息，但有一个问题依然存在： 如果我有一个树状分层结构是这样的：

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或者您可以使用iteration。无论哪种方式都没有关系。但是你需要一个搜索树的策略。

这里有一些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

例如：

# 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 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) 

让我们构建一个样本树结构：

root = TreeHierarchyClass(0) 

for i in range(10): 
    root.add(i) 

for i in range(10): 
    root.children[1].add(i + 10) 

现在让我们找到了一些物品：

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.