python - 在 Python 的字典树中生成所有从叶到根的路径

Question

我有一个像这样的“非标准”形式的字典树:

tree = {'0': {'A': {'B': {'C': {}}}},
             {'D': {'E': {}},
                   {'F': {}}}}

叶节点被定义为字典键值对，其中值为空字典。我想将所有从叶到根的路径提取为列表列表，如下所示:

paths_ = [['C', 'B', 'A', '0'],
          ['E', 'D', '0'],
          ['F', 'D', '0']]

如果有帮助，路径也可以反转。

paths_ = [['0', 'A', 'B', 'C'],
          ['0', 'D', 'E'],
          ['0', 'D', 'F']]

我知道我必须递归地完成它，并且我需要为每条路径提供一个累加器列表。如果该函数产生路径列表也很好。我到目前为止是这样的:

def paths(node, subtree, acc=[]):
    if not subtree:
        yield [node]+acc
    for n, s in subtree.items():
        yield paths(n, s, acc)

它并没有真正按照我的意愿行事:

paths_ = list(paths('0', tree['0']))

理想情况下，这应该返回列表列表。任何帮助将不胜感激。

Answer 1

假设您实际上打算为 tree 使用以下结构:

tree = {'0': {'A': {'B': {'C': {}}},
              'D': {'E': {},
                    'F': {}}}}

这是一个类似的 paths() 函数，它应该可以执行您想要的操作:

def paths(tree, cur=()):
    if not tree:
        yield cur
    else:
        for n, s in tree.items():
            for path in paths(s, cur+(n,)):
                yield path

结果:

>>> list(paths(tree))
[('0', 'A', 'B', 'C'), ('0', 'D', 'E'), ('0', 'D', 'F')]

请注意，我使用元组而不是列表作为默认参数，这是因为 mutable default arguments can get you into trouble .