Probléme Arbre Binaire

Version imprimable

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

Voici mon code:
Code:

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.:aie:

Bonjour,

Comme ça, ça marche:

Code:

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

Tyrtamos

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

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
#! /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:

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:

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.

30/08/2010, 15h10
sopsag

Citation:

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...

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

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
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:

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

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:

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