在 Python 中的字典树中生成所有叶到根的路径 [英] Generate all leaf-to-root paths in a dictionary tree in Python

问题描述

我有一个非标准"形式的字典树，如下所示:

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 路径(节点，子树，acc=[]):如果不是子树:产量[节点]+acc对于 n, s 在 subtree.items() 中:屈服路径(n，s，acc)

它并没有真正做到我想要的:

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

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

解决方案

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

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

这是一个类似的 paths() 函数，它应该可以做你想做的事:

def 路径(树，cur=()):如果不是树:收益率曲线别的:对于 n, s 在 tree.items() 中:对于 path(s, cur+(n,)) 中的路径:屈服路径

结果:

<预><代码>>>>列表(路径(树))[('0', 'A', 'B', 'C'), ('0', 'D', 'E'), ('0', 'D', 'F')]

请注意，我使用元组作为默认参数而不是列表，这是因为可变的默认参数会给您带来麻烦.

I have a dictionary-tree in an "non-standard" form like so:

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

Leaf nodes are defined as dictionary key-value pairs where the values is an empty dictionary. I would like to extract all the leaf-to-root paths as lists of lists like so:

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

The paths can be reversed too if that is helpful.

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

I know I have to do it recursively and I need an accumulator list for each path. It would also be nice if the function yielded the path-lists. What I have so far is this:

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

It doesn't really do what I want:

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

Ideally this should return the list-of-lists. Any help will be much appreciated.

解决方案

Assuming you actually intended the following structure for tree:

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

Here is a similar paths() function that should do what you want:

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

Result:

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

Note that I used a tuple as the default argument instead of a list, this is because mutable default arguments can get you into trouble.

这篇关于在 Python 中的字典树中生成所有叶到根的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！