如何在查字典的基础上创建深度未知的多维字典？（Python）

Question

我有一个“查找”字典，它表示节点：

# Original "lookup" dictionary

{
  0 : [1, 2],
  2 : [3],
  4 : [5]
}

……我希望在此基础上创建一本新词典，如下所示：

# New multidimensional dictionary

{
  0 : {
        1 : {},
        2 : {
              3 : {}
            }
      }
  4 : {
        5 : {}
      }
  }
}

如何使用递归实现这一点？你知道吗

原始“lookup”字典的键表示父节点，值表示一个或多个节点树中的子节点。你知道吗

原始“lookup”字典包含未知数量的键/值，深度未知。你知道吗

Answer 1

我将假设这个数据结构代表一棵树，节点被编号，这样父节点的索引总是比子节点的索引低。然后，您可以在助手索引（nodeindex）的帮助下构建所需的树，该索引允许您在一个步骤中查找每个节点：

tree = dict()
nodeindex = dict()
for node, vals in sorted(lookup.items()):
    if node not in nodeindex:
        nodeindex[node] = tree[node] = dict()  # insert at the top level

    position = nodeindex[node]
    for val in vals:
        if val in nodeindex:
            raise ValueError("Value (%d, %d) would create a loop!" %(node, val))
        nodeindex[val] = position[val] = dict()

如果非树图是合法的，则循环的最后一部分会将找到的值赋给position[val]，而不是引发错误：

    ...
    for val in vals:
        if val in nodeindex:
            position[val] = nodeindex[val]
        else:
            nodeindex[val] = position[val] = dict()