如何基於查找字典創建未知深度的多維字典？ （蟒蛇）

Question

我有這樣的「查找」的字典，它代表的節點：

# Original "lookup" dictionary 

{ 
    0 : [1, 2], 
    2 : [3], 
    4 : [5] 
} 

...我希望創建一個基於這個新的字典，就像這樣：

# New multidimensional dictionary 

{ 
    0 : { 
     1 : {}, 
     2 : { 
       3 : {} 
      } 
     } 
    4 : { 
     5 : {} 
     } 
    } 
} 

如何這可以通過遞歸來實現嗎？

原來的「查找」字典的鍵表示父節點和值代表孩子在一個或多個節點樹的節點。

原始「查找」字典包含未知數量的鍵/值，深度未知。

Answer 1

我會假設這個數據結構代表一棵樹，並且節點被編號，以便父節點總是比子節點索引更低。然後，你可以建立你想不遞歸樹，有一個輔助指標（nodeindex），可以讓你找到一個步驟中的各節點的幫助：

tree = dict() 
nodeindex = dict() 
for node, vals in sorted(lookup.items()): 
    if node not in nodeindex: 
     nodeindex[node] = tree[node] = dict() # insert at the top level 

    position = nodeindex[node] 
    for val in vals: 
     if val in nodeindex: 
      raise ValueError("Value (%d, %d) would create a loop!" %(node, val)) 
     nodeindex[val] = position[val] = dict() 

如果非樹圖是合法的，最後的該環路的一部分將分配給position[val]，而不是拋出一個錯誤它找到值，：

... 
    for val in vals: 
     if val in nodeindex: 
      position[val] = nodeindex[val] 
     else: 
      nodeindex[val] = position[val] = dict()