Подсчет количества узлов в бинарном дереве с листьями

Question

Основной класс Дерево

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

    def count_nodes(self): 
     if self.value is None: 
      return -1 
     else: 
     return 1 + self.count_nodes(self.left) + self.count_nodes(self.right) 

      #self.size += 1 
      #if self.left is not None: 
       #self.left.count_nodes() 
      #if self.right is not None: 
       #self.right.count_nodes() 
      #return self.size 

с подклассами Node и листьев

class Node (Tree): 
    def __init__(self, value, left, right): 
     self.left = left 
     self.right = right 
     self.value = value 

class Leaf (Tree): 
    def __init__(self, value): 
     self.value = value 

Что мне делать, когда столкнулся с листа? Я попробовал вышеуказанные 2 метода и до сих пор не знаю, как обращаться с листом.

образца дерева будет следующим и tree.count-nodes() должен вернуть 7

tree = Node ("one", 
      Node ("two", Leaf ("three"), Leaf ("four")), 
      Node ("five", Leaf ("six"), Leaf ("seven"))) 

Answer 1

Ваш подход является правильным - число узлов в бинарном дереве равно 1 (корневой узел) + nodes_in_left_subtree (если существует) + nodes_in_right_subtree (если существует). Это рекурсивное определение и может быть реализовано как рекурсивная функция, как вы пробовали.

В вашей реализации у вас есть некоторые недостатки:

• вы не проверить, если поддеревья действительно существуют
• self.left и self.right фактически Tree и вы должны вызвать call_nodes на этих Tree S не на self

PS Ваш код не синтаксически корректен. Проверка self.value is None странная для меня, но это может быть правдой для вашего проблемного домена. root переменная никогда не используется. Вы можете подумать, действительно ли это необходимо для текущей организации данных.

Answer 2

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

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

    def count_nodes(self,root): 
     if (root.right is None and root.left is None) : 
      return -1 
     else: 
     return 1 + self.count_nodes(self.left) + self.count_nodes(self.right)