在Python ElementTree中，如何获取树中元素的所有祖先的列表？

Question

我需要“get_ancestors_recursively”函数。
样品运行可以是

>>> dump(tr)
<anc1>
  <anc2>
    <element> </element>
  </anc2>
</anc1>
>>> input_element = tr.getiterator("element")[0]
>>> get_ancestors_recursively(input_element)
['anc1', 'anc2']

有人可以帮我吗？

Answer 1

另一个选项是 LXML，它为内置 ElementTree api 提供了有用的扩展。如果您愿意安装外部模块，它有一个很好的

Element.getparent()

函数，您可以简单地递归调用直到达到

ElementTree.getroot()

。这可能是最快、最优雅的解决方案（因为

lxml.etree module

为指向其父级的元素引入了指针属性，因此不必在整个树中搜索正确的

parent/child

对）。

Answer 2

在最新版本的ElementTree（v1.3或更高版本）中，您可以简单地执行

input_element.find('..')

递归地。但是，Python 附带的 ElementTree 没有此功能，并且我在 Element 类中没有看到任何向上查找的内容。

我相信这意味着你必须以困难的方式做到这一点：通过对元素树的详尽搜索。

def get_ancestors_recursively(e, b):
    "Finds ancestors of b in the element tree e."
    return _get_ancestors_recursively(e.getroot(), b, [])

def _get_ancestors_recursively(s, b, acc):
    "Recursive variant. acc is the built-up list of ancestors so far."
    if s == b:
        return acc
    else:
        for child in s.getchildren():
            newacc = acc[:]
            newacc.append(s)
            res = _get_ancestors_recursively(child, b, newacc)
            if res is not None:
                return res
        return None

由于 DFS，这很慢，并且会产生大量垃圾收集列表，但如果你能处理它应该没问题。

Answer 3

通过大量谷歌搜索找到了这个小宝石（http://elmpowered.skawaii.net/?p=74）

parent = root.findall(".//{0}/..".format(elem.tag))

这里的 root 是树的根节点。 elem 是您通过迭代获得的实际元素对象。

这确实需要您了解根源，这可能意味着更改 XML 解析的设置方式，但这充其量是次要的。

Answer 4

您可以使用树遍历算法。这可以在线性时间内完成任务。

def xml_get_ancestors(element: Element, root: Element):
    ancestors = []

    for node in root.iter():
        if node == element:
            return ancestors

        while len(ancestors) > 0 and node not in ancestors[-1]:
            ancestors.pop()
        
        ancestors.append(node)
    
    return None