2

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

在此处输入图像描述

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

[
    (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]))

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

4

4 回答 4

1

让我们先画出递归算法：

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

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

这就是它所需要的，所以让我们将其转换为伪代码，嗯，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

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

于 2016-03-17T17:18:44.243 回答
0 
def _subtrees(root):

   subtrees=[]
   queue = []
   queue.append(root)
   while(len(queue)=!0):
      root=queue[0]
      children = list(root.children)
      if (children):
         queue = queue + list(root.children)
         subtrees.append((root.dep, [child.dep for child in children]))
      queue=queue.pop(0)

   return subtrees
于 2016-03-17T14:08:50.133 回答
0

假设您想知道这一点是为了专门使用 spaCy，为什么不只是：

[(word, list(word.children)) for word in sent]

Doc 对象允许您按顺序遍历所有节点。所以你不需要在这里递归地遍历树——只需迭代。

于 2016-03-17T18:07:01.760 回答
0

我还不能完全发表评论，但是如果您像这样修改@syllogism_ 的响应，它将省略所有没有任何子节点的节点。

[(word, list(word.children)) for word in s if bool(list(word.children))]
于 2019-08-04T16:32:15.900 回答