递归函数只返回嵌套字典的一个分支的结果

Question

我有一个分支嵌套字典来可视化物种分类数据。我正在尝试编写一个函数，它在特定级别上为我提供所有分支

我尝试过迭代函数和递归函数，但我只使用了递归函数。 但是，根据我放置return/print语句的位置，我的函数要么返回None（但打印正确的信息），要么只返回数据的一个分支。 使用第二个选项，输出是完美的，直到数据集分支

tree = {"k-b":
        {"p-a":
         {"c-a":{"o-a":{}, "o-b":{}},
          "c-b":{"o-a":{}}},
         "p-b":
         {"c-a":{"o-a":{},"o-b":{}}}}}

def branches(tree, level):
    if level == 0:
        #print(tree.keys())
        return tree.keys()
    else:
        for i in tree.keys():
             return branches(tree[i], level-1)

print(branchNumber(tree, 2))

对于级别2，我期望[['c-a', 'c-b'], ['c-a']]（它不必是数组的数组，我也不关心它是否有dict\u keys（）或其他任何东西）

我实际上得到了dict_keys(['c-a', 'c-b'])，它排除了第二个分支

或者，如果在递归调用分支之前删除“return”并取消对print语句的注释，它将打印：

dict_keys(['c-a', 'c-b'])
dict_keys(['c-a']) 

这正是我想要的输出，但是函数返回None，所以我不能为将来的应用程序存储这些信息

Answer 1

您的代码总是返回循环中的第一项，因此您的算法过早地结束，并且没有探索所有必要的分支。您可以yield结果来创建生成器函数（除其他方法外）：

tree = {"k-b":
        {"p-a":
         {"c-a":{"o-a":{}, "o-b":{}},
          "c-b":{"o-a":{}}},
         "p-b":
         {"c-a":{"o-a":{},"o-b":{}}}}}

def branches(tree, level):
    if level == 0:
        yield list(tree.keys())
    elif level > 0:
        for v in tree.values():
            yield from branches(v, level - 1)

for i in range(4):
    print(f"level {i}:", list(branches(tree, i)))

输出：

level 0: [['k-b']]
level 1: [['p-a', 'p-b']]
level 2: [['c-a', 'c-b'], ['c-a']]
level 3: [['o-a', 'o-b'], ['o-a'], ['o-a', 'o-b']]

---

行elif level > 0:是一种优化，以避免深入到树中

另外，for i in tree.keys()，然后tree[i]访问值可以更清楚地表示为for v in tree.values()

Answer 2

听起来像是要返回所有分支的列表。一种方法是使用列表理解：

def branches(tree, level):
    if level == 0:
        #print(tree.keys())
        return tree.keys()
    else:
        return [branches(tree[i], level-1) for i in tree.keys()]

请注意，这将返回一个深度嵌套的列表。压平是留给读者的练习

Answer 3

您可能希望返回该级别上所有项的列表：

tree = {"k-b":
        {"p-a":
         {"c-a":{"o-a":{}, "o-b":{}},
          "c-b":{"o-a":{}}},
         "p-b":
         {"c-a":{"o-a":{},"o-b":{}}}}}

def branches(tree, level):
    if level == 0:
        #print(tree.keys())
        return tree.keys()
    else:
        return [branches(tree[i], level-1) for i in tree.keys()]

print(branches(tree, 2))

输出：

[[dict_keys(['c-a', 'c-b']), dict_keys(['c-a'])]]