Ошибка «Не в функции» в рекурсивной функции

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 проблемы с текущим кодом,

1. Вы не сосчитать корневой узел в данный момент
2. Вы возвращаете 1, когда нет ни одного ребенка, вы должны возвращаться 0 в этом случае. Точно так же мы должны подсчитать количество Чайлдс на каждом уровне, так nodes_so_far должен быть инициализирован с длиной списке Чайлдс

Исправление для них функция становится:

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, этот код вернет неправильное количество узлов. В частности, он вернет количество листьев дерева, так как вы считаете только текущий узел, если у него нет детей. Эта проблема может быть устранена путем инициализации nodes_so_far до 1, представляющего текущий узел.

Как предложение, вы можете переключить оператор python for in xrange на простой оператор 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}))