在Python / Django中递归收集子级 [英] Recursively Collect Children in Python/Django

问题描述

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

I have a model like so....

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

我想创建一个递归函数，该函数最终将返回整个人家谱的字典...。

I want to create a recursive function that will eventually return a dictionary of an entire persons family tree....

例如...

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

GetChildren是我的递归函数，该函数将不断呼叫GetChildren，直到没有更多的孩子为止……然后应该返回一个字典，像这样保存所有这些孩子...

Where GetChildren is my recursive function that will continuously call GetChildren, until there are no more children... It should then return a dictionary that holds all of these children like so...

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

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

I have never been good with recursion, would someone mind explaining how I would go about accomplishing this...

推荐答案

此实现应正常工作

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

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

Note that this will take as many database calls as there are persons. You can try to fetch all the data into memory if you run into performance issues.

思考递归

考虑递归的一种方法是从基本情况开始-即递归将在何处结束。在您的情况下，我们知道如果一个人没有孩子，家族树的样子：

One way to think about recursion is to start off with the base case - i.e. where the recursion will end. In your case, we know how the family tree looks like if a person has no children:

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

有了基本案例后，考虑一下必须执行一次递归的问题。

After you have the base case(s), think about the problem where you have to perform the recursion once.

在您的情况下，应该是有孩子的父母，但没有大孩子。我们知道每个孩子的家谱应该是什么样子-这只是基本情况！这使我们找到了解决方案，在该解决方案中，我们返回了父母的名字以及每个孩子的家谱的列表。导致类似这样的情况：

In your case, it would be parents with children, but no grand children. We know how each child's family tree should look - it's just the base case! This leads us to the solution where we return the parent's name, and a list of each child's family tree. Leading to something like:

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

编辑

Django会自动为ForeignKey生成反向关系。

Django automatically generates reverse relations for a ForeignKey.

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

这篇关于在Python / Django中递归收集子级的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！