python - 递归构建分层 JSON 树？

Question

我有一个父子关系数据库。数据如下所示，但可以以您想要的任何方式呈现(字典、列表列表、JSON 等)。

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

我需要的输出是一个分层的 JSON 树，它将使用 d3 呈现。数据中有离散的子树，我将它们附加到根节点。所以我需要递归地遍历链接，并建立树结构。我能得到的最远的是遍历所有人并附加他们的 child ，但我无法弄清楚如何做更高阶的链接(例如如何将有 child 的人附加到其他人的 child )。这类似于另一个问题 here ，但我没有办法提前知道根节点，所以我无法实现公认的解决方案。

我将从我的示例数据中获取以下树结构。

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

此结构在我的 d3 布局中呈现如下。

Answer 1

要识别根节点，您可以解压缩 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 .