我正在尝试遍历一棵树,并将某些子树放入特定的数据结构中。我认为一个例子是最好的解释方式:
对于这棵树,我想要根节点及其子节点。然后任何有自己 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]))
请注意,此代码不会生成与图像中相同的树。我觉得生成器也更适合这里,但我的生成器比递归还差。
请您参考如下方法:
让我们首先勾勒出递归算法:
给定一个树节点,返回:
- 节点及其子节点的元组
- 每个 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
根只是一个节点,因此不需要特殊处理。但是如果我误解了数据结构,请修复成员引用。
