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

Question

我实际上正在使用 Jython，并且对 Python 的处理方式还很陌生......

当我使用 javax.swing.tree.DefaultMutableTreeNode 时，我可以简单地使用深度/宽度FirstEnumeration()...

但是，如果我使用 DOM 树(例如，来自 XML)进行操作，则没有这样的等效项...但我突然想到，在 Python/Jython 中一定有一种非常优雅且强大的方法，可以使用递归生成器。

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

令我惊讶的是，我无法仅通过谷歌搜索或在这里查看来找到简单的答案。

Answer 1

据我所知，没有内置实现。一个非常直接的解决方案是:

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