2

伙计们，

我有任意字典，可能有任意数量的其他字典和数组的嵌套，例如：

{
    "a": {
        "b": "1",
        "c": [
            {
                "d": "2"
            },
            {
                "d": {
                    "e": "3",
                    "f": "4"
                }
            }
        ]
    }
}

我想把它很好地表示为一棵树，为了做到这一点，我想将它转换为一个结构，例如：

{
    "name": "a",
    "children": [
        {
            "name": "b",
            "value": "1"
        },
        {
            "name": "c",
            "children": [
                {
                    "name": "d",
                    "value": "2"
                },
                {
                    "name": "d",
                    "children": [
                        {
                            "name": "e",
                            "value": "3"
                        },
                        {
                            "name": "f",
                            "value": "4"
                        }
                    ]
                }
            ]
        }
    ]
}

我认为这样做需要类似地处理子字典和子数组。但是，我很难想出一种方法来进行这种转变。我曾尝试使用递归，也尝试使用包含“名称”、“值”和“孩子”的键/值的节点类，但我很难解析任意深度的输入创建此常规节点/树表示。

这看起来像人们以前做过的事情吗？非常感谢您的意见。

4

1 回答 1

4

您正确地将其识别为树状数据结构，并且转换它是非常明智的，因为原始表示已被完全破坏。

既然你知道你有一棵树，你需要问自己它的节点是什么。在您的情况下，节点是：

  1. 一片叶子，它有一个名字和一个值
  2. 一个内部节点，它有一个名字和孩子

问题在于第二种类型有两种不同的表示形式：

  1. 一双("<name>", { "<child1>" : ..., "<child2>" })
  2. 一双("<name>", [{"<child1>" : ... }, { "<child2>": ... }])

您的示例没有显示它，但也许以下也是可能的：

("<name>", [{"<child1>" : ... }, { "<child2>": ..., "<child3>": ... }])

递归确实是解决这个问题的好方法。边缘情况很清楚，它是叶节点。您只需要先检查其他两种情况：

def transform_node(name, val):
    if isinstance(val, list):
        val = ("children", [transform_node(k,v) for x in val for k, v in x.items()])
    elif isinstance(val, dict):
        val = ("children", [transform_node(*kv) for kv in val.items()])
    else:
        val = ("value", val)
    return dict([("name", name), val])

现在你得到：

>>> transform_node("a", 3)
{'name': 'a', 'value': 3}
>>> transform_node("a", { "c1" : 3, "c2" : 4 })
{'name': 'a', 'children': [{'name': 'c2', 'value': 4}, {'name': 'c1', 'value': 3}]}
>>> transform_node("a", [{ "c1" : 3 }, { "c2" : 4, "c3": 5 }])
{'name': 'a', 'children': [{'name': 'c1', 'value': 3}, {'name': 'c3', 'value': 5}, {'name': 'c2', 'value': 4}]}

完美的！现在你可以这样做：

>>> tree = { "a": { "b": 1 }}
>>> transform_node("root", tree)
{'name': 'root', 'children': [{'name': 'a', 'children': [{'name': 'b', 'value': 1}]}]}

当然，如果您希望“a”成为根，那么您可以提取根的第一个孩子。

也就是说，最好将其表示为使用类的真实数据类型，而不是完全无类型的字典。

于 2013-02-06T16:51:49.557 回答