python - "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 = {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

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

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

更正这些，函数变为:

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