Как получить листовые узлы дерева с помощью Python?

Question

Привет, я новичок в ООП, поэтому имейте это в виду, пока вы читаете это.

У меня есть простая реализация дерева Python (см. Ниже код).

class TreeNode(object): 
    def __init__(self, data): 
     self.data = data 
     self.children = [] 

    def add_child(self, obj): 
     self.children.append(obj) 

class Tree: 
    def __init__(self): 
     self.root = TreeNode('ROOT') 

    def preorder_trav(self, node): 
     if node is not None: 
      print node.data 
      if len(node.children) == 0: 
       print "("+ node.data + ")" 
       for n in node.children: 
        self.preorder_trav(n) 

if __name__ == '__main__': 
    tr = Tree() 
    n1 = tr.root 
    n2 = TreeNode("B") 
    n3 = TreeNode("C") 
    n4 = TreeNode("D") 
    n5 = TreeNode("E") 
    n6 = TreeNode("F") 

    n1.add_child(n2) 
    n1.add_child(n3) 
    n2.add_child(n4) 
    n2.add_child(n5) 
    n3.add_child(n6) 

    tr.preorder_trav(n1) 

Теперь мне нужно реализовать метод получения листов листьев. Под термином листовой узел Я имею в виду узел, у которого нет детей.

Мне интересно, как сделать get_leaf_nodes() метод.

Некоторые решения приходят на мой взгляд, являются

1. Создание self.leaf_nodes = [] внутри метода __init__. Сделав это, я знаю, что это увидит только этот экземпляр дерева.
2. Изготовление класса leaf_nodes = [] над __init__ способ. Сделав это, я знаю, что все экземпляры дерева смогут увидеть список leaf_nodes.

Вышеупомянутые решения заставят меня создать список leaf_nodes внутри моего класса, чтобы использовать метод get_leaf_nodes(). Я ищу только метод get_leaf_nodes(), который будет выполнять вычисления на моем дереве и вернет список.

Например, в C мы будем называть malloc(), а затем мы можем вернуть указатель на функцию, которая называется get_leaf_nodes().

Answer 1

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

def get_leaf_nodes(self): 
    leafs = [] 
    def _get_leaf_nodes(node): 
     if node is not None: 
      if len(node.children) == 0: 
       leafs.append(node) 
      for n in node.children: 
       _get_leaf_nodes(n) 
    _get_leaf_nodes(self.root) 
    return leafs 

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

def get_leaf_nodes(self): 
    leafs = [] 
    self._collect_leaf_nodes(self.root,leafs) 
    return leafs 

def _collect_leaf_nodes(self, node, leafs): 
    if node is not None: 
     if len(node.children) == 0: 
      leafs.append(node) 
     for n in node.children: 
      self._collect_leaf_nodes(n, leafs) 

Это способ, которым я хотел бы сделать это в Java.

Answer 2

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

def get_leaves(node): 
    if not node.children: 
     yield node 

    for child in node.children: 
     for leaf in get_leaves(child): 
      yield leaf 

Answer 3

Один из хороших рекурсивных подходов к поиску листьев.

def leaf_count(self): 

     if(self == None): 
      return 0 

     if(self.left == None or self.right == None): 
      return 1 

     return self.left.leaf_count() + self.right.leaf_count()