Python递归函数来创建通用树 [英] Python recursive function to create generic tree

问题描述

我正在尝试为每个节点创建一个具有 n 个子节点的树.问题是，当我尝试使用递归函数来实现它时，我最终会进行多次递归调用，因此我无法使用单个 return 语句，因此将 None 设为最终结果.

I'm trying to create a tree with n children for each node. Problem is, when I try to implement this using a recursive function, I ends up with multiple recursive calls so I can't have a single return statement, hence having None as a final result.

这是我的一段代码:

def recursive_func(tree, n):
    if n == 0:
        return tree
    else:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)
            tree.addChild(child_tree)

get_permutations() 给出要创建的子树列表.我还有一个 Tree 类，其中包含一个节点值和一个子项列表.

get_permutations() gives a list of child trees to create. I also have a Tree class with a node value and a list of children.

这是树类:

class Tree:
    def __init__(self, result):
        self.node = node
        self.children = []

    def addChild(self, tree):
        self.children.append(tree)

这可能是我的问题设计中的新手错误，但我很乐意得到一些帮助.

This is probably a rookie error in the design of my problem, but I would be glad to get some help.

推荐答案

TLDR:既然你使用了 recursive_func 的结果，它应该总是 return 它的 tree.

TLDR: Since you use the result of recursive_func, it should always return its tree.

recursive_func 对这个问题有三个重点:

The recursive_func has three important points for this problem:

def recursive_func(tree, n):
    if n == 0:
        return tree  # 1.
    else:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)  # 2.
            tree.addChild(child_tree)
    # 3.

现在，1. 定义函数有时返回一个Tree.这与 2. 匹配，always 期望函数返回一个 Tree.但是，两者都与 3. 冲突，后者在第二个分支完成时隐式返回 None.

Now, 1. defines that the function sometimes returns a Tree. This matches 2. which always expects the function to return a Tree. However, both conflict with 3., which implicitly returns None when the second branch is done.

由于除了 return 之外第一个分支是空的，1. 和 3. 都可以折叠到一个路径，总是返回一个Tree.

Since the first branch is empty aside from the return, both 1. and 3. can be collapsed to one path that always returns a Tree.

def recursive_func(tree, n):
    if n > 0:
        permutations = get_permutations()
        for permutation in permutations:
            child_tree = recursive_func(Tree(permutation), n-1)
            tree.addChild(child_tree)
    return tree

这篇关于Python递归函数来创建通用树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！