如何在 python 中使用 BFS 创建树？

Question

所以我在 JSON 中有一个像这样的扁平树，作为对象数组：

[{
    aid: "id3",
    data: ["id1", "id2"]
},

{
    aid: "id1",
    data: ["id3", "id2"]
},

{
    aid: "id2",
    nested_data: {aid: "id4", atype: "nested", data: ["id1", "id3"]},
    data: []
}]

我想收集那棵树并通过递归循环将 id 解析为数据，如下所示（假设我们从 "id3" 开始）：

{
   "aid":"id3",
   "payload":"1",
   "data":[
      {
         "id1":{
            "aid":"id1",
            "data":[
               {
                  "id3":null
               },
               {
                  "id2":null
               }
            ]
         }
      },
      {
         "id2":{
            "aid":"id2",
            "nested_data":{
               "aid":"id4",
               "atype":"nested",
               "data":[
                  {
                     "id1":null
                  },
                  {
                     "id3":null
                  }
               ]
            },
            "data":[
               
            ]
         }
      }
   ]
}

以便我们进行广度优先搜索，并在第一个入口将某些字段解析为 "value": "object with that field" 和 "value": Null

如何在python3中做这样的事情？

Answer 1

除了您的结构在语法方面存在的所有问题（标识符必须在引号内等）之外，下面的代码将为您提供所需的答案。

但是你应该仔细考虑你在做什么，并考虑以下因素：

使用您提供的平面结构中表达的关系将意味着您将进行无休止的递归，因为您的项目包含其他项目，而其他项目又包含第一个项目（如 id3 包括 id1，其中又包括 id3。因此，您必须定义停止条件，或者确保这不会发生在您的平面结构中。
你的初始平面结构最好是字典的形式，而不是 {id, data} 对的列表。这就是为什么下面的代码做的第一件事就是转换它。
你最终想要的结构在包含的信息方面包含很多冗余。考虑简化它。
最后，您没有提及“nested_data”节点以及应如何处理它们。我只是假设如果存在，则需要进一步扩展。

请考虑尝试在您的问题中提供一些背景信息，一些真实的数据示例（我相信提供的数据不是真实数据，因此存在不一致和冗余），并尝试自己做出努力；这是唯一的学习方式。

from pprint import pprint

def reformat_flat_info(flat):
    reformatted = {}
    for o in flat:
        key = o["aid"]
        del o["aid"]
        reformatted[key] = o
    return reformatted

def expand_data(aid, flat, lvl=0):
    obj = flat[aid]
    if obj is None: return {aid: obj}

    obj.update({"aid": aid})
    if lvl > 1:
        return {aid: None}

    for nid,id in enumerate(obj["data"]):
        obj["data"][nid] = expand_data(id, flat, lvl=lvl+1)

    if "nested_data" in obj:
        for nid,id in enumerate(obj["nested_data"]["data"]):
            obj["nested_data"]["data"][nid] = expand_data(id, flat, lvl=lvl+1)

    return {aid: obj}

# Provide the flat information structure
flat_info = [
    {
        "aid": "id3",
        "data": ["id1", "id2"]
    }, {
        "aid": "id1",
        "data": ["id3", "id2"]
    }, {
        "aid": "id2",
        "nested_data": {"aid": "id4", "atype": "nested", "data": ["id1", "id3"]},
        "data": []
    }
]
pprint(flat_info)
print('-'*80)

# Reformat the flat information structure
new_flat_info = reformat_flat_info(flat=flat_info)
pprint(new_flat_info)
print('-'*80)

# Generate the result
starting_id = "id3"
result = expand_data(aid=starting_id, flat=new_flat_info)
pprint(result)

如何在 python 中使用 BFS 创建树？

How to create a tree using BFS in python?

python

tree

json

breadth-first-search