如何在python中递归地创建一个未知大小的嵌套字典?

Question

我有一个对象，每个深度的深度和宽度都是未知的。有点像路径，但它是不同类型的对象。

我的目标是创建一个嵌套的字典来表示这个结构。

它作为层次结构顶部的一个项目开始，我可以使用get_items()函数获取它下面的元素。另外，如果我在对象上调用str()，它将返回对象的名称。

例如:

str(object) = 'top hierarchy'
object.get_items() returns a list ~ [object_level1_part1, object_level1_part2]
str(object_level1_part1) = 'level1_part1'
object_level1_part1.get_items() returns a list ~  [object_level2_part1]
str(object_level2_part2) = 'level2_part1'

等等……在任何级别上都不能保证列表中的任何对象将如何存在。此外，也无法保证每个关卡的深度。但是，深度可能不会大于10。

我想取这个对象&递归地搜索它，以创建一个类似于以下内容的字典:

result_dict = {'top_hierarchy':{'level1_part1':{'level2_part1':{}}, 'level1_part2':{}}}

我遇到的一个挑战是以嵌套的方式不断地向字典中添加内容——我必须指定以前的键。

result_dict['top_hierarchy']['level1_part1']['level2_part1'] = {'level3_part1':{}}

是否有一种方法来创建一个嵌套字典递归与未知的深度和宽度?

Answer 1

正如您的标题所示，您所描述的问题是递归编程的教科书示例:每个子对象代表较小规模的原始挑战。此外，递归程序不关心递归深度或每个级别的宽度(只要Python内置的最大递归深度没有超过，或者您的RAM没有溢出)。因此，应用一个在每个子对象上调用自身的递归函数将是完美的选择。如果我们一般称递归函数为rf，那么解的核心将看起来像rf(child) for child in parent.get_items()。其余的只是拼凑您对输出的需求:您将使用字典将str(parent)映射到它的所有子节点，因此(结构上)类似于{str(parent): [child for child in parent.get_items()]}的东西也将是解决方案的一部分

考虑到所有这些，你的问题的解决方案就变得很简单了:

def unpack(obj):
return {str(o): unpack(o) for o in obj.get_items()}
result_dict = {str(object): unpack(object)}

用一个类来快速测试你的数据结构:

class myObj:
def __init__(self, name, objects=[]):
self.name = name
self.objects = objects

def __str__(self):
return self.name

def get_items(self):
return self.objects
# build recursive structure bottom up
l2p1 = myObj('l2p1')
l1p1 = myObj('l1p1', [l2p1])
l1p2 = myObj('l1p2')
th = myObj('th', [l1p1, l1p2])
# test the unpacking
result_dict = {str(th): unpack(th)}
result_dict
{'th': {'l1p1': {'l2p1': {}}, 'l1p2': {}}}