建筑，父子依赖

Question

名单我有类型的字典列表看起来是这样的：

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} ] 

实际类型的字典是一个有点复杂 - 他们有更多的键和值。

正如你所看到的 - 每个字典都有一个“父母”键，它告诉我们元素父母的ID和'ID'键。

现在的问题是：是否有可能建立一个新的列表（或排序这一个）的方式，所有的字母都是父母的方式？

所以新的字典将是：

[{'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：有可能没有根元素
PPS（用“父”键=“”元素）：父元素可以具有多于1-2级的儿童

Answer 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 

第一个功能给你的孩子/关系结构，而第二个让你建立对每个可能的顶部节点列表。如果删除节点5963，这将使

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

：

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