通过字典的字典递归，总是从顶部开始

Question

我有一本字典，内容如下，层次结构不详：

dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}}

我找到了thefollowinguseful来学习如何递归，但是我很难修改代码来获得我想要的，它是从顶层到死胡同的所有路径的列表。你知道吗

所需输出为：

list = ['a,b,c', 'a,b,d', 'a,b,e', 'f,g']

为了开始处理这个问题，我使用了DFS方法：

hierarchy = []
for parent in dict_of_dicts:
    recurse_dicts(concepts, parent, hierarchy)

def recurse_dicts(concepts, parent, hierarchy):
    hierarchy.append(parent)
    for child in concepts[parents]:
        if len(recurse[node][child].keys()) > 0:
            recurse_dicts(recurse[node], child, hierarchy)
        else:
            return

这导致：

hierarchy = ['a', 'b', 'c', 'd', 'e']

这很重要，但不是我想要的。你知道吗

Answer 1

假设您的值是始终字典，您可以使用：

def paths(d, path=(), res=None):
    if res is None:
        res = []
    for key, value in d.iteritems():
        if not value:
            # end of the line, produce path
            res.append(','.join(path + (key,)))
        else:
            # recurse down to find the end of this path
            paths(value, path + (key,), res)
    return res

这将使用一个共享列表（在第一次调用时生成）将生成的路径传递回调用方，并为每个递归步骤构建一个路径，以便在遇到空值时将其添加到结果列表中。你知道吗

演示：

>>> dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}}
>>> paths(dict_of_dicts)
['a,b,c', 'a,b,e', 'a,b,d', 'f,g']

路径没有排序，因为字典没有顺序；如果需要，您仍然可以按键排序：

for key in sorted(d):
    value = d[key]

而不是for key, value in d.iteritems()循环。你知道吗

Answer 2

下面是一个递归DFS过程，用于跟踪每个分支的路径：

dict_of_dicts = {'a': {'b': {'c': {}, 'd': {}, 'e': {}}}, 'f': {'g': {}}}

def dfs(path, d):
    if d == {}:
        print path;
    for item in d:
        dfs(path+[item],d[item])

dfs([],dict_of_dicts)

输出：

['a', 'b', 'c']
['a', 'b', 'e']
['a', 'b', 'd']
['f', 'g']