"Not in function" 递归函数错误

Question

我正在编写一个算法来计算一棵树的节点总数。这是代码：

def tree_nodes(tree):
    """Given a tree, returns the total amount of nodes it has."""
    def recursive_node_count(node):
        """Recursive count function."""
        childs = tree[node]
        if childs == None:
            return 1
        else:
            nodes_so_far = 0
            for i in xrange(len(childs)):
                nodes_in_this_branch = recursive_node_count(childs[i])
                nodes_so_far += nodes_in_this_branch          
            return nodes_so_far

    root = tree['root']
    total_nodes = recursive_node_count(root)
    return total_nodes

tree 基本上是一个列表字典。示例：

tree = {0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0}

当我尝试运行我的代码时，这是我收到的输出：

at Answer.py. not in a function on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in recursive_node_count on line 31
at Answer.py. in tree_nodes on line 36
at Answer.py. in <module> on line 96

这些是原始代码中的行 31（在函数定义内）、36（也在定义内）和 96（对定义的调用）：

31: nodes_in_this_branch = recursive_node_count(childs[i])
36: total_nodes = recursive_node_count(root)
96: nodes = tree_nodes(tree)

我检查了语法、缩进、制表符、空格，但找不到错误。我是 Python 的初学者。你们能帮帮我吗？

Answer 1

您当前的代码有 2 个问题，

您目前不计算根节点
当没有 child 时你 return 为 1，在这种情况下你应该 return 为 0。我们同样需要计算每个级别的 childs 的数量，因此 nodes_so_far 应该用 childs 列表的长度初始化

更正这些，函数变为：

def tree_nodes(tree):
    """Given a tree, returns the total amount of nodes it has."""
    def recursive_node_count(node):
        """Recursive count function."""
        childs = tree[node]
        if childs == None:
            return 0 # There are no child so return 0 in base case
        else:
            nodes_so_far = len(childs) # set to number of nodes passed
            for i in xrange(len(childs)):
                nodes_in_this_branch = recursive_node_count(childs[i])
                nodes_so_far += nodes_in_this_branch          
            return nodes_so_far
    root = tree['root']
    total_nodes = 1 + recursive_node_count(root) # Add 1 to count the root node
    return total_nodes

在干燥的运行中，这给出了输出：

>>> tree = {0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0}
>>> tree_nodes(tree)
5

Answer 2

您的回答遗漏了几件事。这是围绕您的代码编写的固定版本：

def tree_nodes(tree):
    def recursive_node_count(node):
        if node is None:
            return 0
        total_nodes = 1
        if tree[node]:
            for child in tree[node]:
                if child:
                    total_nodes += recursive_node_count(child)
        return total_nodes

    root = tree['root']
    total_nodes = recursive_node_count(root)
    return total_nodes

>>> tree = {0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0}
>>> print tree_nodes(tree)
5

Answer 3

根据您提供的代码，我无法重现该错误。它在语法上没有任何问题，而且确实运行良好。如果您可以更深入地了解您遇到的错误，我将编辑我的答案。

也就是说，正如 mu 指出的那样，此代码将 return 节点数不正确。具体来说，它将 return 树的叶子数，因为如果当前节点没有任何子节点，您只计算当前节点。这个问题可以通过将 nodes_so_far 初始化为代表当前节点的 1 来解决。

作为建议，您可能希望将 for in xrange python 语句切换为普通的 for in 语句。 for in 语句遍历列表，这样您就不必使用索引号返回列表。

下面的代码说明了这些变化。此代码将始终输出正确数量的节点，即使在只有一个节点并且是根节点的情况下也是如此。

def tree_nodes(tree):
    """Given a tree, returns the total amount of nodes it has."""
    def recursive_node_count(node):
        """Recursive count function."""
        childs = tree[node]
        if not childs:
            # Return 1 for the current node.
            return 1
        else:
            # Initialize to 1 to count the current node.
            nodes_so_far = 1
            # Python for in statement
            for child in childs:
                nodes_for_child = recursive_node_count(child)
                nodes_so_far += nodes_for_child
            return nodes_so_far
    root = tree['root']
    total_nodes = recursive_node_count(root)
    return total_nodes

print(tree_nodes(tree={0: [1], 1: [2], 2: [3, 4], 3: None, 4: None, 'root': 0}))
print(tree_nodes(tree={0: None, 'root': 0}))

"Not in function" 递归函数错误

"Not in function" error in recursive function

python

tree

recursion

function