¶ Objectif
L’objectif de ce TP est d’implémenter un arbre binaire. Pour cela, nous utiliserons la programmation orientée objet afin de créer une classe Arbre.
On rappelle qu’un arbre binaire est composé de 3 éléments :
- un nœud
- un sous-arbre gauche
- un sous-arbre droit
Dans ce TP, l’arbre vide prendre la valeur None.
¶ Travail à faire
¶ Partie 1 - Une classe Arbre
Question 1 - Créer un nouveau fichier Arbre.py. Ce fichier contiendra la classe Arbre.
Question 2 - Écrire le constructeur de la classe Arbre selon les indications suivantes :
- Le constructeur prendre 3 paramètres :
noeud,gaucheetdroit. - Les paramètres
gaucheetdroitne sont pas obligatoires. S'ils ne sont pas renseignés, leur valeur seraNone(Arbre vide). - Les 3 paramètres permettent d'initialiser les 3 attributs.
>>> a = Arbre('A')
>>> b = Arbre('B')
>>> c = Arbre('C',a,b)
Question 3 - Écrire la méthode __str__. Cette méthode retourne une chaine de caractères représentant un arbre binaire. Elle sera composée de la valeur du noeud, du sous-arbre gauche et du sous-arbre droit.
Cette méthode est récursive et fera appel à la fonction str pour afficher les sous-arbres.
>>> a = Arbre('A', Arbre('B'))
>>> str(a)
'(A,(B,None,None),None)'
Question 4 - Écrire la méthode est_feuille. Cette méthode retourne True si le noeud est une feuille, False sinon.
>>> b = Arbre('b')
>>> a = Arbre('A', b)
>>> a.est_feuille()
False
>>> b.est_feuille()
True
Question 5 - Écrire la méthode get_sous_arbre_gauche. Cette fonction retourne le sous-arbre gauche. S'il est vide, on retournera None.
>>> a = Arbre('A', Arbre('B'))
>>> a.get_sous_arbre_gauche()
Question 6 - Écrire la méthode get_sous_arbre_droit. Cette fonction retourne le sous-arbre droit. S'il est vide, on retournera None.
>>> a = Arbre('A', Arbre('B'))
>>> a.get_sous_arbre_droit()
Question 7 - Écrire la méthode insert_gauche qui prend en paramètre une valeur. Cette méthode permet de définir une valeur au sous-arbre gauche.
Concrètement, elle crée et ajoute un nouveau sous-arbre gauche avec comme noeud la valeur passée en paramètre. Attention, cette opération n'est possible que si le sous-arbre gauche est vide.
>>> a = Arbre('A')
>>> a.insert_gauche(5)
Question 8 - Écrire la méthode insert_droit qui prend en paramètre une valeur. Cette méthode permet de définir une valeur au sous-arbre droit.
Concrètement, elle crée et ajoute un nouveau sous-arbre droit avec comme noeud la valeur passée en paramètre. Attention, cette opération n'est possible que si le sous-arbre droit est vide.
>>> a = Arbre('A')
>>> a.insert_droit(5)
Question 9 - Créer un nouveau fichier main.py.
Question 10 - Dans le fichier main.py, écrire le code nécessaire pour construire l'arbre suivant.
¶ Partie 2 - Les caractéristiques d'un arbre
Question 11 - Dans la classe Arbre, écrire la méthode taille. Cette fonction retourne un nombre entier correspondant à la taille de l'arbre.
- Ce sera une méthode récursive, dans laquelle on fera plusieurs appels récursifs.
- Il faudra bien déterminer les cas de base.
>>> a = Arbre('A', Arbre('B'))
>>> a.taille()
2
Question 12 - Écrire la méthode hauteur. Cette fonction retourne un nombre entier correspondant à la hauteur de l'arbre.
- Ce sera une méthode récursive, dans laquelle on fera plusieurs appels récursifs.
- Il faudra bien déterminer les cas de base.
>>> a = Arbre('A', Arbre('B'))
>>> a.hauteur()
2
¶ Partie 3 - Les différents parcours
Question 13 - Écrire une méthode parcours_largeur. Cette méthode parcourt et affiche chaque noeud de l'arbre en effectuant un parcours en largeur. On utilisera une file.
>>> a = Arbre('A', Arbre('B'))
>>> a.parcours_largeur()
Question 14 - Écrire une méthode parcours_profondeur. Cette méthode parcourt et affiche chaque noeud de l'arbre en effectuant un parcours en profondeur. On utilisera une pile.
>>> a = Arbre('A', Arbre('B'))
>>> a.parcours_profondeur()
Question 15 - Écrire une méthode parcours_prefixe. Cette méthode parcourt et affiche chaque nœud de l’arbre en effectuant un parcours en profondeur préfixe. Cette méthode sera récursive.
>>> a = Arbre('A', Arbre('B'))
>>> a.parcours_prefixe()
Question 16 - Écrire une méthode parcours_infixe. Cette méthode parcourt et affiche chaque nœud de l’arbre en effectuant un parcours en profondeur infixe. Cette méthode sera récursive.
>>> a = Arbre('A', Arbre('B'))
>>> a.parcours_infixe()
Question 17 - Écrire une méthode parcours_postfixe. Cette méthode parcourt et affiche chaque nœud de l’arbre en effectuant un parcours en profondeur infixe. Cette méthode sera récursive.
>>> a = Arbre('A', Arbre('B'))
>>> a.parcours_infixe()
Question 18 - Vérifier les parcours obtenus lors de l'activité 1.
Question 19 - Écrire une méthode recherche. Cette méthode prend en paramètre une variable valeur et retourne True si le paramètre valeur est présent dans l’arbre, False sinon.
>>> a = Arbre('A', Arbre('B'))
>>> a.recherche('B')
True
Question 20 - Écrire la méthode affiche. Cette méthode permet d'afficher un arbre de la manière suivante.
>>> b = Arbre("B", Arbre('D'), Arbre('E'))
>>> c = Arbre("C")
>>> a = Arbre("A",b,c)
>>> a.affiche()
|-->A
|-->B
|-->D
|-->E
|-->C
On ajoute un décalage à gauche supplémentaire pour afficher les nœuds fils.