Activité Term NSI : Arbres binaires

Objectifs

• Etre capable de modéliser en Python un arbre binaire en utilisant une classe objet;
• Implémenter en Python des algorithmes récursifs de parcours d'arbres binaires;
• Calculer la hauteur d'un arbre binaire;
• Construire un arbre binaire complet;
• Construire un arbre binaire de recherche à partir d'une liste;
• Rechercher une clef dans un arbre binaire de recherche.

Consignes

• Vous devez répondre aux questions indiquées en couleur bleue.

• Vous devez m'envoyer (en dépôt sur le cahier de texte d'Ecole Directe ou si ce n'est pas possible par mail à Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser.) un fichier nommé NOM1_NOM2_TP_arbres.zip avec NOM1,NOM2 les noms des élèves du groupe qui un document texte avec les réponses aux questions numérotées de Q1 à Q12 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.

Classe objet pour représenter un arbre binaire

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

• le nom de sa racine : nom
• son sous-arbre gauche (ou None si l'arbre ne possède pas de sous-arbre gauche) : fils_gauche
• son sous-arbre droit (ou None si l'arbre ne possède pas de sous-arbre droit) : 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)

class Arbre():

    def __init__(self,nom):
        pass

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.

• 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.

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 :

• Ordre préfixe

  1. On affiche le noeud visité;
  2. On visite le fils gauche si il existe;
  3. On visite le fils droit si il existe.

• Ordre infixe

  1. On visite le fils gauche si il existe;
  2. On affiche le noeud visité;
  3. On visite le fils droit si il existe.

• Ordre postfixe

  1. On visite le fils gauche si il existe;
  2. On visite le fils droit si il existe;
  3. On affiche le noeud visité.

Ainsi pour l'arbre binaire ci-dessus, voici les 3 parcours :

• Ordre préfixe : 10 - 8 - 3 - 15 - 20 - 5 - 4
• Ordre infixe : 3 - 8 - 20 - 15 - 10 - 4 - 5
• Ordre postfixe : 3 - 20 - 15 - 8 - 4 - 5 - 10

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)

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 :

• 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 complet
  • racine : 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).

Arbre binaire de recherche

Rappel :

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

• Les étiquettes des noeuds sont appelées des clé.
• Les clés de tous les noeuds d'un sous-arbre gauche d'un noeud X sont inférieures ou égales à la clé de X.
• Les clés de tous les noeuds d'un sous-arbre droit d'un noeud X sont strictement supérieures à la clé de X.

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 :

• 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 recherche
  • racine : 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.

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 :

• 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 :

• L'appel à la méthode recherche_clef_abr(self,57,nb_etapes=1) doit retourner True,4;
• L'appel à la méthode recherche_clef_abr(self,8,nb_etapes=1) doit retourner True,3;
• L'appel à la méthode recherche_clef_abr(self,59,nb_etapes=1) doit retourner True,1;
• L'appel à la méthode recherche_clef_abr(self,14,nb_etapes=1) doit retourner False,None.