如何将以下数据结构转换为层次数据结构

Question

有一个数组，数组中的每个元素都是下图中的一个节点，节点之间有一个层次关系，类似于“树”数据结构（只是子节点可以引用回父节点）。你知道吗

#The current data structure is in the following format
[
      {
        'id': 1,
        'name': '开始',
        'next': '2,3,4'
      },
      {
        'id': 2,
        'name': '2号',
        'next': ''
      },
      {
        'id': 3,
        'name': '3号',
        'next': '5,8'
      },
      {
        'id': 4,
        'name': '4号',
        'next': '6'
      },
      {
        'id': 5,
        'name': '5号',
        'next': '7'
      },
      {
        'id': 6,
        'name': '6号',
        'next': ''
      },
      {
        'id': 7,
        'name': '7号',
        'next': '1,3,5'
      },
      {
        'id': 8,
        'name': '8号',
        'next': ''
      }
]

为了确保上述数组中的第一个元素是根节点，请编写一个代码将上述任何类型的数据格式转换为以下层次格式。你知道吗

#to convert
{
    "id":1,
    "name":"开始",
    "backpoints":[ ],
    "childs":[
        {
            "id":2,
            "name":"2号",
            "backpoints":[ ],
            "childs":[ ]
        },
        {
            "id":3,
            "name":"3号",
            "backpoints":[ ],
            "childs":[
                {
                    "id":5,
                    "name":"5号",
                    "backpoints":[ ],
                    "childs":[
                        {
                            "id":7,
                            "name":"7号",
                            "backpoints":[
                                "1",
                                "3",
                                "5"
                            ],
                            "childs":[ ]
                        }
                    ]
                },
                {
                    "id":8,
                    "name":"8号",
                    "backpoints":[ ],
                    "childs":[ ]
                }
            ]
        },
        {
            "id":4,
            "name":"4号",
            "backpoints":[ ],
            "childs":[
                {
                    "id":6,
                    "name":"6号",
                    "backpoints":[ ],
                    "childs":[ ]
                }
            ]
        }
    ]
}

Answer 1

您可以迭代给定的dict列表（在下面的示例中名为nodes），并使用将节点ID映射到节点对象的dict，然后迭代next键中的节点ID，以便在映射dict中预先创建项，作为childs子列表中的项（如果映射dict中还不存在该ID），或将ID附加到backpoints子列表：

mapping = {}
for node in nodes:
    nexts = node.pop('next')
    entry = mapping.setdefault(node['id'], {})
    entry.update({**node, **{'backpoints': [], 'childs': []}})
    if nexts:
        for n in map(int, nexts.split(',')):
            if n in mapping:
                entry['backpoints'].append(str(n))
            else:
                entry['childs'].append(mapping.setdefault(n, {}))

所以mapping[nodes[0]['id']]会返回：

{
    "id": 1,
    "name": "开始",
    "backpoints": [],
    "childs": [
        {
            "id": 2,
            "name": "2号",
            "backpoints": [],
            "childs": []
        },
        {
            "id": 3,
            "name": "3号",
            "backpoints": [],
            "childs": [
                {
                    "id": 5,
                    "name": "5号",
                    "backpoints": [],
                    "childs": [
                        {
                            "id": 7,
                            "name": "7号",
                            "backpoints": [
                                "1",
                                "3",
                                "5"
                            ],
                            "childs": []
                        }
                    ]
                },
                {
                    "id": 8,
                    "name": "8号",
                    "backpoints": [],
                    "childs": []
                }
            ]
        },
        {
            "id": 4,
            "name": "4号",
            "backpoints": [],
            "childs": [
                {
                    "id": 6,
                    "name": "6号",
                    "backpoints": [],
                    "childs": []
                }
            ]
        }
    ]
}

演示：https://repl.it/repls/StrikingFunctionalCrash