使用生成器的Pythonic树枚举器方法

Question

我实际上正在使用 Jython，并且对 Python 的做事方式非常陌生...

当我使用 javax.swing.tree.DefaultMutableTreeNode 时，我可以简单地使用 depth/breadthFirstEnumeration()...

但是如果我正在做的事情DOM 树（例如来自 XML）没有这样的等价物...但我突然想到，在 Python/Jython 中必须有一种非常优雅且强大的方法使用递归生成器来执行此操作。

希望我想要的是实用程序方法的最通用目的，该方法本质上将对您可以扔给它的任何类型的树对象进行枚举......所以您可能必须提供为您提供给定节点的子节点的方法。 ..在 org.w3c.dom.Node 的情况下，这将是 getChildNodes()...那么您可能需要第二个可选参数来指定深度或广度...

令我惊讶的是我还没有找到只需通过谷歌搜索或在此处查找即可获得简单的答案 例子。

Answer 1

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

然后您可以轻松地使用它们，如下所示：

def dom_get_children(node):
    nodeList = node.getNodeList()
    for i in range(nodeList.getLength()):
        yield nodeList.item(i)

for node, depth in depth_first_search(some_dom_element, dom_get_children):
    # do something

Answer 2

谢谢...在我等待的同时，我一直在尝试自己解决这个问题。

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

实际上是您的解决方案看起来，对于由常规 Python 列表组成的树来说效果很好...不幸的是 org.w3c.dom.Node 特别“迟钝”... getChildNodes() 实际上生成一个名为 NodeList 的对象，尽管它显然是一个列表（ Java Array）仍保留某种形式完全密封自省...特别是， dir() 会告诉您其“childNodes”字段的类是“org.apache.xerces.dom.DeferredElementImpl”...我的经验是任何以“Impl”结尾的内容“玩起来不会很有趣......

因此，我显然找不到将方法作为参数传递并调用它的方法......即使有一个更适合的类似Python的类，我目前还不清楚你如何调用您传递的方法作为参数...无论如何...

下面是我的 3 个产品，非常不言自明：1）深度优先 2）选择深度优先或广度优先 3）相同，但提供一些带有深度指示的内容（例如，您可以格式化打印输出）。
不幸的是，使用解决方案#3，我被迫创建一个新类，因为我发现不可能向 Node 对象添加属性……显然，与 Python 相比，Jython 有局限性和“杂质”。我知道有用于处理 XML 等的 python 模块...将在适当的时候研究它。
（当然，Jython 的优点之一是您可以逐渐从 Java 过渡到 Python）。

如果有经验丰富的 Python/Jython 人员有任何意见，我会很感兴趣...

1. 仅限深度优先：

   def heightFirstTreeEnumeration( 节点 ):
     节点列表 = 节点.getChildNodes()
     对于范围内的 i(nodeList.getLength())：
       子节点 = nodeList.item( i )
       产生子节点
       对于 heightFirstTreeEnumeration( childNode ) 中的项目：
         产量项
   

2. 选择深度优先或广度优先

   def treeEnumeration（节点，深度第一= True）：
     节点列表 = 节点.getChildNodes()
     对于范围内的 i(nodeList.getLength())：
       子节点 = nodeList.item( i )
       产生子节点
       如果深度优先：
         对于 treeEnumeration( childNode ) 中的项目：
           产量项
     如果不是深度优先：
       对于范围内的 i(nodeList.getLength())：
         子节点 = nodeList.item( i )
         对于 treeEnumeration( childNode, False ) 中的项目：
           产量项
   

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

   类 NodeWrapper():
     def __init__(自身, 节点, 深度):
       self.node = 节点
       self.深度 = 深度
     def __repr__( 自我 ):
       return "节点 %s, 深度 %d" % (self.node, self.深度)
   
   def treeEnumerationShowDepth( 节点，深度 = 0，深度第一 = True ):
     节点列表 = 节点.getChildNodes()
     对于范围内的 i(nodeList.getLength())：
       包装器= NodeWrapper（nodeList.item（i），深度）
       产量包装器
       如果深度优先：
         对于treeEnumerationShowDepth（wrapper.node，深度+ 1）中的项目：
           产量项
     如果不是深度优先：
       对于范围内的 i(nodeList.getLength())：
         子节点 = nodeList.item( i )
         对于treeEnumerationShowDepth（childNode，深度+ 1，False）中的项目：
           产量项
   
   从 org.w3c.dom 导入节点
   
   对于 treeEnumerationShowDepth( dom.getDocumentElement(), 0, False ) 中的包装器：
     print "%snode: %s" % (wrapper.deep * " ",wrapper.node )