#!/usr/bin/env python # coding: utf-8 # # Algorithmes sur les arbres binaires # > Cours NSI Terminale - Thème 5. # - toc: true # - badges: true # - comments: false # - categories: [python, NSI, Terminale, Arbres binaires, Algorithmique, POO, TP] # - image: images/nsi5.png # ## Algorithmes sur les arbres # # Dans ce classeur, nous allons mettre en oeuvre les algorithmes vus en cours. Nous partirons de deux classes : # - Noeud permettant de décrire la structure d'un noeud dans un arbre binaire # - Arbrebin qui est l'arbre proprement dit. Il se caractérise par # - sa racine qui est un Noeud # - des méthodes pour peupler cet arbre et l'afficher sous forme graphique # - des méthodes que vous allez construire pour mettre le cours en pratique # # ### Découverte des classes de base # # Validez les cellules suivantes et analysez bien la structure proposée. # In[ ]: from graphviz import Digraph # In[ ]: class Noeud(): """Représente un noeud dans un arbre binaire - Propriétés : * valeur : valeur du noeud * gauche : noeud gauche ou None * droit : noeud droit ou None - Méthodes : * est_feuille() * __repr__() : affichage d'un noeud""" def __repr__(self): """la méthode __repr__ définit ce qui sera affiché lorsqu'on tapera l'objet dans Jupyter ou un terminal Ici, on affiche juste la valeur du noeud""" return str(f"## {self.valeur} ##") def __init__(self,valeur): self.valeur = valeur self.gauche = None self.droit = None def est_feuille(self): """Renvoie un booleen selon que le noeud est une feuille""" return self.gauche is None and self.droit is None # In[ ]: class Arbrebin: """Représente un objet arbre binaire - Propriétés : * racine : objet de type Noeud désignant la racine de l'arbre - Méthodes : * show() : représentation graphique de l'arbre à l'aide de graphviz """ def __init__(self, nd = None): # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel self.racine = nd def importe(self, tableau): """Importe un arbre depuis un tableau ["Noeud", [S_A_G], [S_A_D]] [ ] désigne un arbre vide""" def importe_tableau(tableau): # Cas particuliers if tableau == []: return None if len(tableau) == 1: return Noeud(tableau[0]) # tableau a une longueur >= 2 nd = Noeud(tableau[0]) nd.gauche = importe_tableau(tableau[1]) nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None return nd self.racine = importe_tableau(tableau) def show(self): """Renvoie un objet graphviz pour la visualisation graphique de l'arbre""" def representation(dot, noeud, aretes): # Ajoute la représentation du noeud à la représentation dot de l'arbre if noeud is not None: dot.node(str(id(noeud)), str(noeud.valeur)) # Appel récursif de la fonction representation if noeud.gauche is not None: representation(dot, noeud.gauche, aretes) aretes.append((str(id(noeud)) , str(id(noeud.gauche)))) if noeud.droit is not None: representation(dot, noeud.droit, aretes) aretes.append((str(id(noeud)) , str(id(noeud.droit)))) dot = Digraph(comment="Arbre binaire", format='svg') aretes = [] representation(dot, self.racine, aretes) dot.edges(aretes) return dot # Regardons notre classe en action : Nous allons recréer l'arbre exemple du cours. # In[ ]: # On crée la structure d'arbre à l'aide d'un tableau ["Noeud", [S_A_G], [S_A_D]] arbre_liste = ["A", ["B", ["C",[],["E"]], ["D"]], ["F", ["G", ["I"]], ["H",["J", ["K"]]] ], ] # In[ ]: # On crée une instance vide de notre arbre arbre = Arbrebin() # On importe le tableau ci-dessus arbre.importe(arbre_liste) # In[ ]: # On visualise l'arbre graphiquement arbre.show() # ### Taille et Hauteur d'un arbre # # Nous allons ajouter nos premières méthodes personelles à la classe **Arbrebin**. Commençons par la taille de l'arbre. Nous avons conçu un algorithme récursif en cours se basant sur le principe que la taille d'un arbre est égal à 1 + la taille du Sous Arbre Gauche + la taille du Sous Arbre Droit. Voici une implémentation de cet algorithme dans la classe **Arbrebin**, elle vous servira de modèle pour les autres méthodes que vous aurez à implémenter dans ce TD. # # Vous remarquerez que pour éviter la multiplication des méthodes, nous créons une **fonction locale** `taille_arbre` qui n'est visible que dans la méthode `taille`. C'est cette fonction qui implémente en réalité l'algorithme, la méthode n'étant là que pour invoquer la fonction `taille_arbre` sur la racine de l'arbre. # In[ ]: class Arbrebin: """Représente un objet arbre binaire - Propriétés : * racine : objet de type Noeud désignant la racine de l'arbre - Méthodes : * show() : représentation graphique de l'arbre à l'aide de graphviz """ def __init__(self, nd = None): # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel self.racine = nd def importe(self, tableau): """Importe un arbre depuis un tableau ["Noeud", [S_A_G], [S_A_D]] [ ] désigne un arbre vide""" def importe_tableau(tableau): # Cas particuliers if tableau == []: return None if len(tableau) == 1: return Noeud(tableau[0]) # tableau a une longueur >= 2 nd = Noeud(tableau[0]) nd.gauche = importe_tableau(tableau[1]) nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None return nd self.racine = importe_tableau(tableau) def show(self): """Renvoie un objet graphviz pour la visualisation graphique de l'arbre""" def representation(dot, noeud, aretes): # Ajoute la représentation du noeud à la représentation dot de l'arbre if noeud is not None: dot.node(str(id(noeud)), str(noeud.valeur)) # Appel récursif de la fonction representation if noeud.gauche is not None: representation(dot, noeud.gauche, aretes) aretes.append((str(id(noeud)) , str(id(noeud.gauche)))) if noeud.droit is not None: representation(dot, noeud.droit, aretes) aretes.append((str(id(noeud)) , str(id(noeud.droit)))) dot = Digraph(comment="Arbre binaire", format='svg') aretes = [] representation(dot, self.racine, aretes) dot.edges(aretes) return dot def taille(self): """Renvoie la taille de l'arbre""" def taille_arbre(nd): # condition d'arrêt if nd is None: return 0 # Appel récursif return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit) return taille_arbre(self.racine) # In[ ]: # Utilisation sur l'arbre exemple : # On instancie notre arbre arbre = Arbrebin() arbre.importe(arbre_liste) # On invique la méthode taille arbre.taille() # #### A vous de jouer # # En utilisant le même modèle que pour la taille, vous allez implémenter la méthode `hauteur` déterminant la hauteur de l'arbre. Vous complèterez donc la cellule ci-dessous et vérifierez qu'elle passe bien le test. # In[ ]: class Arbrebin: """Représente un objet arbre binaire - Propriétés : * racine : objet de type Noeud désignant la racine de l'arbre - Méthodes : * show() : représentation graphique de l'arbre à l'aide de graphviz """ def __init__(self, nd = None): # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel self.racine = nd def importe(self, tableau): """Importe un arbre depuis un tableau ["Noeud", [S_A_G], [S_A_D]] [ ] désigne un arbre vide""" def importe_tableau(tableau): # Cas particuliers if tableau == []: return None if len(tableau) == 1: return Noeud(tableau[0]) # tableau a une longueur >= 2 nd = Noeud(tableau[0]) nd.gauche = importe_tableau(tableau[1]) nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None return nd self.racine = importe_tableau(tableau) def show(self): """Renvoie un objet graphviz pour la visualisation graphique de l'arbre""" def representation(dot, noeud, aretes): # Ajoute la représentation du noeud à la représentation dot de l'arbre if noeud is not None: dot.node(str(id(noeud)), str(noeud.valeur)) # Appel récursif de la fonction representation if noeud.gauche is not None: representation(dot, noeud.gauche, aretes) aretes.append((str(id(noeud)) , str(id(noeud.gauche)))) if noeud.droit is not None: representation(dot, noeud.droit, aretes) aretes.append((str(id(noeud)) , str(id(noeud.droit)))) dot = Digraph(comment="Arbre binaire", format='svg') aretes = [] representation(dot, self.racine, aretes) dot.edges(aretes) return dot def taille(self): """Renvoie la taille de l'arbre""" def taille_arbre(nd): # condition d'arrêt if nd is None: return 0 # Appel récursif return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit) return taille_arbre(self.racine) def hauteur(self): """Renvoie la hauteur de l'arbre""" def hauteur_arbre(nd): # YOUR CODE HERE raise NotImplementedError() return hauteur_arbre(self.racine) # In[ ]: # Cellule de tests arbre = Arbrebin() arbre.importe(arbre_liste) assert arbre.hauteur() == 5 # On indique la méthode taille # ### Parcours en profondeur # Voici la méthode permettant le parcours en profondeur préfixe. # 0. Ajoutez-la à la classe Arbrebin # 0. Vérifiez son bon fonctionnement # 0. Implémentez de même les parcours suffixe et infixe. # 0. Validez votre travail grâce à la cellule de tests. # # Vous ferez attention de choisir les mêmes noms de méthodes que dans la cellule de test pour passer ces derniers avec succès. # ```python # def parcours_prefixe(self): # """Renvoie la liste des noeuds dans un parcours Prefixe""" # def prefixe(noeud): # # Condition d'arrêt # if noeud is None: # return [] # # Appel récursif et renvoi réponse # # La valeur est insérée AVANT les appels # return [noeud.valeur] + prefixe(noeud.gauche) + prefixe(noeud.droit) # # return prefixe(self.racine) # ``` # In[ ]: class Arbrebin: """Représente un objet arbre binaire - Propriétés : * racine : objet de type Noeud désignant la racine de l'arbre - Méthodes : * show() : représentation graphique de l'arbre à l'aide de graphviz """ def __init__(self, nd = None): # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel self.racine = nd def importe(self, tableau): """Importe un arbre depuis un tableau ["Noeud", [S_A_G], [S_A_D]] [ ] désigne un arbre vide""" def importe_tableau(tableau): # Cas particuliers if tableau == []: return None if len(tableau) == 1: return Noeud(tableau[0]) # tableau a une longueur >= 2 nd = Noeud(tableau[0]) nd.gauche = importe_tableau(tableau[1]) nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None return nd self.racine = importe_tableau(tableau) def show(self): """Renvoie un objet graphviz pour la visualisation graphique de l'arbre""" def representation(dot, noeud, aretes): # Ajoute la représentation du noeud à la représentation dot de l'arbre if noeud is not None: dot.node(str(id(noeud)), str(noeud.valeur)) # Appel récursif de la fonction representation if noeud.gauche is not None: representation(dot, noeud.gauche, aretes) aretes.append((str(id(noeud)) , str(id(noeud.gauche)))) if noeud.droit is not None: representation(dot, noeud.droit, aretes) aretes.append((str(id(noeud)) , str(id(noeud.droit)))) dot = Digraph(comment="Arbre binaire", format='svg') aretes = [] representation(dot, self.racine, aretes) dot.edges(aretes) return dot def taille(self): """Renvoie la taille de l'arbre""" def taille_arbre(nd): # condition d'arrêt if nd is None: return 0 # Appel récursif return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit) return taille_arbre(self.racine) # YOUR CODE HERE raise NotImplementedError() # In[ ]: # Cellule de tests arbre = Arbrebin() arbre.importe(arbre_liste) assert arbre.parcours_prefixe() == ['A', 'B', 'C', 'E', 'D', 'F', 'G', 'I', 'H', 'J', 'K'] assert arbre.parcours_suffixe() == ['E', 'C', 'D', 'B', 'I', 'G', 'K', 'J', 'H', 'F', 'A'] assert arbre.parcours_infixe() == ['C', 'E', 'B', 'D', 'A', 'I', 'G', 'F', 'K', 'J', 'H'] # ### Parcours en largeur # Pour finir, ajoutez à la classe **Arbrebin** la méthode `parcours_largeur()` # # Vous vérifierez votre travail avec la cellule de tests. # Il pourra être utile de revoir [l'implémentation des files FIFO avec un tableau python](http://www.lecluse.fr/nsi/NSI_T/donnees/listes_piles_files/). # In[ ]: class Arbrebin: """Représente un objet arbre binaire - Propriétés : * racine : objet de type Noeud désignant la racine de l'arbre - Méthodes : * show() : représentation graphique de l'arbre à l'aide de graphviz """ def __init__(self, nd = None): # Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel self.racine = nd def importe(self, tableau): """Importe un arbre depuis un tableau ["Noeud", [S_A_G], [S_A_D]] [ ] désigne un arbre vide""" def importe_tableau(tableau): # Cas particuliers if tableau == []: return None if len(tableau) == 1: return Noeud(tableau[0]) # tableau a une longueur >= 2 nd = Noeud(tableau[0]) nd.gauche = importe_tableau(tableau[1]) nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None return nd self.racine = importe_tableau(tableau) def show(self): """Renvoie un objet graphviz pour la visualisation graphique de l'arbre""" def representation(dot, noeud, aretes): # Ajoute la représentation du noeud à la représentation dot de l'arbre if noeud is not None: dot.node(str(id(noeud)), str(noeud.valeur)) # Appel récursif de la fonction representation if noeud.gauche is not None: representation(dot, noeud.gauche, aretes) aretes.append((str(id(noeud)) , str(id(noeud.gauche)))) if noeud.droit is not None: representation(dot, noeud.droit, aretes) aretes.append((str(id(noeud)) , str(id(noeud.droit)))) dot = Digraph(comment="Arbre binaire", format='svg') aretes = [] representation(dot, self.racine, aretes) dot.edges(aretes) return dot def taille(self): """Renvoie la taille de l'arbre""" def taille_arbre(nd): # condition d'arrêt if nd is None: return 0 # Appel récursif return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit) return taille_arbre(self.racine) # YOUR CODE HERE raise NotImplementedError() # In[ ]: # Cellule de tests arbre = Arbrebin() arbre.importe(arbre_liste) assert arbre.parcours_largeur() == ['A', 'B', 'F', 'C', 'D', 'G', 'H', 'E', 'I', 'J', 'K'] # ## Arbres Binaires de Recherche # # Il est temps de passer aux arbres binaires de recherche. Un ABR est un arbre binaire particulier. Il est donc souhaitable que toutes les méthodes définies dans la classe **Arbrebin** soient aussi disponibles dans la classe **Abr** que nous allons créer. # # Faire un copier/coller de ces dernières serait fort maladroit. La structure d'objet nous offre un mécanisme particulièrement intéressant ici : la notion ***d'héritage***. En faisant hériter notre classe **Abr** de la classe **Arbrebin**, toutes les méthodes d'**Arbrebin** seront disponibles pour **Abr** et nous n'aurons juste qu'à nous soucier des méthodes spécifiques aux arbres binaires de recherche. # # ### Insertion # # Afin de pouvoir commencer à manipuler nos ABR, nous allons implémenter la méthode `insere`. Complétez la classe ci-dessous # In[ ]: class Abr(Arbrebin): """Arbre Binaire de Recherche Hérite de la classe Arbre binaire""" def __init__(self): """A l'initialisation, notre arbre est vide""" self.racine = None def insere(self, valeur): """Insère valeur dans note ABR paramètre : valeur à insérer""" def insere_noeud(nd, valeur): # insère la valeur dans nd # renvoie le noeud complété # YOUR CODE HERE raise NotImplementedError() self.racine = insere_noeud(self.racine, valeur) # Si votre méthode `insere` fonctionne, la cellule ci-dessous doit construire un ABR en utilisant l'arbre d'exemple. # # Une fois votre classe au point, changez l'ordre de parcours de l'arbre de départ pour observer l'impact # sur l'ABR construit. Vous constarerez alors que l'ABR est loin d'être unique : tout dépend de l'ordre # d'insertion des valeurs. Un de ces ABR sera plus efficace pour la recherche. Trouvez-vous lequel ? # In[ ]: # Vous pouvez modifier le contenu de cette cellule ! # On crée un ABR vide mon_abr = Abr() # On insère les valeurs de notre arbre de départ dans un certain ordre for v in arbre.parcours_prefixe(): mon_abr.insere(v) mon_abr.show() # In[ ]: # Cellule de test mon_abr = Abr() for v in arbre.parcours_prefixe(): mon_abr.insere(v) # les méthodes de Arbrebin sont disponibles pour Abr sans avoir eu a les recréer # c'est la magie de l'héritage assert mon_abr.hauteur() == 9 # ### recherche # Pour la suite de notre activité, nous changerons un peu et jouerons avec les termes d'une suite célèbre. Peut-être la reconnaîtrez-vous ! Commmençons par construire notre ABR. Que constatez-vous ? Cet arbre est-il intéressant pour rechercher une valeur ? # In[ ]: suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987] suite_abr = Abr() for v in suite: suite_abr.insere(v) suite_abr.show() # Pour résoudre ce problème, nos allons utiliser une technique surprenante : appeler l'aléatoire à la rescousse ! Vous allez constater qu'en mélangeant notre suite, la situation s'améliore très sensiblement ! # In[ ]: from random import shuffle suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987] shuffle(suite) suite_abr = Abr() for v in suite: suite_abr.insere(v) suite_abr.show() # Voilà qui est nettement mieux !! # # Vous allez maintenant pour terminer cette activité implémenter la méthode `recherche` qui prend une valeur en paramètre et renvoie un booleen selon que la valeur est dans l'arbre ou non. # In[ ]: class Abr(Arbrebin): """Arbre Binaire de Recherche Hérite de la classe Arbre binaire""" def __init__(self): """A l'initialisation, notre arbre est vide""" self.racine = None # YOUR CODE HERE raise NotImplementedError() # In[ ]: suite = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 277, 610, 987] shuffle(suite) suite_abr = Abr() for v in suite: suite_abr.insere(v) assert suite_abr.recherche(233) assert not suite_abr.recherche(317) # In[ ]: