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

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

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

理想情况下，我可以将其放入一些树库中，例如treelib获取列出叶节点、访问父母、祖父母等数据的方法。

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"}

在你的例子中：

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

也就是说，我建议不要用字符串替换空子列表"None"，而只需将其设置为空列表（因此只需删除or "None"上面的内容）。