如何将显示层次关系的字典列表转换为树？

Question

我有这个听写清单：

[
    {"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"}
              ]
            }
          ]
        }
      ]
    }
  ]
}

看起来很乱，但本质上是 children 列表中节点的嵌套字典。不太确定如何实现这一目标。欢迎任何其他解压缩此树的想法！

理想情况下，我可以将其放入 treelib 等树库中，以获取列出叶节点、访问 parents、grandparents 等数据的方法.

Answer 1

首先，我将转换为：

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"）。

如何将显示层次关系的字典列表转换为树？

How can I convert a list of dicts showing hierarchical relationships into a tree?

python

tree

hierarchical-data

data-structures