L'objectif de cette activité est de découvrir comment implémenter les différentes structures de données en Python, avec ou sans les objets, à travers 3 TP :
- TP1 : Implémentation d'un arbre binaire par tuple de tuple (sans utiliser les objets)
- TP2 : Implémentation d'un arbre binaire en Programmation Orientée Objet (POO)
- TP3 : Implémentation des structures de données linéaires en POO
TP1 : Implémentation d'un arbre binaire par tuple de tuple
|
Voici les différents éléments vus durant ce TP1 :
- définition récursive des arbres binaires
- implémentation d'un nœud avec un tuple (racine,fils gauche,fils droit)
- l’arbre vide est représenté par None
- codage d'un arbre binaire avec des tuples de tuples
- par exemple :
arbre=(2,(1,(0,None,None),None),(5,(4,(3,None,None),None),(12,(9,(8,(6,None,(7,None,None)),None),(10,None,(11,None,None))),(13,None,(14,None,(18,(17,(15,None,(16,None,None)),None),(19,None,None)))))))
- affichage du nombre de nœuds, du nombre de feuilles, de la liste de feuilles et de la hauteur de l'arbre binaire
- tracé graphique de l'arbre binaire en utilisant la bibliothèque matplotlib
- implémentation d'un arbre binaire de recherche (ABR) avec des tuples de tuples
- recherche récursive d'une valeur dans l'ABR
- recherche du minimum (on va à fond à gauche) et du maximum (on va à fond à droite) dans l'ABR
- modification de l'ABR : ajout et suppression d'une valeur
- génération d'un ABR aléatoire à partir d'une liste aléatoire
- implémentation des différents types de parcours d'un arbre
- le parcours en largeur (parcours niveau par niveau)
- distinction entre les 3 parcours en profondeur :
- le parcours préfixe : R,G,D
- le parcours infixe : G,R,D (donne une liste triée des nœuds de l’ABR)
- le parcours suffixe : G,D,R
- utilisation d'un ABR pour trier une liste aléatoire : on range la liste dans un ABR puis on donne son parcours infixe
- création d'une liste par compréhension. Exemple : [2*k for k in range(8)] donne [0, 2, 4, 6, 8, 10, 12, 14]
- codage d'un texte en binaire en utilisant les codes ASCII des caractères
- décodage d'un message binaire pour retrouver les codes ASCII
- notion de code-préfixe (aucun mot du code préfixe ne peut se prolonger pour donner un autre mot du code)
- codage de Huffman pour la compression de données : il génère pour chaque caractère un code-préfixe à taille variable
- utilisation d'un file de priorité (file auto-triée lors de l'ajout d'un élément) avec le module heapq de Python
- estimation du taux de compression obtenu avec le codage de Huffman par rapport au codage ASCII
Pour aller plus loin, voici des programmes en Python permettant d'afficher un arbre binaire défini sous forme d'un tuple de tuple, non pas en utilisant la bibliothèque matplotlib, mais en utilisant simplement le module Turtle de Python.
Les 3 premières versions dessinent un arbre binaire statique : pour le modifier il faut modifier le code source définissant l'arbre binaire à tracer sous forme d'un tuple de tuple :
Les 5 versions suivantes sont interactives : pour faire évoluer l'arbre binaire il suffit de cliquer dans la fenêtre de la tortue avec la souris.
Pour connaître les contrôles interactifs utilisés par chacun des programmes, lisez le message affiché dans la console de Python au langement du programme :
Enfin, voici quelques applications interactive pour bien comprendre la représentation et la modélisation des arbres :
TP2 : Implémentation d'un arbre binaire en Programmation Orientée Objet (POO)
|
Voici les différents éléments travaillés durant ce TP2 :
Création d'une classe Arbre possédants les méthodes suivantes :
- __init__(self, val)
- ajout_gauche(self, val)
- ajout_droit(self, val)
- taille(self)
- hauteur(self)
- vide(self) renvoyant True si l'arbre est vide
Création de 3 fonctions externes à la classe Arbre prenant en paramètre un objet "arbre" de classe Arbre et affichant chacune un parcours en profondeur sur une ligne dans la console :
- parcours_prefixe(arbre)
- parcours_infixe(arbre)
- parcours_suffixe(arbre)
Enrichissement de la classe Arbre en créant 3 nouvelles méthodes qui affichent chacune un parcours en profondeur de l'arbre lui-même sur une ligne dans la console :
- parcours_prefixe(self)
- parcours_infixe(self)
- parcours_suffixe(self)
TP3 : Implémentation des structures de données linéaires en POO
|
Voici les différents éléments vus durant ce TP3 :
- rappel des bases de la POO : classes, attributs, méthodes, instance, constructeur, etc.
- rappel sur les structures de données (linéaire ou non linéaire, homogène ou non, statique ou dynamique)
- création, test et solution de la classe Perso
- création d'une classe Tableau avec les méthodes insert et supprime (programme de base à compléter puis solution finale donnée)
- création d'une classe Pile (programme de base à compléter puis solution finale donnée)
- création d'une classe File (programme de base à compléter puis solution finale donnée)
- création d'une classe Maillon pour implémenter une liste chaînée (programme de base à compléter puis solution finale donnée)
Vous savez maintenant implémenter en Python toutes sortes de structures de données, avec ou sans la programmation orientée objets.
Réalisé par Jean-Christophe MICHEL
© Janvier 2025
