Рекурсивный подсчет узлов в двоичном дереве

Question

Я должен считать узлы в двоичном дереве рекурсивно. Я новичок в Python и не могу найти решение моей проблемы, чтобы закончить мой код.

Это то, что я уже пробовал. Как видите, он не завершен, и я не могу понять, куда идти.

class Tree:
    def __init__(self, root):
        self.root = root

    def add(self, subtree):
        self.root.children.append(subtree)

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children is not None else []

def check_root(tree):
    if tree.root is None:
        return 0
    if tree.root is not None:
        return count_nodes(tree)

def count_nodes(tree):
    if tree.root.children is not None:
        j = 0
        for i in tree.root.children:
            j = 1 + count_nodes(tree)
        return j


print(count_nodes(Tree(None))) # 0
print(count_nodes(Tree(Node(10)))) # 1
print(count_nodes(Tree(Node(5, [Node(6), Node(17)])))) #3

С каждым новым шагом я получаю разные ошибки. Например, с этим кодом я превысил максимальную глубину рекурсии.

Спасибо, что уделили время на прочтение этого. Любая подсказка или помощь, что делать дальше будет принята с благодарностью.

Answer 1

Простой способ:

Допустим, A - это двоичное дерево с дочерними элементами или узлами, которые не являются NULL . Например,

     3  
    / \  
  7     5  
   \     \  
   6       9  
  / \     /  
 1  11   4 

Теперь для подсчета количества узлов у нас есть простой обходной путь.

Рекурсивный метод: >>> get_count (root)

Для бинарного дерева основная идея рекурсии состоит в том, чтобы пройти дерево в Post-Order . Здесь, если текущий узел заполнен, мы увеличиваем результат на 1 и добавляем возвращаемые значения левого и правого поддеревьев, такие как:

class TestNode(): 


def __init__(self, data):  
    self.data = data 
    self.left = None
    self.right = None

Теперь мы продвигаемся вперед, чтобы получить количество полных узлов в двоичном дереве, используя метод, приведенный ниже:

def get_count(root): 

  if (root == None): 
    return 0

  res = 0
  if (root.left and root.right): 
     res += 1

  res += (get_count(root.left) + 
        get_count(root.right))  
  return res  

В конце, чтобы запустить код, мы будем управлять основной областью действия : Здесь мы создаем наше двоичное дерево A , как указано выше:

if __name__ == '__main__': 

  root = TestNode(3)  
  root.left = TestNode(7)  
  root.right = TestNode(5)  
  root.left.right = TestNode(6)  
  root.left.right.left = TestNode(1)  
  root.left.right.right = TestNode(4)

Теперь в конце, внутри main scope мы напечатаем количество двоичных файловузлы дерева, такие как:

  print(get_Count(root)) 

Вот временная сложность этой рекурсивной функции для get_count для двоичного дерева A .

Сложность времени: O (n)

Answer 2

Я бы начал с передачи корневого узла в функцию count_nodes -

print(count_nodes(Tree(None)).root) # 0
print(count_nodes(Tree(Node(10))).root) # 1
print(count_nodes(Tree(Node(5, [Node(6), Node(17)]))).root) #3

или сделал бы вспомогательную функцию для этого.

Тогда функция count_nodes может просто выглядетькак это

def count_nodes(node):
    return 1 + sum(count_nodes(child) for child in node.children)

РЕДАКТИРОВАТЬ: Я только что заметил, вы можете иметь корень None, это означает, что вы также должны обрабатывать это:

def count_nodes(node):
    if node is None:
        return 0
    return 1 + sum(count_nodes(child) for child in node.children)

И если вы действительно хотите обрабатывать дерево или узел в одной функции, вы можете сделать его немного уродливее:

def count_nodes(tree_or_node):
    if isinstance(tree_or_node, Tree):
        return count_nodes(tree_or_node.root)
    if tree_or_node is None:
        return 0
    return 1 + sum(count_nodes(child) for child in tree_or_node.children)

и затем вы можете вызвать его так, как вы это делали изначально.

Answer 3

Ваша проблема в том, что вы считаете одно и то же дерево бесконечно. Посмотрите на эту строку:

j = 1 + count_nodes(tree)