生成在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')