-2

从如下所示的字典中创建家谱的最快方法是什么：

family = [
    {'name': 'a', 'parent': ''},
    {'name': 'b', 'parent': 'a'},
    {'name': 'c', 'parent': 'a'},
    {'name': 'd', 'parent': 'b'},
    {'name': 'e', 'parent': 'd'},
    {'name': 'f', 'parent': ''},
    {'name': 'g', 'parent': 'f'},
    {'name': 'h', 'parent': 'a'}
]

最终，我试图将其打印出来（带有大量额外信息，但这是一般的想法），如下所示的列表：

a
  b
    d
      e
  c
  h
f
  g

解决方案是创建一个函数来遍历列表直到它为空，在它找到父项的每个项目上使用 .pop() 吗？或者在python中有更好的方法吗？

这是一个更大问题的一部分，但是，我正在尝试找到完成这个小部分的最佳方法。因此，即使是 lambda 的噩梦也可能是可能的。请尝试以一种易于扩展的简洁方式回答:)

4

2 回答 2

3

我建议将您的字典列表处理成更有用的数据结构。我会制作一个从父母到他们孩子列表的字典映射（没有父母的“祖先”将被包括为空字符串的“孩子”）。

然后，递归地应用以下算法打印出树，从祖先列表和depth0 开始：

  1. 遍历输入列表中的人员（如果列表为空，则什么都不做，作为我们的基本情况）。
  2. 对于每个人，首先打印他们的名字，前面有depth空格。
  3. 从我们的字典中查找那个人的孩子的列表，然后递归，depth一个更大的。
  4. 继续到下一个人。

这是代码：

from collections import defaultdict

def preprocess(family_list):
    descent_dict = defaultdict(list)
    for person in family_list:
        descent_dict[person["parent"]].append(person["name"])
    return descent_dict

def print_family_tree(descent_dict, people, depth=0):
    for person in people:
        print("  "*depth+person)
        print_family_tree(descent_dict, descent_dict[person], depth+1)

示例运行：

>>> family = [
    {'name': 'a', 'parent': ''},
    {'name': 'b', 'parent': 'a'},
    {'name': 'c', 'parent': 'a'},
    {'name': 'd', 'parent': 'b'},
    {'name': 'e', 'parent': 'd'},
    {'name': 'f', 'parent': ''},
    {'name': 'g', 'parent': 'f'},
    {'name': 'h', 'parent': 'a'}
]

>>> d = preprocess(family)
>>> print_family_tree(d, d[''])
a
  b
    d
      e
  c
  h
f
  g
于 2013-11-11T09:31:56.803 回答
1

警告 - 这是一个糟糕的解决方案

请改用@Blckknght 提供的以下答案。这是一个糟糕的解决方案，运行时间为 O(N**2)，因为它依赖于格式错误的数据结构。

您将需要使用一个递归函数，该函数接收一个根节点，打印该节点的所有子节点，然后调用自身。像下面这样的东西。不要试图在适当的位置编辑家庭字典，你只会让你的生活变得比需要的更难。

类似下面的功能可能对您有用。请记住，这只是一个简单的示例，您需要添加相当多的错误处理，以避免它在您有循环或 owt 时爆炸。

INDENT = ' ' #Change this to taste

def print_family(parent,family,indent=0):
    for child in family:
        if child['parent'] == parent:

             # Print here
             print '%s%s' % (INDENT * indent,child['name'])

             # Call on the child
             print_family(child['name'],family,indent + 1)

# Kick it off with the root node
print_family('',family)
于 2013-11-11T09:32:55.213 回答