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

Question

我有一个字典，里面有ID和每个ID对应的多个字符串值。对于每个ID的每个值，我都会进行一次数据库查询，并得到一组结果：

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

比如说，对于每个值，比如“运行”，我执行一个查询，它会返回另一组数据，然后我从这组数据中取出每个值，再执行查询，这样又会得到另一组数据。最后，我会得到一个最终的结果。等我把每个“运行”下的所有子元素的最终结果都拿到后，我就会转到“跳跃”这个部分，继续处理。

我之前问过这个问题，但没有得到任何回复，所以有人建议我去掉代码，只问问题。这里是我几天前问的同样问题的链接。我需要实现类似于不相交集合的东西吗？

Answer 1

这看起来像是普通的树遍历。你可以使用广度优先搜索（BFS）或者深度优先搜索（DFS）。

Answer 2

你可以把类别和子类别想象成一棵树，每个节点有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)]

如果你对生成器不太熟悉，它们其实就是一种迭代器，能够“产生”值，而不是直接返回值。它们的不同之处在于，产生值时只是暂时停在那个位置，当你请求下一个值时，它会从停下的地方继续。

通过在生成器内部使用一些巧妙的递归，你可以轻松地解析整棵树。

[elem for elem in leaves(lst)] 是一种列表推导式，它的作用是为每一个由 leaves 迭代的元素构建一个包含 elem 的列表。