從分支列表中重構樹

給出每個子列表標識分支的節點列表列表。目標是編寫一個python程序來從這些分支重建樹。「分支」是指從樹根開始到葉子結束的列表。假設主列表中有這種形式：從分支列表中重構樹

branches = [b_1 , b_2 , b_3 , ... , b_n]

這裏多家分支機構等於葉n的數量。每個分支包含一個節點列表，以便從樹的根到葉：

b_i = [root,n_1,n_2,n_3,...,leaf_i]

的目標是將所有列表合併成捕獲樹的結構的字典。每個節點應該有兩個鍵值對：名稱和子級。 name的值是節點的名稱，而children的值是節點的列表（再次包含名稱和子元素的字典）。沒有這種特殊的結構，這個問題是非常相似的How to turn a list into nested dict in Python

例如，如果列表是：

branches=[[root,n1,l1],[root,n1,l2],[root,n2,l3],[root,n2,l4]]

我們正在尋找這樣一個字典：

treeDict = {'name':root,'children': 
       [ 
       {'name':n1,'children':[ 
        {'name':l1,'children':[]}, 
        {'name':l2,'children':[]}]}, 
       {'name':n2,'children':[ 
        {'name':l3,'children':[]}, 
        {'name':l4,'children':[]}]} 
       ] 
      }

表示這樹：

 root 
    / \ 
    n1  n2 
    /\ /\ 
    l1 l2 l3 l4

來源

2014-11-05 MostafaMV

你一直想這麼遠嗎？ – 2014-11-05 05:43:34

@KlausD。如果我忘記了'child'列表和'name'鍵，這幾乎是相同的：http://stackoverflow.com/questions/7653726/how-to-turn-a-list-into-nested-dict- in-python – MostafaMV 2014-11-05 05:50:49

This i S使用一些遞歸在字典做的一種方式：

import pprint 


def traverse(root, branch): 
    if not branch: 
     return 
    if branch[0] not in root: 
     root[branch[0]] = {} 
    traverse(root[branch[0]], branch[1:]) 


# Or rather, uglify 
def prettify(root): 
    res = [] 
    for k, v in root.iteritems(): 
     d = {} 
     d['name'] = k 
     d['children'] = prettify(v) 
     res.append(d) 
    return res 


d = {} 
branches = [['root','n1','l1'],['root','n1','l2'],['root','n2','l3'],['root','n2','l4']] 
for b in branches: 
    traverse(d, b) 
pprint.pprint(d) 
pprint.pprint(prettify(d))

輸出：

# The compact representation 
{'root': {'n1': {'l1': {}, 'l2': {}}, 'n2': {'l3': {}, 'l4': {}}}} 

# The desired representation 
[{'children': [{'children': [{'children': [], 'name': 'l2'}, 
          {'children': [], 'name': 'l1'}], 
       'name': 'n1'}, 
       {'children': [{'children': [], 'name': 'l4'}, 
          {'children': [], 'name': 'l3'}], 
       'name': 'n2'}], 
    'name': 'root'}]

來源

2014-11-05 06:18:24

這很棒。唯一的問題是它在最後給出了一個列表，我需要列表中的字典。我可以通過列表中的第一個元素逃脫。謝謝 – MostafaMV 2014-11-05 16:36:06

從分支列表中重構樹

回答

相關問題