如何将显示层级关系的字典列表转换成树形结构？

Question

如何将显示层级关系的字典列表转换成树形结构？

pythondata-structurestreehierarchical-data

5

我有一个字典列表：

[
    {"node": "root", "children": ["a"]},
    {"node": "a", "children": ["b", "b"]},
    {"node": "b", "children": ["c", "c", "c"]},
    {"node": "c", "children": ["d"]},
]

这里提到的是一棵压缩树。我所指的是这个字典列表代表下面的树：

我应该将这个字典列表转换成哪种数据结构，以便我可以将其展开为一棵树呢？我正在考虑将字典列表展开为类似于：

{"root": [
    {"a": [
        {"b": [
            {"c": [
                {"d": "None"}
              ]
            },
            {"c": [
                {"d": "None"}
              ]
            },
            {"c": [
                {"d": "None"}
              ]
            }
          ]
        },
        {"b": [
            {"c": [
                {"d": "None"}
              ]
            },
            {"c": [
                {"d": "None"}
              ]
            },
            {"c": [
                {"d": "None"}
              ]
            }
          ]
        }
      ]
    }
  ]
}

看起来有些混乱，但本质上是嵌套的节点字典，其值是子节点列表。不太确定如何实现这一点。欢迎提出其他解压此树的想法！

理想情况下，我希望能将其放入类似于treelib这样的树库中，以获取列出叶节点、访问父节点、祖父节点等数据的方法。

- room_temperature

1

我认为只需要一个for循环就可以将其转换，而且你可以不使用任何外部模块来完成。 - furas

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- orlp · Accepted Answer

首先，我会将这个转换：

l = [
    {"node": "root", "children": ["a"]},
    {"node": "a", "children": ["b", "b"]},
    {"node": "b", "children": ["c", "c", "c"]},
    {"node": "c", "children": ["d"]},
]

将其转换为更易处理的格式：

compressed = {e["node"]: e["children"] for e in l}

那么很简单：

def expand(compressed, root):
    children = [expand(compressed, n) for n in compressed.get(root, [])]
    return {root: children or "None"}

在您的例子中：

>>> from pprint import pprint
>>> pprint(expand(compressed, "root"))
{'root': [{'a': [{'b': [{'c': [{'d': 'None'}]},
                        {'c': [{'d': 'None'}]},
                        {'c': [{'d': 'None'}]}]},
                 {'b': [{'c': [{'d': 'None'}]},
                        {'c': [{'d': 'None'}]},
                        {'c': [{'d': 'None'}]}]}]}]}

话虽如此，我建议不要用字符串"None"替换空的子列表，而是将其保持为空列表（因此只需删除上面的or "None"）。