Comment puis-je obtenir une liste d'ancêtres-arbres à partir d'un nœud particulier?

Question

Étant donné un arbre où chaque nœud peut avoir N enfants, mais seulement 1 parent. Comment puis-je obtenir les ancêtres d'un noeud? Par exemple, disons que je suis cet arbre:

# Operator 
# ... FooOperator 
# ...... BOperator 
# ......... B1Operator 
# ............ B11Operator 
# ...... AOperator 
# ......... A2Operator 
# ......... A1Operator 
# ......... A3Operator 
# ...... COperator 
# ......... C1Operator 
# ......... C2Operator 
# ............ C21Operator 

tree = { 
    'children': [{ 
     'children': [{ 
      'children': [{ 
       'children': [{ 
        'children': [], 
        'class': 'B11Operator', 
        'parent': 'B1Operator' 
       }], 
       'class': 'B1Operator', 
       'parent': 'BOperator' 
      }], 
      'class': 'BOperator', 
      'parent': 'FooOperator' 
     },{ 
     'children': [{ 
      'children': [], 
      'class': 'A2Operator', 
      'parent': 'AOperator' 
     },{ 
      'children': [], 
      'class': 'A1Operator', 
      'parent': 'AOperator' 
     },{ 
      'children': [], 
      'class': 'A3Operator', 
      'parent': 'AOperator' 
     }], 
     'class': 'AOperator', 
     'parent': 'FooOperator'},{ 
     'children': [{ 
      'children': [], 
      'class': 'C1Operator', 
      'parent': 'COperator' 
     },{ 
      'children': [{ 
       'children': [], 
       'class': 'C21Operator', 
       'parent': 'C2Operator' 
      }], 
      'class': 'C2Operator', 
      'parent': 'COperator' 
     }], 
     'class': 'COperator', 
     'parent': 'FooOperator' 
    }], 
    'class': 'FooOperator', 
    'parent': 'Operator' 
    }], 
    'class': 'Operator', 
    'parent': None 
} 

def display_tree(node, indent=0): 
    print('.' * indent, node['class']) 
    indent += 3 
    for child in node['children']: 
     display_tree(child, indent) 

display_tree(tree) 

Comment voulez-vous obtenir une liste ancêtres de "C21Operator" tels que le résultat était ["Operator", "FooOperator", "COperator", "C2Operator", "C21Operator"]?

Answer 1

Compte tenu de votre structure de données, je pense qu'une solution force brute est possible:

In [6]: def path_to_child(tree, target, acc=None): 
    ...:  if acc is None: 
    ...:   acc = [] 
    ...:  if tree['class'] == target: 
    ...:   return acc 
    ...:  for child in tree['children']: 
    ...:   found = path_to_child(child, target, acc + [tree['class']]) 
    ...:   if found is not None: 
    ...:    return found 
    ...: 

In [7]: path_to_child(tree, 'C21Operator') 
Out[7]: ['Operator', 'FooOperator', 'COperator', 'C2Operator'] 

In [8]: 

Vous pouvez peut-être traverser l'arbre de façon plus intelligente si vous savez où attendre votre cible.