Bonjour,

je suis entrain de faire un programme sur les arbres binaire AVL .

class noeud:

    def __init__(self,racine,filsGauche,filsDroit):

        self.r = racine                                                  # Nom du noeud  de l'arbre.
        self.g = filsGauche                                              # Nom du fils gauche de la racine.   ( Les fils droit et gauche sont aussi des noeuds )    
        self.d = filsDroit                                               # Nom du fils droit de la racine.                 
        self.h = 1 + max( Hauteur(filsGauche) , Hauteur(filsDroit) )     # Hauteur des sous-arbres (droite et gauche).


def arbre(a): # Construit un arbre avec de la forme  ["nom de la racine" , [le sous-arbre gauche] , [le sous arbre droit ], int(la hauteur de la racine)]
    
    if test_vide(a):
        res=None

    else:
        res=[]
        res.append(a.r)
        res.append(arbre(a.g))
        res.append(arbre(a.d))

    return res
                   
        

def Hauteur(a):

    res = -1  # On considérera par défaut que l'arbre est vide.
    
    if (test_vide(a)!=False):
        res = a.h

    return res

def calculHauteur(a):

    a.h = 1 + max( Hauteur(a.g) , Hauteur(a.d) )
        
    
    
        
 
def test_vide(a): # Retourne vrai si l'arbre est vide , faux s'il ne l'ai pas.   
    
    vide=False    
    if (a.r == None):        
        vide=True        
    return vide 






#------------------ Exemple  -------------------------------

c=noeud("c",None,None)
e=noeud("e",None,None)
d=noeud("d",None,None)
b=noeud("b",d,e)
a=noeud("a",b,c)

vide=noeud(None,None,None)

et j'ai deux erreurs qui je n'arrive pas à corriger

Traceback (most recent call last):
  File "C:/Users/utilisateur/Desktop/AVL.pyw", line 79, in <module>
    c=noeud("c",None,None)
  File "C:/Users/utilisateur/Desktop/AVL.pyw", line 30, in __init__
    self.h = 1 + max( Hauteur(filsGauche) , Hauteur(filsDroit) )     # Hauteur des sous-arbres (droite et gauche).
  File "C:/Users/utilisateur/Desktop/AVL.pyw", line 52, in Hauteur
    if (test_vide(a)==False):
  File "C:/Users/utilisateur/Desktop/AVL.pyw", line 68, in test_vide
    if (a.r == None):
AttributeError: 'NoneType' object has no attribute 'r'

Salut,

Je ne crois pas que ton erreur vienne de ce morceau de code. Pourrai-tu en ajouter stp?

Bonjour,

C'est tout le code

Ce n'est donc pas le même code. Dans ton erreur, on voit un if (test_vide(a)==False): qu'on ne retrouve pas dans ton code.

Sinon, voici ton erreur:

#Suivons le cheminement

#Ton premier noeud c:
c = noeud("c", None, None)

#Tu définit ainsi c.h:
c.h = 1 + max(Hauteur(None), Hauteur(None))

#Dans ta fonction Hauteur, tu utilise la fonction test_vide(a) en remplaçant 
#a par None:
vide=False
if (None.r == None):        
        vide=True        
    return vide

#Or None n'a pas d'attribut r, d'où ton erreur

Sinon quelques petites remarques:

class Noeud:  #1ère lettre en majuscule

    def __init__(self,racine,filsGauche,filsDroit):

        self.r = racine
        self.g = filsGauche
        self.d = filsDroit
        #Par contre pas de 1ère lettre en majuscule pour les fonctions
        self.h = 1 + max( hauteur(filsGauche) , hauteur(filsDroit) )


def hauteur(a):

    res = -1

    if not test_vide(a):  # mieux que: (test_vide(a)==False)
        res = a.h

    return res


def test_vide(a):

    vide=False
    if not a.r:  #equivalent à (a.r == None)
        vide=True
    return vide

Sinon, pour essayer de contourner ton problème, tu pourrais ajouter une condition dans ton if:

def test_vide(a):

    vide=False
    if not a or not a.r:  #Si a == None ou a.r == None:
        vide=True
    return vide

Bonjour,

En fait je voulais crée une fonction qui prend en paramètre un arbre a et qui compare sa racine r  avec None puisque que si la racine est vide alors il n'y a pas de nœud et donc pas d'arbre , un arbre vide est modélisé par  vide = noeud = (None,None,None) 

donc je fais a.r pour avoir la racine .

"En fait je voulais crée une fonction qui prend en paramètre un arbre a et qui compare sa racine r  avec None"

Oui, et c'est là d'où provient ton erreur. Car certaines fois tu as mis comme arbre un objet None: c = ("c", None, None). Tu considère à ce moment que None est un arbre. C'est dans la fonction test_vide() que tu considère cela en essayant de prendre l'attribut r de None (regarde mon message précédent, le premier bloc t'explique le cheminement du problème).

j'ai cette erreur avec votre modification

f = noeud("f",None,None)

def test_vide(a):
 
    vide=False
    if not a or not a.r:  #Si a == None ou a.r == None:
        vide=True
    return vide


Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    test_vide(f)
  File "C:\Users\Idriss\Desktop\s1\AVL.pyw", line 84, in test_vide
    if not a or not a.r:  #Si a == None ou a.r == None:
AttributeError: 'tuple' object has no attribute 'r'

Oui, parce que là tu as mis f dans test_vide(). Ce n'est pas f mais ses éléments qu'il faut vérifier.

Ok, reprenons: Tu définis une classe noeud() qui va avoir 4 attributs: racine, filsGauche, filsDroit et h. Les 3 premiers attributs ne posent pas de problèmes puisqu'indépendant.

Par contre, l'attribut h va utiliser la fonction Hauteur() sur les 2 attributs filsGauche et filsDroit. Autrement dit, quand tu fais: c = noeud("c", None, None) ton filsGauche sera égal à None et ton filsDroit aussi. Donc dans ta fonction Hauteur, ce sera None que tu mettra comme paramètre: Hauteur(None).

Jusque là pas de souci. Or dans ta fonction Hauteur(), tu utilise une autre fonction. La fonction qui regarde si l'arbre est vide: test_vide(). Et le paramètre de cette fonction c'est toujours filsGauche ou filsDroit qui sont égale à None. Donc ce que tu teste c'est test_vide(None).

C'est là d'où provient ton erreur. None n'a pas d'attribut r, car None n'est pas une instance de ta classe noeud(). C'est pour cela que j'ai rajouté la condition if a==None.

Après je ne sais pas si ça correspond à ce que tu veux faire. Peut-être faudrait-il à la place que tu créé un objet noeud vide qui remplacera le None.

Donc je crée un model de noeud qui est vide et je le compare avec un arbre a pour savoir si a est vide ou non.

pour le model de la feuille comment pourrais je faire ? , puisqu'en plus de comparer les fils droit et gauche , il comparera la racine , comment puis je faire pour qu'il ne comparaisse que les fils droit et gauche

Bonjour,

Ca marche, j'ai fais ceci :

vide = noeud(None,None,None)
c=noeud("c",vide,vide)
e=noeud("e",vide,vide)
d=noeud("d",vide,vide)
b=noeud("b",d,e)
a=noeud("a",b,c)

def test_vide(a):

    vide = False
    if ( (a == None) or (a.r == vide) ):
        vide = True

    return vide

def test_feuille(a):

    feuille = False
    if ( test_vide(a) == False ):
        if ( (a.g == vide) and (a.d == vide) ):
            feuille = True

    return feuille

mais j'ai une erreur avec hauteur ,

    vide = noeud(None,None,None)
  File "C:\Users\Idriss\Desktop\s1\AVL.pyw", line 30, in __init__
    self.h = 1 + max( hauteur(filsGauche) , hauteur(filsDroit) )     # Hauteur des sous-arbres (droite et gauche).
  File "C:\Users\Idriss\Desktop\s1\AVL.pyw", line 54, in hauteur
    res = a.h
AttributeError: 'NoneType' object has no attribute 'h'

class noeud:

    def __init__(self,racine,filsGauche,filsDroit):

        self.r = racine                                                  # Nom du noeud  de l'arbre.
        self.g = filsGauche                                              # Nom du fils gauche de la racine.   ( Les fils droit et gauche sont aussi des noeuds )    
        self.d = filsDroit                                               # Nom du fils droit de la racine.                 
        self.h = 1 + max( hauteur(filsGauche) , hauteur(filsDroit) )     # Hauteur des sous-arbres (droite et gauche).
        

def hauteur(a):

    res = -1  # On considére par défaut que l'arbre est vide.
    
    if (test_feuille(a) == False):
        res = a.h

    return res

def calculHauteur(a):

    a.h = 1 + max( hauteur(a.g) , hauteur(a.d) )

-
Edité par soraka 23 septembre 2014 à 10:49:24