时间戳

首页 > 解决方案 > 如何从这个列表中获取所有的孩子、孙子……？

python - 如何从这个列表中获取所有的孩子、孙子……？

问题描述

我items是亲子关系。每个孩子都知道它的父母，但父母不知道它的孩子和孙子：

items = [
  {'id': 1, 'parent': None},
  {'id': 2, 'parent': 1},
  {'id': 3, 'parent': 2},
  {'id': 4, 'parent': None},
  {'id': 5, 'parent': 4},
]

我正在尝试构建一个 dict，其中包含所有项目 id 及其所有子项、孙子项等的列表：

all_children_of_items = {
  1: [2, 3],  # 2 = child, 3 = grandchild
  2: [3],
  3: [],
  4: [5],
  5: [6]
}

我目前的方法只考虑孩子，而不是孙子：

all_children_of_items = {}
while True:
  change = False
  for item in items:
    if item['id'] not in all_children_of_items:
      all_children_of_items[item['id']] = []
    if item['parent']:
      if item['parent'] not in all_children_of_items:
        all_children_of_items[item['parent']] = []
      if item['id'] not in all_children_of_items[item['parent']]:
        all_children_of_items[item['parent']].append(item['id'])
  if not change:
    break

当前结果：

{
  1: [2], 
  2: [3], 
  3: [], 
  4: [5], 
  5: []
}

任何的想法？提前致谢！

标签： pythonpython-3.xtreenested

解决方案

你可以试试这个：

tree = {}

for item in items:
    parent = item['id']
    child = [it['id'] for it in items if it['parent'] == parent]
    grandchild = [it['id'] for c in child for it in items if it['parent'] == c]
    tree[parent] = [*child, *grandchild]

print(tree)

输出： {1: [2, 3], 2: [3], 3: [], 4: [5], 5: []}

我看不到小时候5的6情况，所以我的代码也没有。

可以进一步优化代码，并针对更一般的用例进行修改。我把它留给你，你认为合适。

编辑：

为了：

items = [{'id': 1, 'parent': None},
 {'id': 2, 'parent': 1},
 {'id': 3, 'parent': 2},
 {'id': 4, 'parent': 3},
 {'id': 5, 'parent': 4}]

代码：

def nepotism(parent):
    lineage = []
    def recurs(parent):
        for item in items:
            if item['parent'] == parent:
                possible_parent = item['id']
                lineage.append(possible_parent)
                recurs(possible_parent)
    recurs(parent)
    return lineage

tree = dict([(item['id'], nepotism(item['id'])) for item in items])
print(tree)

输出：

{1: [2, 3, 4, 5], 2: [3, 4, 5], 3: [4, 5], 4: [5], 5: []}

推荐阅读