Aller au contenu principal

TP1 - Création d'arbres binaires

Objectifs
  1. Comprendre la structure des arbres binaires ;
  2. Manipuler des classes ;
  3. Implémenter des parcours d'arbres.
Pré-requis

Suivre le cours sur les arbres.

  • Créer un dossier Arbres
  • Créer un fichier Classes_Arbre
Documentation

Pour chaque fonction créée, ne pas oublier de la documenter.

Le but de cette première partie est de modéliser un arbre binaire en Python à l’aide de la programmation orientée objet.

Nous allons construire progressivement une classe représentant un nœud binaire, puis implémenter différentes méthodes permettant d’obtenir des informations sur l’arbre et de le parcourir.

Création de la classe NoeudBinaire​

On souhaite définir une classe NoeudBinaire qui servira de base à la construction de nos arbres.

Un nœud binaire est caractérisé par :

  • une valeur stockée dans le nœud ;
  • un fils gauche, qui est soit un autre NoeudBinaire, soit None ;
  • un fils droit, qui est soit un autre NoeudBinaire, soit None.
Structure récursive

Un arbre binaire est une structure récursive :

  • chaque fils est lui-même un arbre binaire ;
  • l’arbre est entièrement représenté par son nœud racine.
  1. Créer la classe NoeudBinaire puis implémenter son constructeur __init__ prenant dans l’ordre :
    • la valeur du nœud (valeur),
    • le fils gauche (fils_gauche),
    • le fils droit (fils_droite).
Afficheur d'arbres

Pour faciliter les tests, une fonction afficher_arbre(arbre) est téléchargeable ici.

  • Placer le fichier afficheur_arbre.py dans le même dossier que votre fichier Python.

  • Importer la fonction en début de fichier :

    from afficheur_arbre import afficher_arbre
  1. Créer l'arbre suivant : et stocker la racine dans une variable nommée arbre_binaire.

Méthodes de classe​

Taille d'un arbre​

La taille d’un arbre binaire correspond au nombre total de nœuds.

  1. Donner la taille de l’arbre arbre_binaire.
Méthode récursive

Pour calculer la taille d’un arbre à partir de sa racine :

  • Compter le nœud courant (1).
  • Ajouter la taille du sous-arbre gauche s’il existe.
  • Ajouter la taille du sous-arbre droit s’il existe.
  1. Implémenter la méthode taille(self) dans la classe NoeudBinaire qui retourne la taille de l’arbre.
  2. Tester la méthode taille sur l’arbre arbre_binaire.

Hauteur d’un arbre​

La hauteur d’un arbre correspond à la profondeur maximale, c’est-à-dire la distance entre la racine et la feuille la plus éloignée.

  1. Donner la hauteur de l’arbre arbre_binaire.
Méthode récursive
  • Calculer la hauteur du sous-arbre gauche s'il existe.
  • Calculer la hauteur du sous-arbre droit s'il existe. -. Retourner 1 + le maximum des hauteurs des deux sous-arbres.
  1. Implémenter la méthode hauteur(self) dans la classe NoeudBinaire qui retourne la hauteur de l’arbre.
  2. Tester la méthode hauteur sur l’arbre arbre_binaire.

Feuilles d’un arbre​

Une feuille est un nœud qui ne possède aucun fils.

  1. Donner le nombre de feuilles de l’arbre arbre_binaire.
  2. Implémenter la méthode est_feuille(self) qui retourne True si le nœud est une feuille, False sinon.
Méthode récursive
  • Si le noeud courant n’a pas de fils → c’est une feuille, on retourne 1.
  • Si le noeud courant a un fils gauche → on calcule le nombre de feuilles du sous-arbre gauche.
  • Si le noeud courant a un fils droit → on calcule le nombre de feuilles du sous-arbre droit.
  • On retourne la somme du nombre de feuilles des sous-arbres gauche et droit.
  1. Implémenter la méthode nombre_feuilles(self) qui retourne le nombre de feuilles de l’arbre.
  2. Tester les méthodes est_feuille et nombre_feuilles sur l’arbre arbre_binaire.

Parcours des arbres binaires​

Le parcours d’un arbre correspond à un ordre de visite des nœuds à partir de la racine.

Nous allons implémenter quatre types de parcours :

  • parcours préfixe ;
  • parcours suffixe ;
  • parcours infixe ;
  • parcours en largeur.

Dans tous les parcours, l’affichage se fait avec print.

Parcours préfixe​

Ordre : racine → gauche → droite

  1. Implémenter la méthode parcours_prefixe(self) qui affiche les nœuds de l’arbre dans l’ordre préfixe.
  2. Tester la méthode parcours_prefixe sur l’arbre arbre_binaire.

Parcours suffixe​

Ordre : gauche → droite → racine

  1. Implémenter la méthode parcours_suffixe(self) qui affiche les nœuds de l’arbre dans l’ordre suffixe.
  2. Tester la méthode parcours_suffixe sur l’arbre arbre_binaire.

Parcours infixe​

Ordre : gauche → racine → droite

  1. Implémenter la méthode parcours_infixe(self) qui affiche les nœuds de l’arbre dans l’ordre infixe.
  2. Tester la méthode parcours_infixe sur l’arbre arbre_binaire.

Parcours en largeur​

Le parcours en largeur visite les nœuds niveau par niveau.

Structure et méthode

Ce parcours utilise une file (FIFO).

Principe :

  1. Mettre la racine dans la file.
  2. Tant que la file n’est pas vide :
    • retirer un nœud et l’afficher ;
    • ajouter ses fils dans la file.
  1. Importer la classe File (du TP précédent).
  2. Implémenter la méthode parcours_largeur(self) qui affiche les nœuds de l’arbre dans l’ordre du parcours en largeur.
  3. Tester la méthode parcours_largeur sur l’arbre arbre_binaire.