Vous devez m'envoyer (en dépôt sur le cahier de texte d'Ecole Directe un fichier nommé NOM_TP_arbres.zip avec NOM votre nom un document texte avec les réponses aux questions numérotées de Q1 à Q10 et les sources de toutes les fonctions Python demandées.
Le squelette du fichier Python source avec les méthodes à compléter est accessible ici : Squelette Python
Chaque fonction doit être documentée en utilisant les docstring
et incluant plusieurs jeux de tests utilisant la bibliothèque doctest
.
Un arbre binaire peut être représenté par les attributs suivants :
nom
fils_gauche
fils_droit
Complétez le corps du constructeur de la classe Arbre
afin de construire un arbre dont la racine a pour nom nom
, avec un sous-arbre gauche vide (fils_gauche = None
) et un sous-arbre droit vide
(fils_droit = None
)
Complétez les corps des méthodes suivantes de la classe Arbre
:
set_nom(self,nom)
: renseigne le nom de la racine de l'arbre avec le paramètre nom
de la méthode;insere_fils_gauche(self, fils_gauche)
: renseigne le sous-arbre gauche de l'arbre avec le paramètre fils_gauche
(de type Arbre
) de la méthode;insere_fils_droit(self, fils_droit)
: renseigne le sous-arbre droit de l'arbre avec le paramètre fils_droit
(de type Arbre
) de la méthode.On considère l'arbre binaire suivant :
En utilisant les méthodes précédentes de la classe Arbre
, compléter le corps de la fonction construit_arbre_exemple()
(qui n'est pas une méthode membre de la classe Arbre
) qui permet de créer et de
retourner une instance de cette classe qui permet de représenter cet arbre.
Vous trouverez dans le squelette Python du TP, une méthode de la classe Arbre
nommée affiche_arbre(self)
qui permet de visualiser graphique en mode texte un arbre binaire.
La bibliothèque Python utilisée se nomme binarytree
et la classe Python utilisée permettant de représenter graphiquement un arbre se nomme Node
.
Testez cette méthode avec l'arbre de l'exemple et vérifiez que vous devez obtenir l'affichage suivant dans la console Python :
Dans le fichier squelette Python, la méthode de la classe Arbre
nommée hauteur(self)
comporte des lignes mises en commentaire avec des parties de code à compléter.
Décommentez les lignes du corps de cette méthode et complétez les parties en pointillés.
Indication : le principe de l'algorithme récursif de cette méthode est basé sur le résultat suivant : la hauteur d'un arbre est égale au maximum des hauteurs de ces différentes branches.
Il existe principalement 3 méthodes récursives de parcours d'un arbre binaire :
Ordre préfixe
Ordre infixe
Ordre postfixe
Ainsi pour l'arbre binaire ci-dessus, voici les 3 parcours :
Complétez le corps des 3 méthodes de la classe Arbre
pour parcourir un arbre binaire qui retournent chacune sous la forme d'une liste le parcours correspondant.
Vérifiez que vos méthodes donnent bien les bons résultats pour les 3 parcours de l'arbre de l'exemple.
parcours_prefixe(self)
parcours_infixe(self)
parcours_postfixe(self)
Un arbre binaire complet est un arbre binaire dont chaque noeud possède 2 fils sauf pour le dernier niveau dont tous les noeuds n'ont aucun fils.
On utilisera la convention suivante : la hauteur d’un arbre binaire ne comportant qu’un noeud est 1.
Voici un exemple d'arbre binaire complet
Donner la hauteur et la taille de cet arbre.
Donner le nombre de noeuds d'un arbre binaire complet de hauteur h
(h étant un entier supérieur ou égal à 1).
Dans le fichier squelette Python, deux méthodes (qui ne sont pas des méthodes de la classe Arbre
) permettent
de construire un arbre binaire complet avec des entiers consécutifs à partir de 1 :
genere_arbre_binaire_complet(hauteur)
: permet de générer un arbre binaire complet de hauteur hauteur
.
genere_arbre_binaire_complet_recur(hauteur,racine,noeud_courant,h=1,no=1)
: méthode récursive permettant de construire l'arbre binaire complet.
Description des paramètres de la méthode genere_arbre_binaire_complet_recur(hauteur,racine,noeud_courant,h=1,no=1)
:
hauteur
: hauteur de l'arbre binaire completracine
: noeud racine de l'arbre binaire complet (son étiquette est le nombre 1) : de type Arbre
noeud_courant
: noeud courant de l'arbre en cours de construction (variable de type Arbre
)h
: hauteur courante de l'arbre en cours de construction (valeur 1 lors du premier appel de la méthode)no
: valeur courante de l'étiquette du noeud courant de l'arbre en cours de construction (valeur 1 lors du premier appel de la méthode)
Ecrire le code de la méthode genere_arbre_binaire_complet_recur(hauteur,racine,noeud_courant,h=1,no=1)
.
Rappel :
Un arbre binaire de recherche est un arbre défini comme suit :
On dispose d'une liste d'entiers. On souhaite construire un arbre binaire de recherche à partir de cette liste et en traitant les clefs à insérer dans l'arbre à partir de l'ordre de la liste.
Exemple : Pour la liste d'entiers suivante : [59, 18, 44, 8, 57, 36, 52, 61]
, l'arbre binaire de recherche construit est celui-ci :
Dans le fichier squelette Python, deux méthodes (qui ne sont pas des méthodes de la classe Arbre
) permettent
de construire un arbre binaire complet avec des entiers consécutifs à partir de 1 :
construit_arbre_binaire_recherche(liste)
: permet de générer un arbre binaire de recherche à partir de la liste de nombres liste
.
insere_arbre_binaire_recherche_recur(nombre,indice,racine,noeud)
: méthode récursive permettant d'insérer une clef (un nombre) au bon endroit dans l'arbre binaire de recherche en cours de construction.
Description des paramètres de la méthode insere_arbre_binaire_recherche_recur(nombre,racine,noeud)
:
nombre
: la clef à insérer dans l'arbre binaire de rechercheracine
: noeud racine de l'arbre binaire de recherche (variable de type Arbre
)noeud
: noeud courant de l'arbre en cours de construction (variable de type Arbre
)
Ecrire le code de la méthode insere_arbre_binaire_recherche_recur(nombre,racine,noeud)
.
Testez votre méthode à partir d'une liste d'entiers générés aléatoirement de taille comprise entre 5 et 10 et en affichant l'arbre binaire de recherche généré à l'aide de la méthode affiche_arbre(self)
de la classe
Arbre
.
Ecrire le code de la méthode recherche_clef_abr(self,clef,nb_etapes=1)
membre de la classe Arbre
qui recherche si la clé clef
est présente dans l'arbre binaire de recherche et retourne :
True,nb_etapes
(nb_etapes étant le nombre d'étapes (cad d'appels récursifs de la méthode))False,None
sinon.Exemple : Pour l'arbre binaire de recherche de l'exemple ci-dessus :
recherche_clef_abr(self,57,nb_etapes=1)
doit retourner True,4
;recherche_clef_abr(self,8,nb_etapes=1)
doit retourner True,3
;recherche_clef_abr(self,59,nb_etapes=1)
doit retourner True,1
;recherche_clef_abr(self,14,nb_etapes=1)
doit retourner False,None
.
Auteur : Hugues Malherbe