Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Candidat au Club
    Implémentation en POO de la taille d'un arbre binaire
    Bonjour,
    Je n'arrive pas à trouver où j'ai fait une erreur dans mon script. Mon arbre binaire a une taille de 12 or mon script me donne 11.

    Code Python :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
     
    class Noeud:
        # Le constructeur
        def __init__(self, value, left=None, right=None):
            self.value = value
            self.left = left
            self.right = right
     
        # Méthode qui permet d’afficher la valeur
        # de la racine avec la fonction print
        def __str__(self):
            return str(self.value)
     
        # méthode taille de l'arbre
        def taille(self):
            t1 = 0
            t2 = 0
            if not self:
                return 0
            else:
                if self.left:
                    t1 = 1 + self.left.taille()
                if self.right:
                    t2 = 1 + self.right.taille()
                return t1 + t2
     
    arbre = Noeud('r',\
                Noeud('a',\
                  Noeud('c', None, Noeud('h')),\
                  Noeud('d',Noeud('i'),\
                        Noeud('j',Noeud('m'), None))),\
                Noeud('b',\
                  Noeud('e', Noeud('k'), None),\
                  Noeud('f'))\
                )
     
    print(arbre) # affiche r
    print("la taille de l'arbre est : ", end='')
    print(arbre.taille())


    Un grand merci !

  2. #2
    Expert éminent
    Salut,

    Tu omets de compter le noeud racine "r".
    Ton calcul se présente comme ceci:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
     
    r = 1 + a
        1 + b
    a = 1 + c
        1 + d
    b = 1 + e
        1 + f
    c = 1 + h
        0
    d = 1 + i
        1 + j
    e = 1 + k
        0
    f = 0
        0
    i = 0
        0
    j = 1 + m
        0
    k = 0
        0
    m = 0
        0

    Si on totalise les 1 cela fait bien 11.
    Ce problème se présente à chaque niveau de l'arbre.
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    print(arbre) # affiche r
    print("la taille de l'arbre est : ", end='')
    print(arbre.taille())
    # "a" = a+c+d+h+i+j+m = 7 print 6 !
    print(arbre.left.taille())
    # "d" = d+i+j+m = 4 print 3 !
    print(arbre.left.right.taille())

  3. #3
    Candidat au Club
    Bonjour,

    Je m'en doutais mais je ne vois pas comment modifier le code pour qu'il comptabilise un seule fois la racine et non récursivement à chaque sous-arbre

    Merci

  4. #4
    Expert éminent
    Comme ceci, par exemple:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
        def taille(self, root=1):
            t1 = root
            t2 = 0
            if not self:
                return 0
            else:
                if self.left:
                    t1 += 1 + self.left.taille(0)
                if self.right:
                    t2 = 1 + self.right.taille(0)
                return t1 + t2

  5. #5
    Expert éminent sénior
    Salut,

    Citation Envoyé par Elisa-Landes Voir le message
    Je m'en doutais mais je ne vois pas comment modifier le code pour qu'il comptabilise un seule fois la racine et non récursivement à chaque sous-arbre
    Si on veut compter le nombre de nœuds avec une fonction récursive, on écrira:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    def taille(arbre):
        if arbre is None:
            return 0
        return 1 + taille(arbre.left) + taille(arbre.right)


    Simple et efficace...

    Ça dit juste qu'un arbre n'est pas qu'un tas de feuilles: d'où les jongleries glissantes pour faire de cette fonction une méthode (de feuille)...

    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  6. #6
    Candidat au Club
    Un grand merci, justement c'était pour pouvoir faire comparer la fonction récursive avec une méthode à mes élèves et ainsi en déduire les avantages et les inconvénients.
    merci encore

  7. #7
    Expert éminent sénior
    Salut,

    Citation Envoyé par Elisa-Landes Voir le message
    c'était pour pouvoir faire comparer la fonction récursive avec une méthode à mes élèves et ainsi en déduire les avantages et les inconvénients.
    C'est juste un point de vue différent qui modifie la condition permettant la descente récursive.

    On ne peut pas transposer en remplaçant arbre par self:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
        def taille(self):
             if self is None:
                 return 0

    Car self ne peut être égal à None.
    Il va falloir tester l'existence de fils avant de descendre:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
       def taille(self):
            s = 1
            for n in (self.left, self.right):
                if n is not None:
                    s += n.taille()
            return s


    - W
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

###raw>template_hook.ano_emploi###