1

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

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()'}
]

我正在考虑让结果看起来像以下层次结构：

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': []
    }]
}]

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

4

2 回答 2

2

你可以使用递归方法，这个函数会在线性时间内制作你想要的字典：

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-10T08:19:46.673 回答
1

对于所示的简单案例，您可以只跟踪父母并从列表中一次性构建您的树，如下所示：

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-10T07:41:42.657 回答