遞歸構建分層JSON樹？

我有一個父子連接的數據庫。數據如下所示，但可以以任何您想要的方式顯示（字典，列表，JSON等）。遞歸構建分層JSON樹？

links=(("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl"))

我需要的輸出是一個層次結構的JSON樹，它將用d3進行渲染。數據中有離散的子樹，我將附加到根節點。所以我需要遞歸地通過鏈接，並建立樹結構。我能得到的最遠是遍歷所有的人並追加他們的孩子，但我無法想象做更高級的鏈接（例如，如何將一個人的子女追加到別人的孩子身上）。這與另一個問題here類似，但我無法預先知道根節點，所以我無法實現可接受的解決方案。

我將從我的示例數據中查找以下樹形結構。

{ 
"name":"Root", 
"children":[ 
    { 
    "name":"Tom", 
    "children":[ 
     { 
     "name":"Dick", 
     "children":[ 
      {"name":"Harry"} 
     ] 
     }, 
     { 
      "name":"Larry"} 
    ] 
    }, 
    { 
    "name":"Bob", 
    "children":[ 
     { 
     "name":"Leroy" 
     }, 
     { 
     "name":"Earl" 
     } 
    ] 
    } 
] 
}

此結構在我的d3佈局中呈現如下所示。 Rendered image

來源

2013-08-02 Andrew Barr

那裏沒有問題。還有，你還嘗試過什麼嗎？也許你應該？ – netcoder

找出根本的筆記，你可以解壓縮links，尋找父母誰不兒：

parents, children = zip(*links) 
root_nodes = {x for x in parents if x not in children}

那麼你可以申請遞歸方法：

import json 

links = [("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Bob","Leroy"),("Bob","Earl")] 
parents, children = zip(*links) 
root_nodes = {x for x in parents if x not in children} 
for node in root_nodes: 
    links.append(('Root', node)) 

def get_nodes(node): 
    d = {} 
    d['name'] = node 
    children = get_children(node) 
    if children: 
     d['children'] = [get_nodes(child) for child in children] 
    return d 

def get_children(node): 
    return [x[1] for x in links if x[0] == node] 

tree = get_nodes('Root') 
print json.dumps(tree, indent=4)

我用一組獲得根節點，但如果順序很重要，您可以使用列表和remove the duplicates。

來源

2013-08-02 21:09:31

嘗試follwing代碼：

import json 

links = (("Tom","Dick"),("Dick","Harry"),("Tom","Larry"),("Tom","Hurbert"),("Tom","Neil"),("Bob","Leroy"),("Bob","Earl"),("Tom","Reginald")) 

name_to_node = {} 
root = {'name': 'Root', 'children': []} 
for parent, child in links: 
    parent_node = name_to_node.get(parent) 
    if not parent_node: 
     name_to_node[parent] = parent_node = {'name': parent} 
     root['children'].append(parent_node) 
    name_to_node[child] = child_node = {'name': child} 
    parent_node.setdefault('children', []).append(child_node) 

print json.dumps(root, indent=4)

來源

2013-08-02 20:08:37 falsetru

有點皺紋....你的代碼不能像預期的那樣運行更多的鏈接：例如，當我用這些鏈接嘗試它時，Tom會多次出現！鏈接=（（「湯姆」，「迪克」），（「迪克」，「哈利」），（「湯姆」，「拉里」），（「湯姆」，「Hurbert」），（「湯姆」，「尼爾「），（」Bob「，」Leroy「），（」Bob「，」Earl「），（」Tom「，」Reginald「）） –

@AndrewBarr，我更新了代碼。 – falsetru

如果您希望將數據作爲HTML層次格式化/ JS本身，看看：

Generate (multilevel) flare.json data format from flat json

萬一你有大量的數據，Web轉換將會更快，因爲它使用了reduce功能，而Python缺乏函數式編程。

順便說一句：我也在研究相同的主題，即在d3.js中生成可摺疊的樹結構。如果你想工作，我的電子郵件是：[email protected]。

來源

2013-08-02 20:19:18

遞歸構建分層JSON樹？

回答

相關問題