0

我有一个看起来像这样的字典列表：

list = [{'parent': u'#5963','id': 5962},{'parent': u'','id': 5963}, 
{'parent': u'#5963', 'id': 5964}, {'parent': u'#5966', 'id': 5967}, 
{'parent': u'#5963','id': 5966}, {'parent': u'#5962','id': 5968} ]

实际的 dicts 有点复杂——它们有更多的键和值。

如您所见 - 每个 dict 都有一个“父”键，它告诉我们元素父的 id 和一个“id”键。

现在的问题是：是否有可能以所有 dicts 都以父子方式放置的方式构建一个新列表（或对这个列表进行排序）？

所以新的字典将是：

[{'parent': u'','id': 5963},{'parent': u'#5963','id': 5962}, 
{'parent': u'#5962','id': 5968}, {'parent': u'#5963', 'id': 5964},
{'parent': u'#5963','id': 5966}, {'parent': u'#5966', 'id': 5967} ]

PS：可能没有根元素（'parent' key = ''的元素）
PPS：父元素可能有超过1-2级子元素

4

1 回答 1

1

你不能用直接排序来做到这一点，首先从你的列表中构建一棵树。您需要两个信息：树中的顶级节点列表（没有父节点的节点或不存在父节点的子节点）和父/子关系：

def build_tree(l):
    exists = set(map(lambda x : x['id'], l))

    tops = []
    children = {}
    for e in l:
        parent = e['parent']
        if not parent:
            tops.append(e)
            continue

        parent = int(parent[1:])
        if parent not in exists:
            tops.append(e)
            continue

        if parent in children:
            children[parent].append(e)
        else:
            children[parent] = [ e ]

    return children, tops

然后使用递归函数对该树进行深度优先遍历：

def build_list(children, top):
    l = [ top ]
    if top['id'] in children:
        for child in children[top['id']]:
            l += build_list(children, child)
    return l

第一个函数为您提供子/关系结构，而第二个函数让您为每个可能的顶部节点构建一个列表。

现在您可以使用这两个函数对列表进行排序：

l = [{'parent': u'#5963','id': 5962},{'parent': u'','id': 5963},
{'parent': u'#5963', 'id': 5964}, {'parent': u'#5966', 'id': 5967},
{'parent': u'#5963','id': 5966}, {'parent': u'#5962','id': 5968} ]
children, tops = build_tree(l)
for top in tops:
    print build_list(children, top)
# outputs : [{'id': 5963, 'parent': u''}, {'id': 5962, 'parent': u'#5963'},
# {'id': 5968, 'parent': u'#5962'}, {'id': 5964, 'parent': u'#5963'},
# {'id': 5966, 'parent': u'#5963'}, {'id': 5967, 'parent': u'#5966'}]

如果删除节点 5963，则会给出：

[{'id': 5962, 'parent': u'#5963'}, {'id': 5968, 'parent': u'#5962'}]
[{'id': 5964, 'parent': u'#5963'}]
[{'id': 5966, 'parent': u'#5963'}, {'id': 5967, 'parent': u'#5966'}]
于 2013-07-05T09:59:58.817 回答