将字典列表转换为层次结构

我发现自己需要一些帮助，我试图将字典列表（您会看到）转换为某种树/层次结构。我需要处理的是深度参数列表的当前顺序（这是正确的）。将字典列表转换为层次结构

functions = [ 
    {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'}, 
    {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'}, 
    {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'}, 
    {'depth': 1, 'line': 12, 'type': 'def', 'name': 'find_multi(self)'}, 
    {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'}, 
    {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'}, 
    {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'} 
]

我cosidering得到的结果看起来像以下层次：

functions_hir = [{ 
    'value': {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    'children': [{ 

     'value': {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'}, 
     'children': [{ 

      'value': {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'}, 
      'children': [] 
     }] 
    },{ 
     'value': {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'}, 
     'children': [] 
    },{ 
     'value': {'depth': 1, 'line': 12, 'type': 'def', 'name': 'find_multi(self)'}, 
     'children': [] 
    }] 
},{ 
    'value': {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'}, 
    'children': [] 
},{ 
    'value': {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'}, 
    'children': [{ 

     'value': {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'}, 
     'children': [] 
    }] 
}]

现在，它的简单对我来说，迭代它/递归。但我从没有运气从我的列表中产生这样的层次结构（我甚至没有接近，我猜）..而且我实际上不知道从哪里开始..希望任何人都能设法帮助我！

来源

2013-07-10 JHolta

对于所示的简单的情况下，你可以只保留父母的跟踪和建立你的树从列表中的一个传球，像这样的工作：

hir = {'children': [], 'parent': None} 
depth, current = 0, hir 

for f in functions: 
    f['children'] = [] 
    f_depth = f['depth'] 
    if depth == f_depth: 
     current['children'].append(f) 
     f['parent'] = current 
     current = f 
     depth += 1 
    else: 
     while depth > f_depth: 
      depth -= 1 
      current = current['parent'] 
     current['children'].append(f) 
     f['parent'] = current 
     current = f 
     depth += 1

您希望您的根节点的样子其他节点，或者你将不得不添加特别的处理，这是混乱的。

来源

2013-07-10 07:41:42

看起来像一个真正的昂贵的解决方案。我需要花点时间考虑我是否会接受它。我不太喜欢这种方式。 – JHolta

昂贵的如何？它引入了一个父指针和一个子列表，但没有复制。 –

我明白了。那么，仍然不是我想要的，但我很难理解如何在我的工作中使用这种结构。 – JHolta

你可以使用递归方法，该功能将让你线性时间想词典：

functions = [ 
    {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'}, 
    {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'}, 
    {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'}, 
    {'depth': 1, 'line': 12, 'type': 'def', 'name': 'find_multi(self)'}, 
    {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'}, 
    {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'}, 
    {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'} 
] 

i = 0 
def gather(d): 
    global i 
    res = [] 
    while i < len(functions): 
     if functions[i]["depth"] < d: 
      return res 
     elif functions[i]["depth"] == d: 
      value, i = functions[i], i + 1 
      children = gather(d + 1) 
      res.append({"value": value, "children": children}) 
    return res 

result = gather(0)

，或者你可以做到这一点没有全局变量：

def gather(d, i): 
    res = [] 
    while i < len(functions): 
     if functions[i]["depth"] < d: 
      return i, res 
     elif functions[i]["depth"] == d: 
      value = functions[i] 
      i, children = gather(d + 1, i + 1) 
      res.append({"value": value, "children": children}) 
    return i, res 

result = gather(0, 0)[1]

来源

2013-07-10 08:19:46

将字典列表转换为层次结构

回答

相关问题