Skip to main content
 首页 » 编程设计

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

2025年04月02日17sharpest

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

对于这棵树,我想要根节点及其子节点。然后任何有自己 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])) 

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

请您参考如下方法:

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

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

    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 

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