python - 将 JSON 对象排序到层次结构中

Question

我需要将一个 JSON 数组整理成一个层次结构，这里是我的 JSON 文件，它从未排序，但遵循结构：

{
  "name":"Folder 2",
  "id":"zRDg",
  "parent":"OY00",
  "type":"folder"
},
{
  "name":"Folder 1",
  "id":"OY00",
  "type":"folder"
},
{
  "name":"Folder 3",
  "id":"ZDE1",
  "type":"folder"
},
{
  "name":"DX00025.jpg",
  "id":"9Xdd",
  "parent":"OY00",
  "type":"jpeg"
}

进入这个JSON文件，结构是这样的：

{
  "name":"Folder 1",
  "id":"OY00",
  "type":"folder",
  "children": [{
    "name":"Folder 2",
    "id":"zRDg",
    "type":"folder"
    },
    {
    "name":"DX00025.jpg",
    "id":"9Xdd",
    "type":"jpeg"
  }]
},
{
    "name":"Folder 3",
    "id":"ZDE1",
    "type":"folder"
}

我无法弄清楚，因为我是 python 新手，我的开始（错误）：

for index,item in result:
    if item['parent']:
        for item2 in result:
            if item2['id'] == item['parent']:
                item['children'] = item2
                brake

这没关系，但问题是它不正确python，folder1/folder2/folder3/ 不会为此工作，我需要一个递归函数。我还应该包括这种结构更改，它可以是带有文件夹的文件夹和带有文件夹/文件夹的文件的任意组合。

score 3 · Accepted Answer

使用 Python networkx库之类的东西怎么样？

import json
#networkx is a library for working with networks and trees
import networkx as nx
#The json_graph routines print out JSONic representations of graphs and trees
#http://networkx.github.com/documentation/latest/reference/readwrite.json_graph.html
from networkx.readwrite import json_graph

dd='[{ "name":"Folder 2", "id":"zRDg", "parent":"OY00", "type":"folder"},{ "name":"Folder 1", "id":"OY00", "type":"folder"},{"name":"Folder 3", "id":"ZDE1", "type":"folder"},{ "name":"DX00025.jpg", "id":"9Xdd", "parent":"OY00", "type":"jpeg"}]'
d=json.loads(dd)

#A tree is a directed graph - create one with a dummy root
DG=nx.DiGraph()
DG.add_node('root')

#Construct the tree as a directed graph and annotate the nodes with attributes
#Edges go from parent to child
for e in d:
  DG.add_node(e['id'],name=e['name'],type=e['type'])
  #If there's a parent, use it...
  if 'parent' in e: DG.add_edge(e['parent'],e['id'])
  #else create a dummy parent from the dummy root
  else: DG.add_edge('root',e['id'])

#Get the tree as JSON
data = json_graph.tree_data(DG,root='root')
#and dump the data from the dummy root's children down...
json.dumps(data['children'])

'''
'[{"children": [{"type": "folder", "name": "Folder 2", "id": "zRDg"}, {"type": "jpeg", "name": "DX00025.jpg", "id": "9Xdd"}], "type": "folder", "name": "Folder 1", "id": "OY00"}, {"type": "folder", "name": "Folder 3", "id": "ZDE1"}]'
'''

score 3 · Accepted Answer

myJson = [
    {
      "name":"Folder 2",
      "id":"zRDg",
      "parent":"OY00",
      "type":"folder"
    },
    {
      "name":"Folder 1",
      "id":"OY00",
      "type":"folder"
    },
    {
      "name":"Folder 3",
      "id":"ZDE1",
      "type":"folder"
    },
    {
      "name":"DX00025.jpg",
      "id":"9Xdd",
      "parent":"OY00",
      "type":"jpeg"
    }
]

#this creates a dictionary that maps id names to JSON items.
#ex. itemsKeyedById["9Xdd"] gives the jpg item with id "9Xdd"
itemsKeyedById = {i["id"]: i for i in myJson}

#iterate through each item in the `myJson` list.
for item in myJson:
    #does the item have a parent?
    if "parent" in item:
        #get the parent item
        parent = itemsKeyedById[item["parent"]]
        #if the parent item doesn't have a "children" member, 
        #we must create one.
        if "children" not in parent:
            parent["children"] = []
        #add the item to its parent's "children" list.
        parent["children"].append(item)

#filter out any item that has a parent.
#They don't need to appear at the top level, 
#since they will appear underneath another item elsewhere.
topLevelItems = [item for item in myJson if "parent" not in item]
print topLevelItems

输出（我添加了缩进）：

[
    {
        'name': 'Folder 1', 
        'id': 'OY00',
        'type': 'folder',
        'children': [
            {
                'name': 'Folder 2', 
                'id': 'zRDg',
                'parent': 'OY00', 
                'type': 'folder'
            }, 
            {
                'name': 'DX00025.jpg', 
                'id': '9Xdd',
                'parent': 'OY00', 
                'type': 'jpeg' 
            }
        ]
    }, 
    {
        'name': 'Folder 3', 
        'id': 'ZDE1',
        'type': 'folder'
    }
 ]

它也适用于嵌套超过一层的项目。示例输入：

myJson = [
    {
        "name":"TopLevel folder",
        "id":"0",
        "type":"folder",
    },
    {
        "name":"MidLevel folder",
        "id":"1",
        "type":"folder",
        "parent":"0"
    },
    {
        "name":"Bottom Level folder",
        "id":"2",
        "type":"folder",
        "parent":"1"
    },
    {
        "name":"Vacation Picture",
        "id":"3",
        "type":"jpg",
        "parent":"2"
    },
]

输出：

[
    {
        'type': 'folder', 
        'name': 'TopLevel folder', 
        'id': '0',
        'children': [
            {
                'type': 'folder', 
                'name': 'MidLevel folder', 
                'parent': '0', 
                'id': '1',
                'children': [
                    {
                        'type': 'folder', 
                        'name': 'Bottom Level folder', 
                        'parent': '1', 
                        'id': '2',
                        'children': [
                            {
                                'type': 'jpg', 
                                'name': 'Vacation Picture', 
                                'parent': '2', 
                                'id': '3'
                            }
                        ] 
                    }
                ]
            }
        ]
    }
]

score 2 · Accepted Answer

我对这种情况的解决方案是这样的：

data = INPUT_LIST

class Item:
    def __init__(self, _id, name, type, parent):
        self._id = _id
        self.name = name
        self.type = type
        self.parent = parent
        self.children = []

    def get_dict(self):
        return {
            'id': self._id,
            'name': self.name,
            'type': self.type,
            'children': [child.get_dict() for child in self.children]
        }


lookup = dict((item['id'], Item(item['id'], item['name'], item['type'], item['parent'] if 'parent' in item else None)) for item in data)

root = []

for _id, item in lookup.items():
    if not item.parent:
        root.append(item)
    else:
        lookup[item.parent].children.append(item)

dict_result = [item.get_dict() for item in root]

score 2 · Accepted Answer

您在这里拥有的是一个图（可能只是一棵树），其中节点之间的连接由一个parent键表示。这称为邻接表。

您想通过作为children其他节点列表的键生成一个树结构，其中包含到其他节点的链接。

要将邻接表转换为树，首先需要有一种方法通过其 id 检索节点，因此第一步是创建每个节点的字典，以 id 为键。

然后你必须再次浏览列表并将孩子添加到他们的父母中。

最后，制作一个没有父节点（根节点）的节点列表。

请注意，您根本不需要递归算法。

我们可以结合其中一些步骤来避免多次遍历列表。下面的代码：

def nest_list(L):
    """Modify list of associative dicts into a graph and return roots of graph

    Association is via a 'parent' key indicating a corresponding 'id'.
    Items in the list *will be modified*.
    Children will be placed in a list for a 'children' key
    Items without children will have no 'children' key
    'parent' keys will be removed.

    Returned list is the full list of items which are not children of
    any other items.
    """
    idx = {}
    children = []
    root = []
    # first pass: index items by id
    # if the item has no parents, put it in the 'root' list
    # otherwise add it to the 'children' list which we will
    # process in a second pass
    for item in L:
        idx[item['id']] = item
        if 'parent' in item:
            children.append(item)
        else:
            root.append(item)

    # second pass: find the parents of our children
    for child in children:
        parent = idx[child['parent']]
        del child['parent']
        try:
            # retrieve the list of children for this
            # parent
            childlist = parent['children']
        except KeyError:
            # this item has received no children so far
            # so we need to make a 'children' key and list
            # for it.
            parent['children'] = childlist = []
        # append this child to the parent's list of children
        childlist.append(child)

    #all done: return new root list
    return root

代码在行动：

oldlist = [{
  "name":"Folder 2",
  "id":"zRDg",
  "parent":"OY00",
  "type":"folder"
},
{
  "name":"Folder 1",
  "id":"OY00",
  "type":"folder"
},
{
  "name":"Folder 3",
  "id":"ZDE1",
  "type":"folder"
},
{
  "name":"DX00025.jpg",
  "id":"9Xdd",
  "parent":"OY00",
  "type":"jpeg"
}]

expected = [{
  "name":"Folder 1",
  "id":"OY00",
  "type":"folder",
  "children": [{
    "name":"Folder 2",
    "id":"zRDg",
    "type":"folder"
    },
    {
    "name":"DX00025.jpg",
    "id":"9Xdd",
    "type":"jpeg"
  }]
},
{
    "name":"Folder 3",
    "id":"ZDE1",
    "type":"folder"
}]


from pprint import pprint
newlist = nest_list(oldlist)
pprint(newlist)
assert newlist == expected

python - 将 JSON 对象排序到层次结构中

4 回答 4

Related

Reference