Implémentation en python d'un arbre binaire

In [27]:
class Noeud:
    """
    Classe permettant de construire un arbre binaire.
    atributs : valeur, enfant gauche, enfant droit
    """
    # Constructeur (un arbre possède à minima un noeud)
    def __init__(self, valeur):
        self.valeur = valeur
        self.enfant_gauche = None
        self.enfant_droit = None

    # méthodes de création des enfants
    def insert_gauche(self, valeur):
        if self.enfant_gauche == None:
            self.enfant_gauche = Noeud(valeur)
        else:
            new_node = Noeud(valeur)
            new_node.enfant_gauche = self.enfant_gauche
            self.enfant_gauche = new_node

    def insert_droit(self, valeur):
        if self.enfant_droit == None:
            self.enfant_droit = Noeud(valeur)
        else:
            new_node = Noeud(valeur)
            new_node.enfant_droit = self.enfant_droit
            self.enfant_droit = new_node

    def get_valeur(self):
        """getter de la valeur du noeud"""
        return self.valeur

    # méthodes pour l'affichage
    def get_gauche(self):
        """getter du sous arbre de gauche du noeud en cours"""
        return self.enfant_gauche

    def get_droit(self):
        """getter du sous arbre de droit du noeud en cours"""
        return self.enfant_droit

# Afficher un arbre
def affiche(arbre):
    if arbre != None:
        return (arbre.get_valeur(), affiche(arbre.get_gauche()), affiche(arbre.get_droit()) )

# fonction hauteur
def hauteur(arbre):
    if arbre != None:
        x = arbre
        return 1 + max(hauteur(x.enfant_gauche), hauteur(x.enfant_droit))
    else:
        return 0

# fonction taille
def taille(arbre):
    if arbre != None:
        x = arbre
        return 1 + taille(x.get_gauche()) + taille(x.get_droit())
    else:
        return 0  

# Parcours infixe
def parcours_infixe(arbre):
    """
    Affiche le parcours Infixe d'un arbre
    """
    if arbre != None:
        x = arbre
        parcours_infixe(x.get_gauche())
        print(' -', x.valeur, end='')
        parcours_infixe(x.get_droit())
        
def parcours_prefixe(arbre):
    """
    Affiche le parcours Prefixe d'un arbre
    """
    if arbre != None:
        x = arbre
        print(' -', x.valeur, end='')
        parcours_prefixe(x.get_gauche()) 
        parcours_prefixe(x.get_droit())
        
def parcours_suffixe(arbre):
    """
    Affiche le parcours Suffixe d'un arbre
    """
    if arbre != None:
        x = arbre       
        parcours_suffixe(x.get_gauche()) 
        parcours_suffixe(x.get_droit())
        print(' -', x.valeur, end='')
        

def parcours_largeur(arbre):
    """
    Affiche le parcours en largeur d'un arbre avec un programme itératif
    """
    if arbre != None:
        # On initialise la file avec l'arbre
        file = []
        file.append(arbre)
        while len(file) > 0:
            x = file.pop(0)
            print(' -', x.valeur, end='')
            if x.get_gauche() != None:
                file.append(x.get_gauche())
            if x.get_droit() != None:
                file.append(x.get_droit())
                
def parcours_largeur_rec(arbre):
    """
    Affiche le parcours en largeur d'un arbre avec un programme recursif
    """
    if arbre != None:
        h = hauteur(arbre)
        for i in range(1, h+1):
            affiche_niveau(arbre, i)
        
def affiche_niveau(arbre, niveau):
    if arbre != None:
        x = arbre
        if niveau == 1:
            print(' -', x.valeur, end='')
        else:
            affiche_niveau(x.get_gauche(), niveau - 1)
            affiche_niveau(x.get_droit(), niveau - 1)

Exemple 1 : arbre de la vidéo

In [26]:
# Création de la racine
racine = Noeud('A')
racine.insert_gauche('B')
racine.insert_droit('C')

# En partant de la racine. Création des enfants gauche et droit

b_node = racine.get_gauche()
b_node.insert_gauche('D')
b_node.insert_droit('E')

c_node = racine.get_droit()
c_node.insert_gauche('F')
c_node.insert_droit('G')

e_node = b_node.get_droit()
e_node.insert_gauche('H')
e_node.insert_droit('I')

i_node = e_node.get_droit()
i_node.insert_gauche('N')
i_node.insert_droit('O')

f_node = c_node.get_gauche()
f_node.insert_gauche('J')
f_node.insert_droit('K')

g_node = c_node.get_droit()
g_node.insert_gauche('L')
g_node.insert_droit('M')

m_node = g_node.get_droit()
m_node.insert_gauche('P')
m_node.insert_droit('Q')

######fin de la construction de l'arbre binaire###########

# Affichage de l'arbre
print('hauteur = ', hauteur(racine))
print('taille = ', taille(racine))
print('Parcours infixe')
parcours_infixe(racine)
print()
print('Parcours prefixe')
parcours_prefixe(racine)
print()
print('Parcours suffixe')
parcours_suffixe(racine)
print()
print('Parcours en largeur')
parcours_largeur(racine)
print()
print('Parcours en largeur recursif')
parcours_largeur_rec(racine)

hauteur =  5
taille =  17
Parcours infixe
 - D - B - H - E - N - I - O - A - J - F - K - C - L - G - P - M - Q
Parcours prefixe
 - A - B - D - E - H - I - N - O - C - F - J - K - G - L - M - P - Q
Parcours suffixe
 - D - H - N - O - I - E - B - J - K - F - L - P - Q - M - G - C - A
Parcours en largeur
 - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q
Parcours en largeur recursif
 - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q

Exemple 2 : arbre 1

In [25]:
######début de la construction de l'arbre binaire###########

arbre1_racine = Noeud('A')
arbre1_racine.insert_gauche('B')
arbre1_racine.insert_droit('F')

b_node = arbre1_racine.get_gauche()
b_node.insert_gauche('C')
b_node.insert_droit('D')

f_node = arbre1_racine.get_droit()
f_node.insert_gauche('G')
f_node.insert_droit('H')

c_node = b_node.get_gauche()
c_node.insert_droit('E')

g_node = f_node.get_gauche()
g_node.insert_gauche('I')

h_node = f_node.get_droit()
h_node.insert_droit('J')

######fin de la construction de l'arbre binaire###########

# Affichage de l'arbre
print('Arbre : ', affiche(arbre1_racine))
# Affichage de l'arbre

print('hauteur = ', hauteur(arbre1_racine))
print('taille = ', taille(arbre1_racine))
print('Parcours infixe')
parcours_infixe(arbre1_racine)
print()
print('Parcours prefixe')
parcours_prefixe(arbre1_racine)
print()
print('Parcours suffixe')
parcours_suffixe(arbre1_racine)
print()
print('Parcours en largeur')
parcours_largeur(arbre1_racine)
print()
print('Parcours en largeur recursif')
parcours_largeur_rec(arbre1_racine)

Arbre :  ('A', ('B', ('C', None, ('E', None, None)), ('D', None, None)), ('F', ('G', ('I', None, None), None), ('H', None, ('J', None, None))))
hauteur =  4
taille =  10
Parcours infixe
 - C - E - B - D - A - I - G - F - H - J
Parcours prefixe
 - A - B - C - E - D - F - G - I - H - J
Parcours suffixe
 - E - C - D - B - I - G - J - H - F - A
Parcours en largeur
 - A - B - F - C - D - G - H - E - I - J
Parcours en largeur recursif
 - A - B - F - C - D - G - H - E - I - J
In [ ]: