python - 树遍历并在Python中获取相邻的子节点

Question

我正在尝试遍历一棵树，并将某些子树放入特定的数据结构中。我认为一个例子是最好的解释方式:

对于这棵树，我想要根节点及其子节点。然后任何有自己 child 的 child 都应该以同样的方式遍历，等等。所以对于上面的树，我们最终会得到一个数据结构，例如:

[
    (a, [b, c]),
    (c, [d, e, f]),
    (f, [g, h]),
]

到目前为止我有一些代码可以生成这个，但是有一个问题是它停止得太早了(或者看起来就是这样):

from spacy.en import English


def _subtrees(sent, root=None, subtrees=[]):
    if not root:
        root = sent.root

    children = list(root.children)
    if not children:
        return subtrees

    subtrees.append((root, [child for child in children]))
    for child in children:
        return _subtrees(sent, child, subtrees)


nlp = English()
doc = nlp('they showed us an example')
print(_subtrees(list(doc.sents)[0]))

请注意，此代码不会生成与图像中相同的树。我觉得生成器也更适合这里，但我的生成器比递归还差。

Answer 1

让我们首先勾勒出递归算法:

• 给定一个树节点，返回:

  1. 节点及其子节点的元组
  2. 每个 child 的子树。

这就是它所需要的，所以让我们把它转换成伪代码，嗯，python:

def subtrees(node):
    if not node.children:
        return []

    result = [ (node.dep, list(node.children)) ]
    for child in node.children:
        result.extend(subtrees(child))

    return result

根只是一个节点，因此不需要特殊处理。但是如果我误解了数据结构，请修复成员引用。