특정 노드에서 트리 선조 목록을 얻으려면 어떻게해야합니까?

Question

각 노드가 N 개의 자식을 가질 수 있지만 하나의 부모 만 가질 수있는 트리가 주어집니다. 한 노드의 조상을 얻으려면 어떻게해야합니까? 이러한 결과였다 ["Operator", "FooOperator", "COperator", "C2Operator", "C21Operator"]로

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

가 어떻게 "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]: 

당신은 아마 더 지능적으로 트리를 탐색 할 수 있습니다.