Implémentation en POO de la taille d'un arbre binaire

Version imprimable

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:

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 !

Salut,

Tu omets de compter le noeud racine "r".
Ton calcul se présente comme ceci:

Code:

Si on totalise les 1 cela fait bien 11.
Ce problème se présente à chaque niveau de l'arbre.

Code:

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

24/10/2020, 08h45
Elisa-Landes

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

Comme ceci, par exemple:

Code:

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

24/10/2020, 10h42
wiztricks
Salut,

Citation:

Envoyé par Elisa-Landes

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:

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
24/10/2020, 13h47
Elisa-Landes

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
24/10/2020, 15h31
wiztricks
Salut,

Citation:

Envoyé par Elisa-Landes

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:

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:

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