Как подсчитать листья двоичного дерева?

Question

class Node: 
    def __init__(self, item, left = None, right = None): 
     self.item = item 
     self.left = left 
     self.right = right 

class BST: 

    def __init__(self): 
     self.root = None 

    def recurse_add(self, ptr, item): 
     if ptr == None: 
      return Node(item) 
     elif item < ptr.item: 
      ptr.left = self.recurse_add(ptr.left, item) 
     elif item > ptr.item: 
      ptr.right = self.recurse_add(ptr.right, item) 
     return ptr 

Вот моя попытка:

def count_leaves(self): 
     ptr = self.root 
     counter = 0 
     if ptr.left is None and ptr.right is None: 
      counter += 1 
     if ptr.left: 
      counter += self.count_leaves() 
     if ptr.right: 
      counter += self.count_leaves() 
     return counter 

Я получил RecursionError, есть в любом случае, что я мог бы это исправить Может кто-нибудь объяснить мне, как я буду считать листья бинарного дерева?

Answer 1

Вы всегда повторяете узел self, когда считаете листья.

def count_leaves(self): 
    ptr = self.root # reseting at the root 
    ... 
    counter += self.count_leaves() # recurses from the top of the tree 

Ваша вторичная проблема, похоже, связана с тем, как вы добавляете узлы.

Например,

def recurse_add(self, ptr, item): 
    if prt == None: 
     # say this is false 
    ptr.left = self.recurse_add(ptr.left, item) 
    ... 
    return ptr # The recursive call will return 'ptr.left' 

Таким образом, в основном ptr.left = ptr.left в том случае, ptr != None

Вам нужно перебирать вниз. Обычно я реализую все рекурсивные методы в классе Node, а не передаю указатель в классе Tree.

class Node(object): 
    def __init__(self, item, left = None, right = None): 
     self.item = item 
     self.left = left 
     self.right = right 

    def is_leaf(self): 
     return self.right is None and self.left is None 

    def add(self, item): 
     if item <= self.item: 
      self.left = Node(item) if self.left is None else self.left.add(item) 
     elif item > self.item: 
      self.right = Node(item) if self.right is None else self.right.add(item) 
     return self 

    def count_leaves(self): 
     counter = 0 
     if self.is_leaf(): 
      counter += 1 
     if self.left is not None: 
      counter += self.left.count_leaves() 
     if self.right is not None: 
      counter += self.right.count_leaves() 
     return counter 

Теперь просто передайте методы корню из дерева, если у вас есть корень.

class BST: 

    def __init__(self): 
     self.root = None 

    def is_empty(self): 
     return self.root is None 

    def add(self, item): 
     if self.is_empty(): 
      self.root = Node(item) 
     else: 
      self.root.add(item) 

    def count_leaves(self): 
     return 0 if self.is_empty() else self.root.count_leaves()