如何从特定节点获取树祖先列表？

给定一棵树，其中每个节点可以有N个孩子，但只有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)

你将如何得到"C21Operator"的祖先列表，如结果为["Operator", "FooOperator", "COperator", "C2Operator", "C21Operator"]？

来源

2017-02-27 BPL

你有什么试过，究竟是什么问题呢？ – jonrsharpe

使用这种数据结构我不认为这是真的可能。那么，也许如果你从'tree'开始走每一条可能的路径，然后返回导致你到''C210Operator“'的路径。但是也许用'parent'属性实现你自己的'Node'类，那么只需走父链？ –

+1 @ juanpa.arrivillaga对自定义类的建议，该自定义类实现了更适合此问题的更好的数据结构。 –

鉴于你的数据结构，我想只有蛮力的解决方案是可能的：

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

你或许可以遍历树更智能，如果你知道在哪里期待你的目标。

来源

2017-02-27 23:00:29

你的意见是正确的，最好的方法是建立一个合适的数据结构，让你能够线性地遍历父母。无论如何，你解决了这个问题，我只是想知道;-) – BPL

如何从特定节点获取树祖先列表？

回答

相关问题