Discussion :

[Elisa-Landes]

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 !

[VinsS]

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

[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

[VinsS]

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

[wiztricks]

Salut,

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

[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

[wiztricks]

Salut,

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