使用gen的python树枚举器方法

Question

我实际上在使用Jython，对Python的工作方式非常陌生。。。在

当我使用javax.swing.tree.DefaultMutableTreeNode我可以简单地转到depth/breadthFirstEnumeration（）。。。在

但是，如果我使用DOM树（例如来自XML）的东西，就没有这样的等价物了。。。但我突然意识到，在Python/Jython中，必须有一种非常优雅和强大的方法来使用递归生成器来实现这一点。在

希望我想要的是实用程序方法的最一般用途，它基本上可以对任何类型的树对象进行枚举。。。因此，您可能需要提供一个方法来提供给定节点的子节点。。。以org.w3c为例。dom.节点这将是getChildNodes（）。。。然后，您可能需要第二个可选参数来指定深度或宽度。。。在

令我惊讶的是，我还没有找到一个简单的答案，仅仅是通过谷歌或在这里看看，例如。在

Answer 1

谢谢。。。在我等待的时候，我一直在努力自己解决问题。。在

免责声明：我在费迪南德提出他完美答案的最终版本之前写了这篇文章

事实上，你的解决方案对于一个由常规Python列表组成的树来说工作得很好。。。不幸的是org.w3c。dom.节点尤其是“迟钝”。。。getChildNodes（）实际上生成一个名为NodeList的对象，尽管它显然是某种类型的列表（Java数组），但它仍然是封闭的，不会被内省。。。特别是dir（）将告诉您其“childNodes”字段的类是org.apache.xerces网站.dom.DeferredElementImpl"... 我的经验是，任何以“Impl”结尾的东西玩起来都不会很有趣。。。在

因此，我显然找不到方法作为参数传递并调用它。。。即使有一个更易于接受的类Python，我目前还不清楚如何调用作为参数传递的方法。。。不管怎样。。。在

下面是我的3个选项，非常不言而喻：1）深度优先2）深度或宽度优先选择3）相同，但提供的内容有深度指示（例如，您可以格式化打印输出）。 不幸的是，在解决方案3中，我被迫创建了一个新类，因为我发现无法向节点对象添加属性。。。显然，与Python相比，Jython有局限性和“杂质”。我知道有些python模块用于处理XML等。。。会在适当的时候调查。 （当然，Jython的一个很好的方面是，您可以逐步地从Java转换到Python）。在

如果有经验的Python/Jython的人有什么意见，我会很感兴趣。。。在

1. 仅深度优先：

   def depthFirstTreeEnumeration( node ):
     nodeList = node.getChildNodes()
     for i in range( nodeList.getLength()):
       childNode = nodeList.item( i )
       yield childNode
       for item in depthFirstTreeEnumeration( childNode ):
         yield item
   

2. 深度或广度优先选择

   def treeEnumeration( node, depthFirst = True ):
     nodeList = node.getChildNodes()
     for i in range( nodeList.getLength()):
       childNode = nodeList.item( i )
       yield childNode
       if depthFirst:
         for item in treeEnumeration( childNode ):
           yield item
     if not depthFirst:
       for i in range( nodeList.getLength()):
         childNode = nodeList.item( i )
         for item in treeEnumeration( childNode, False ):
           yield item
   

3. 首先选择深度或宽度，并指示给定节点的深度

   class NodeWrapper():
     def __init__(self, node, depth ):
       self.node = node
       self.depth = depth
     def __repr__( self ):
       return "node %s, depth %d" % (self.node, self.depth)
   
   def treeEnumerationShowDepth( node, depth = 0, depthFirst = True ):
     nodeList = node.getChildNodes()
     for i in range( nodeList.getLength()):
       wrapper = NodeWrapper( nodeList.item( i ), depth )
       yield wrapper
       if depthFirst:
         for item in treeEnumerationShowDepth( wrapper.node, depth + 1 ):
           yield item
     if not depthFirst:
       for i in range( nodeList.getLength()):
         childNode = nodeList.item( i )
         for item in treeEnumerationShowDepth( childNode, depth + 1, False ):
           yield item
   
   from org.w3c.dom import Node
   
   for wrapper in treeEnumerationShowDepth( dom.getDocumentElement(), 0, False ):
     print "%snode: %s" % ( wrapper.depth * "  ", wrapper.node )
   

Answer 2

AFAIK，没有内置的实现。一个非常直接的解决方案是：

import collections

def depth_first_search(node, get_children, depth=0):
    yield node, depth
    for child in get_children(node):
        # In the upcoming Python 3.3, the following can be written as
        # yield from depth_first_search(child, get_children, depth + 1)
        for n, d in depth_first_search(child, get_children, depth + 1):
            yield n, d

def breadth_first_search(node, get_children, depth=0):
    queue = collections.deque([(node, depth)])
    while queue:
        node, depth = queue.popleft()
        queue.extend((n, depth + 1) for n in get_children(node))
        yield node, depth

然后您可以很容易地使用以下方法：

^{pr2}$