Discussion :

[stitch974]

Bonjour à tous,
j'ai un petit problème et je ne comprends pas.

Voici mon code:

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
class Noeud:
    def __init__(self,rac=None):
        self.rac=rac
        self.fg=None
        self.fd=None
 
def insere(abr,e):
    if(abr==None):
        abr=Noeud(e) # :aie:
    else:
        if(abr.rac>=e):
            insere(abr.fg,e)
        else:
            insere(abr.fd,e)
 
b=Noeud(7)
print(b.rac)
print(b.fg,b.fd)
insere(b,-545)
insere(b,341)

Le problème étant que le noeud fraîchement créé n'est pas ajouté à l'arbre binaire.

[tyrtamos]

Bonjour,

Comme ça, ça marche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
def insere(abr, e):
    if abr.rac>=e:
        abr.fg = Noeud(e)
    else:
        abr.fd = Noeud(e)

Tyrtamos

[rambc]

Bonjour,
la solution de Tyrtamos fonctionne. Ceci donne le code suivant où j'ai ajouté une impression très basique de l'arbre :

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
24
25
26
27
28
29
30
31
32
33
34
#! /usr/bin/env python3
 
class Noeud:
    def __init__(self,rac=None):
        self.rac=rac
        self.fg=None
        self.fd=None
 
    def __str__(self):
        return self._strPerso(self)
 
    def _strPerso(self, abr, depth = 0):
        if abr:
            decal = '\n' + '\t'*depth
            depth += 2
            return decal + 'rac: ' + str(abr.rac) + decal + '\tfg: ' + self._strPerso(abr.fg, depth) + decal + '\tfd: ' + self._strPerso(abr.fd, depth)
        else:
            return 'Pas de fils'
 
def insere(abr, e):
    if abr.rac>=e:
        abr.fg = Noeud(e)
    else:
        abr.fd = Noeud(e)
 
 
b=Noeud(7)
print(b)
 
print('', '-'*10, sep="\n")
 
insere(b,-545)
insere(b,341)
print(b)

Le code précédent renvoie :

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
rac: 7
	fg: Pas de fils
	fd: Pas de fils
 
----------
 
rac: 7
	fg: 
		rac: -545
			fg: Pas de fils
			fd: Pas de fils
	fd: 
		rac: 341
			fg: Pas de fils
			fd: Pas de fils

J'aurais tendance avec ce genre d'objet à faire du purement objet de la façon suivante :

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
24
25
26
27
28
29
30
31
32
33
34
35
36
#! /usr/bin/env python3
 
# SOURCE :
#    http://www.developpez.net/forums/d969239/autres-langages/python-zope/general-python/probleme-arbre-binaire
 
class Noeud:
    def __init__(self,rac=None):
        self.rac=rac
        self.fg=None
        self.fd=None
 
    def insere(self, e):
        if self.rac>=e:
            self.fg = Noeud(e)
        else:
            self.fd = Noeud(e)
 
    def __str__(self):
        return self._strPerso(self)
 
    def _strPerso(self, abr, depth = 0):
        if abr:
            decal = '\n' + '\t'*depth
            depth += 2
            return decal + 'rac: ' + str(abr.rac) + decal + '\tfg: ' + self._strPerso(abr.fg, depth) + decal + '\tfd: ' + self._strPerso(abr.fd, depth)
        else:
            return 'Pas de fils'
 
b=Noeud(7)
print(b)
 
print('', '-'*10, sep="\n")
 
b.insere(-545)
b.insere(341)
print(b)

Il serait bien que la méthode insere gère l'ajout d'un arbre comme noeud.

Sur ce, le vélo m'appelle.

[sopsag]

Comme ça, ça marche:

Bé oui, mais ce n'est pas très récursif ce truc...
Tu ne peux ajouter un élément de profondeur 2.

stitch974, ton problème vient de ce lors de l'appel insere(abr.fg,e), ton abr.fg vaut None et que None n'est pas mutable.
C'est à dire que si tu passes None à une fonction qui le modifie ce paramètre, tu retrouveras None à la sortie.

Je te suggère une approche plus objet...

[sopsag]

Voici ce que je voulais dire par "approche objet" :

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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Noeud:
    def __init__( self,rac = None ):
        self.rac = rac
        self.fg  = None
        self.fd  = None
 
    def insere (self,e):
        if self.rac != None :
            if ( self.rac >= e ) :
                if self.fg : 
                    self.fg.insere( e )
                else:
                    self.fg = Noeud( e )
            else:
                if self.fd : 
                    self.fd.insere( e )
                else:
                    self.fd = Noeud( e )
        else:
            self.rac = e
 
    def trace (self,prof=0):
        if self.rac :
            print ' '*prof*3,self.rac
            if self.fg : 
                self.fg.trace( prof+1 )
            else:
                print ' '*(prof+1)*3,'*'
            if self.fd : 
                self.fd.trace( prof+1 )
            else:
                print ' '*(prof+1)*3,'*'
 
a = Noeud()
for i in ( 45,25,60,15,35,55,65,10,20,30,40,50 ):
    a.insere( i )
a.trace()

et ça donne ça :

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
24
25
 45
    25
       15
          10
             *
             *
          20
             *
             *
       35
          30
             *
             *
          40
             *
             *
    60
       55
          50
             *
             *
          *
       65
          *
          *

pas très lisible, je te l'accorde, mais ça permet de vérifier.

[dividee]

Une solution plus "fonctionnelle", dans le sens qu'elle ne modifie pas l'arbre existant mais retourne un nouvel arbre à chaque fois. Un arbre immutable donc:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Noeud:
    def __init__(self, rac=None, fg=None, fd=None):
        self.rac = rac
        self.fg = fg
        self.fd = fd
 
def insere(abr,e):
    if abr == None:
        return Noeud(e)
    else:
        if abr.rac >= e:
            return Noeud(abr.rac, insere(abr.fg, e), abr.fd)
        else:
            return Noeud(abr.rac, abr.fg, insere(abr.fg, e))