python - 在 Python/Django 中递归收集 child

Question

我有一个这样的模型....

class Person(models.Model):
    name = models.CharField(max_length=55,null=False, blank=False)
    parent = models.ForeignKey('Person.Person', null=False, blank=False)

我想创建一个递归函数，它最终会返回一个包含整个人家谱的字典....

例如……

first_person = Person.objects.filter(name='FirstPerson')
family_tree = GetChildren(first_person)

其中 GetChildren 是我的递归函数，它将不断调用 GetChildren，直到没有更多的 child ......然后它应该返回一个包含所有这些 child 的字典......

{
    'name': 'FirstPerson',
    'children': [
        {
            'name': 'FirstPersonChild1'
            'children': [ ... ]
        },
        {
            'name': 'FirstPersonChild2'
            'children': [ ... ]
        }
    ]
}

我从来都不擅长递归，有人介意解释一下我将如何实现这一目标吗...

Answer 1

这个实现应该可以工作

def get_family_tree(person):
    """ return a family tree for a Person object """

    children = person.children.all()

    if not children:
        # this person has no children, recursion ends here
        return {'name': person.name, 'children': []}

    # this person has children, get every child's family tree
    return {
        'name': person.name,
        'children': [get_family_tree(child) for child in children],
    }

请注意，这将调用与人一样多的数据库调用。如果遇到性能问题，您可以尝试将所有数据提取到内存中。

关于递归的思考

考虑递归的一种方法是从基本情况开始——即递归结束的地方。对于您的情况，我们知道如果一个人没有 child ，家谱会是什么样子:

{
    'name': 'FirstPerson',
    'children': [],
}

在你有了基本情况之后，想想你必须执行一次递归的问题。

在您的情况下，这将是有 child 的 parent ，但没有孙子。我们知道每个 child 的家谱应该是什么样子——这只是基本情况!这引导我们找到返回 parent 姓名和每个 child 的家谱列表的解决方案。导致类似的事情:

{
    'name': FirstPerson,
    'children': [<each element is a child's family tree>]
}

编辑

Django 自动为外键生成反向关系。

class Person(models.Model):
    ....
    parent = models.ForeignKey('self', related_name='children', blank=True, null=True)

p = Person()
p.children.all() # automatically fetch all Person objects where parent=p

参见 https://docs.djangoproject.com/en/1.9/ref/models/fields/#foreignkey