Python迭代嵌套字典

Question

首先，问题和代码如下：

def family_lineage(familytree, lineage):
    '''(dict, list of strs) -> boolean
    Return True if lineage specifies a list of names who are directly related
    in a chain of parent-child relationships, and NOT child-parent, parent-grandchild..etc,
    beginning from the first generation listed.

    >>> trace_lineage({'Gina': {'Sam': {'Tina': {}},
                           'Li': {}},
                   'Guy': {}},
                      ['Gina'])
    True

    >>> trace_lineage({'Gina': {'Sam': {'Tina': {}},
                               'Li': {}},
                       'Guy': {}},
                      ['Gina', 'Sam', 'Tina'])
    True
    >>> trace_lineage({'Gina': {'Sam': {'Tina': {}},
                               'Li': {}},
                       'Guy': {}},
                      ['Gina', 'Tina'])
    False
    '''

所以，在上面的例子中，它显示“Guy”没有孩子，“Gina”有两个孩子，“Sam”和“Li”山姆有一个孩子，蒂娜。在

^{pr2}$

所以，我的问题是，如果家族树延续超过三代，我该怎么写？有没有更简洁的方法来编写这段代码？在

Answer 1

基本上，您希望查看是否可以遍历树；使用^{}循环元素，如果引发KeyError，则路径不存在：

def family_lineage(familytree, lineage):
    if not familytree:
        return False
    try:
        reduce(lambda d, k: d[k], lineage, familytree)
        return True
    except KeyError:
        # No match at this level, recurse down the family tree
        return any(family_lineage(val, lineage) for val in familytree.itervalues())

reduce()将lambda函数递归地应用于lineage，从familytree开始。在

为了支持在树的更深层次查找沿袭，您需要在KeyErrors上向下递归

演示：

^{pr2}$

Answer 2

以下是一种迭代方法，即使lineage不是从家谱树的顶部开始的，它也可以工作：

def family_lineage(familytree, lineage):
    trees = [familytree]
    while trees:
        tree = trees.pop()
        trees.extend(t for t in tree.values() if t)
        for name in lineage:
            if name not in tree:
                break
            tree = tree[name]
        else:
            return True
    return False