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.

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

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

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

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

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

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

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.

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

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

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

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

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

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