Imprimer

 

Objectifs

Consignes

 

 

Classe objet pour représenter un arbre binaire

Un arbre binaire peut être représenté par les attributs suivants :

 

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)

class Arbre():

    def __init__(self,nom):
        pass


 

Complétez les corps des méthodes suivantes de la classe Arbre :

 

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.

 

Représentation graphique d'un arbre binaire en mode texte

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 :

Hauteur d'un arbre binaire

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.

Parcours d'un arbre binaire

Il existe principalement 3 méthodes récursives de parcours d'un arbre binaire :

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.

Arbre binaire complet

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 de hauteur h (h étant un entier supérieur ou égal à 1).

Donner la hauteur et la taille de cet arbre.

Génération d'un arbre binaire complet dont les noeuds sont des entiers naturels consécutifs à partir de 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 :

Ecrire le code de la méthode genere_arbre_binaire_complet_recur(hauteur,racine,noeud_courant,h=1,no=1).

Arbre binaire de recherche

Rappel :

Un arbre binaire de recherche est un arbre défini comme suit :

Kiwi standing on oval

Construction d'un arbre binaire de recherche à partir d'une liste de nombres

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 :

 

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.

Recherche d'une clef dans un arbre binaire de recherche

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 :

Exemple : Pour l'arbre binaire de recherche de l'exemple ci-dessus :

Affichages : 343