Обход дерева и получение соседних дочерних узлов в Python

Question

Я пытаюсь пересечь дерево и получить определенные поддеревья в конкретную структуру данных. Я думаю, что пример это лучший способ объяснить это:

Для этого дерева, я хочу корневой узел и его дети. Тогда все дети, у которых есть свои дети, должны проходить одинаково, и так далее. Так для приведенного выше дерева, мы в конечном итоге со структурой данных, такие как:

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

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 

Answer 2

первый эскиз Давайте рекурсивный алгоритм:

• Учитывая узел дерева, возвращение:

  1. Кортеж узла с его детьми
  2. поддеревьев каждого ребенка ,

Это все, что нужно, так что давайте преобразуем его в псевдокоде, ЭУ, питон:

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 

Корень всего узла, так что не нужно специальное лечение. Но, пожалуйста, исправьте ссылки на членство, если я неправильно понял структуру данных.

Answer 3

Предполагая, что вы хотите знать об этом для использования Spacy конкретно, почему не просто:

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

Объект Doc позволяет перебрать все узлы в порядке. Поэтому вам не нужно рекурсивно ходить по дереву - просто итерации.