特定のノードからツリー祖先のリストを取得するにはどうすればよいですか？

Question

各ノードがN個の子を持つことができるが、親は1つしかないツリーが与えられる。どのようにして1つのノードの祖先を得ることができますか？たとえば、のは、私はこの木を得たとしましょう：

# 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) 

どのようにして、このような結果は["Operator", "FooOperator", "COperator", "C2Operator", "C21Operator"]たよう"C21Operator"から先祖リストを取得するのでしょうか？あなたのデータ構造を考えると

Answer 1

は、私が唯一のブルートフォースソリューションが可能だと思う：

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]: 

あなたはどこの目標を期待するの知っている場合は、おそらくもっとインテリジェントにツリーを走査することができます。