Implémentation des arbres

Comme pour les listes, il est possible d'implémenter un arbre de plusieurs façons.

Programmation orientée objet

Voici l'implémentation d'un arbre utilisant la programmation orienté objet :

class ArbreBinaire:
    def __init__(self, valeur, gauche = None, droit = None):
        self.valeur = valeur  # Étiquette
        self.gauche = gauche  # Sous-arbre gauche
        self.droit = droit    # Sous-arbre droit

1) Recréez l'arbre suivant en utilisant cette implémentation.

B = ArbreBinaire("B")
D = ArbreBinaire("D", B, None)
K = ArbreBinaire("K")
Z = ArbreBinaire("Z")
E = ArbreBinaire("E", K, Z)
I = ArbreBinaire("I", D, E)

2) Proposez et testez une méthode récursive permettant de calculer la taille de l'arbre.

def taille(self):
    taille = 1 # Le nœud lui-même
    if self.gauche is not None:
        taille = taille + self.gauche.taille()
    if self.droit is not None:
        taille = taille + self.droit.taille()
    return taille

3) Proposez et testez une méthode récursive permettant de calculer la hauteur de l'arbre.

def hauteur(self):
    if self.gauche is None and self.droit is None:
        return 0
    elif self.gauche is None and self.droit is not None:
        return 1 + self.droit.hauteur()
    elif self.gauche is not None and self.droit is None:
        return 1 + self.gauche.hauteur()
    else:
        return 1 + max(self.droit.hauteur(),self.gauche.hauteur())

4) Proposez et testez une méthode récursive permettant de faire le parcours préfixe de l'arbre.

def parcours_prefixe(self):
    print(self.valeur,end='-')
    if self.gauche is not None:
        self.gauche.parcours_prefixe()
    if self.droit is not None:
        self.droit.parcours_prefixe()

5) Proposez et testez une méthode récursive permettant de faire le parcours infixe de l'arbre.

def parcours_infixe(self):
    if self.gauche is not None:
        self.gauche.parcours_infixe()
    print(self.valeur,end='-')
    if self.droit is not None:
        self.droit.parcours_infixe()

6) Proposez et testez une méthode récursive permettant de faire le parcours suffixe de l'arbre.

def parcours_suffixe(self):
    if self.gauche is not None:
       self.gauche.parcours_suffixe()
    if self.droit is not None:
       self.droit.parcours_suffixe()
    print(self.valeur,end='-')

7) Proposez et testez une méthode non récursive permettant de faire le parcours en largeur de l'arbre.

def parcours_largeur(self):
    f = []
    f.append(self)
    while len(f) != 0:
        x = f.pop(0)
        print(x.valeur,end='-')
        if x.gauche is not None:
            f.append(x.gauche)
        if x.droit is not None:
            f.append(x.droit)

Utilisation de tuples

Il n'est pas nécessaire d'utiliser la programmation orientée objet pour implémentter un arbre, on peut simplement utiliser des tuples ou des tableaux. Ainsi, on pourra utiliser des tuples de trois éléments représentant la valeur du nœud, sont sous-arbre gauche et son sous-arbre droit :

noeud = (valeur, arbre.gauche, arbre.droit)

Ainsi, pour représenter cet arbre :

Nous utiliserons le code suivant :

arbre = ('A', ('B', None, None), ('C', None, None))

Vous allez maintenant recréer les algorithmes précedents avec cette implémentation.

8) Recréez l'arbre suivant en utilisant cette implémentation.

arbre = ('I', ('D', ('B', None, None), None), ('E', ('K', None, None), ('Z', None, None)))

9) Proposez et testez une fonction récursive permettant de calculer la taille de l'arbre.

def taille(arbre):
    if arbre is None:
        return 0
    else:
        return 1 + taille(arbre[1]) + taille(arbre[2])

10) Proposez et testez une fonction récursive permettant de calculer la hauteur de l'arbre.

def hauteur(arbre):
    if arbre[1] is None and arbre[2] is None:
        return 0
    elif arbre[1] is None and arbre[2] is not None:
        return 1 + hauteur(arbre[2])
    elif arbre[1] is not None and arbre[2] is None:
        return 1 + hauteur(arbre[1])
    else:
        return 1 + max(hauteur(arbre[1]),hauteur(arbre[2]))

11) Proposez et testez une fonction récursive permettant de faire le parcours préfixe de l'arbre.

def parcours_prefixe(arbre):
    print(arbre[0],end='-')
    if arbre[1] is not None:
        parcours_prefixe(arbre[1])
    if arbre[2] is not None:
        parcours_prefixe(arbre[2])

12) Proposez et testez une fonction récursive permettant de faire le parcours infixe de l'arbre.

def parcours_infixe(arbre):
    if arbre[1] is not None:
        parcours_infixe(arbre[1])
    print(arbre[0],end='-')
    if arbre[2] is not None:
        parcours_infixe(arbre[2])

13) Proposez et testez une fonction récursive permettant de faire le parcours suffixe de l'arbre.

def parcours_suffixe(arbre):
    if arbre[1] is not None:
        parcours_suffixe(arbre[1])
    if arbre[2] is not None:
        parcours_suffixe(arbre[2])
    print(arbre[0],end='-')

14) Proposez et testez une fonction non récursive permettant de faire le parcours en largeur de l'arbre.

def parcours_largeur(arbre):
    f = []
    f.append(arbre)
    while len(f) != 0:
        x = f.pop(0)
        print(x[0],end='-')
        if x[1] is not None:
            f.append(x[1])
        if x[2] is not None:
            f.append(x[2])