Python:在每个节点扩展的算法遍历树

Question

我有一个字典，其中包含 id 和每个 ID 的多个值，它们是字符串。对于每个 Id 中的每个值，我进行数据库查询并获得设置结果:

{111: Run, Jump, swim}
{222: Eat, drink}

所以对于每个值，假设运行我执行一个查询，它返回另一组数据，然后选择该组的每个值并运行查询，这将给出另一组，最后我到达只有一个项目的地步返回。一旦我完成获取 Run 的每个子元素的最后一个元素，然后我移动到 Jump 并继续。

我之前问过这个问题，但没有得到任何结果，所以人们告诉我删除代码，然后再问这个问题。这是 link对于我几天前问的同一个问题。我需要实现类似 disjoin set 的东西吗？

Answer 1

您可以将类别/子类别视为一棵树，每个节点都有 N 个分支(取决于您有多少个类别)。据我所知，你基本上想要生成一个有序的树叶列表。

一种简单的方法是通过生成器(使用原始问题中的术语):

def lookup(elem):
    # do your SQL call here for a given category 'elem' and return
    # a list of it's subcategories
    return []

def leaves(lst):
    if lst:
        for elem in lst:                          # for every category
            for sublist in leaves(lookup(elem)):  # enumerate it's sub categories
                yield sublist                     # and return it
            yield elem                            # once lookup(elem) is [] return elem

d = { 111: [Run, Jump, swim] , 222: [Eat, drink] }

for key, lst in d.items():
    print key, [elem for elem in leaves(lst)]

如果您不熟悉生成器，它们只是“生成”值而不是返回值的迭代器结构。不同之处在于，yield 只会在那个位置暂停迭代器，当请求下一个值时，迭代器会在它停止的地方继续。

通过生成器内部的一些巧妙的递归，您可以简单地解析整棵树。

[elem for elem in leaves(lst)] 是一个列表理解，它只是为 leaves< 迭代的每个元素构建一个包含 elem 的列表.