生成在Python

Question

在字典树的所有叶到根的路径我有一个字典树中的“非标准”的形式，如下所示：

tree = {'0': {'A': {'B': {'C': {}}}}, 
      {'D': {'E': {}}, 
        {'F': {}}}} 

叶节点被定义为字典键值对的值是一个空的字典。 我想提取所有叶到根路径，列表的列表，像这样：

paths_ = [['C', 'B', 'A', '0'], 
      ['E', 'D', '0'], 
      ['F', 'D', '0']] 

的路径可以颠倒过，如果这是有帮助的。

paths_ = [['0', 'A', 'B', 'C'], 
      ['0', 'D', 'E'], 
      ['0', 'D', 'F']] 

我知道我必须做递归，我需要每个路径的累加器列表。如果函数产生了路径列表，它也会很好。我到目前为止是这样的：

def paths(node, subtree, acc=[]): 
    if not subtree: 
     yield [node]+acc 
    for n, s in subtree.items(): 
     yield paths(n, s, acc) 

它并没有真正做我想做什么：

paths_ = list(paths('0', tree['0'])) 

理想这应该返回列表的名单。任何帮助都感激不尽。

Answer 1

假设你真正用于tree以下结构：

tree = {'0': {'A': {'B': {'C': {}}}, 
       'D': {'E': {}, 
        'F': {}}}} 

下面是一个类似paths()函数应该做你想要什么：

def paths(tree, cur=()): 
    if not tree: 
     yield cur 
    else: 
     for n, s in tree.items(): 
      for path in paths(s, cur+(n,)): 
       yield path 

结果：

>>> list(paths(tree)) 
[('0', 'A', 'B', 'C'), ('0', 'D', 'E'), ('0', 'D', 'F')] 

请注意，我使用了一个元组作为缺省参数ins一个清单的tead，这是因为mutable default arguments can get you into trouble。

Answer 2

假设树结构是这种格式： {'0'：{'A'：{}，'B'：{}}} 然后像这样的事情应该做的伎俩。

def paths(nodeId, children, ancestors, allPaths): 
    ancestors.append(nodeId) 
    if len(children) == 0: 
     allPaths.append(ancestors) 
    else: 
     for childId in children: 
      paths(childId, children[childId], ancestors[:], allPaths) 

allPaths = [] 
paths('0', tree['0'], [], allPaths) 

类似的东西应该工作。通常我会先尝试一下，但现在我在iPad上。如果它不起作用，它应该给你一些想法。

Answer 3

您可以使用类似于此的内容，与所选答案类似。

import collections 

def iter_paths(tree, parent_path=()): 
    for path, node in tree.iteritems(): 
     current_path = parent_path + (path,) 
     if isinstance(node, collections.Mapping): 
      for inner_path in iter_paths(node, current_path): 
       yield inner_path 
     else: 
      yield current_path 

对于以下字典：

tree = {'A':1, 'B':{'B1':1, 'B2':2}, 'C':{'C1':{'C11':1, 'C12':2},'C2':{'C21':1, 'C22':2}}}

输出应（产量顺序可能会有所不同）：

('A',) 
('C', 'C2', 'C22') 
('C', 'C2', 'C21') 
('C', 'C1', 'C12') 
('C', 'C1', 'C11') 
('B', 'B1') 
('B', 'B2')