Comment obtenir des nœuds feuilles de l'arbre à l'aide de Python?

Salut à tous, je suis nouveau sur OOP donc avoir cela à l'esprit pendant que vous êtes de lire ceci.

J'ai un simple Python arbre de la mise en œuvre(voir code ci-dessous).

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)

Ce dont j'ai besoin maintenant est de mettre en œuvre une méthode pour obtenir les Nœuds Feuilles en arrière. Par le terme nœud feuille je veux dire un nœud qui n'a pas d'enfants.

Je me demandais comment faire un get_leaf_nodes() méthode.

Certaines solutions me viennent à l'esprit sont

  1. Faire un self.leaf_nodes = [] à l'intérieur de la __init__ méthode. En faisant cela, je sais que ça va être vu que par cet arbre instance.
  2. Faire un membre de la classe leaf_nodes = [] ci-dessus __init__ méthode. En faisant cela, je sais tout l'arbre des instances seront en mesure de voir leaf_nodes liste.

Les solutions ci-dessus me poussera à créer un leaf_nodes liste à l'intérieur de ma classe afin que les get_leaf_nodes() méthode pourrait utiliser. Ce que je cherche, c'est d'avoir seulement un get_leaf_nodes() méthode qui vous permettra d'effectuer le calcul sur mon arbre et retourne une liste.

Par exemple en C, nous aurions appel malloc() et alors nous pourrions retourner le pointeur vers la fonction qui a appelé la get_leaf_nodes().

Habituellement, vous devez utiliser la récursivité pour résoudre ce problème. stackoverflow.com/questions/479343/...
Je sais que sur la récursivité. Je l'ai utilisé déjà à preorder_trav() la méthode aussi. Le truc, c'est que la OO problème de Conception que j'ai. Dois-je faire une liste à l'intérieur de ma classe ou il y a un moyen de retourner la liste des nœuds feuilles sans faire à l'intérieur de init ou en tant que membre de la classe?

OriginalL'auteur limitcracker | 2014-01-08

  1. 8

    En python, vous pouvez utiliser une fonction interne à recueillir les nœuds feuilles, puis retourner la liste d'entre eux.

    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

    Si vous voulez un plus propre approche de la programmation orientée objet, vous pouvez créer un supplément de méthode privée pour la collecte des feuilles:

    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)

    C'est la façon dont je le ferais en Java.

    Il a très bien fonctionné. J'ai un couple de questions. (a)Est-il propre approche de la programmation orientée objet pour utiliser une fonction à l'intérieur d'une méthode? (b) Les maple leafs = [] déclaration de réserver le tas ou de la pile d'espace de stockage? Parce que je pense que si il se réserve l'espace de pile les feuilles de liste serait point à données aléatoires après la get_leaf_nodes renvoie à droite?
    (a) Non, il n'est pas "propre" à l'approche de la programmation orientée objet, mais pourquoi utiliser python si vous ne voulez pas TOUT le pouvoir à l'intérieur ;), d'ailleurs à partir d'un client du point de vue de votre objet se comporte comme un "nettoyage" de la programmation orientée objet objet (b) leafs = [] crée un nouvel objet de type list et attribuer une référence à la variable leaf alors quand vous revenez vous êtes juste de retour d'une référence à l'objet de la liste, qui python continue le tour jusqu'à ce qu'aucune référence ne pouvait y accéder (python utilise le garbage collector approche de la programmation orientée objet)
    Merci pour votre explication à mes questions. J'aime votre réponse. Je vais attendre pour plus de réponses et puis je ll accepter 🙂
    Vous êtes les bienvenus 🙂

    OriginalL'auteur Alvaro Fuentes

  2. 2

    Cette méthode devrait être suffisant pour obtenir le laisse accessible à partir de n'importe quel nœud, si vous l'appelez, avec la racine de votre arbre, vous obtiendrez toutes les feuilles de l'arbre:

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

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

    OriginalL'auteur avenet

  3. 0

    L'un des bons récursive approche pour trouver des feuilles.

    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()

    OriginalL'auteur technazi

  4. 0

    Je pense que les précédents contributeurs ont répondu à cette question correctement, mais personne n'a vraiment montré comment configurer les nœuds et ajouter ces valeurs à l'arbre, puis de l'exécuter à démontrer qu'il fonctionne en fait tous ensemble. C'est pourquoi je vais répondre à cette question:

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


class Pattern():
    def getLeafs(self,root):
        if not root: 
            return []
        if not root.left and not root.right: 
            return [root.val]
        leaves = self.getLeafs(root.left) + self.getLeafs(root.right)
        return leaves 

    def similar_leaf(self, root1, root2):
        return self.getLeafs(root1) == self.getLeafs(root2)


#simple test 
root= Node(3)
root.left = Node(5)
root.right= Node(1)

root.left.left =  Node(6)
root.left.right =  Node(2)
root.left.right.left =Node(7)
root.left.right.right =Node(4)

root.right.left =  Node(9)
root.right.right =  Node(8)

pattern =Pattern()
print(pattern.similar_leaf(root,root))

    OriginalL'auteur grepit