Implémentation récursive.

Avant propos.

Si on voit un arbre enraciné comme cas particulier de graphe non orienté, on peut utiliser les modélisations vues de ce chapitre. Cependant comme les arbres sont des graphes très particuliers, il existe des modélisations plus efficaces.

Version "récursive".

On peut envisager un arbre autrement que comme un cas partciulier de graphe : on peut le voir comme étant composé de trois choses : une clef, un arbre à gauche et un arbre à droite. C'est une définition récursive et dans cette représentation l'arbre et le noeud de l'implémentation précédente se "confondent".


		
Exercice
		
    
		
  1. Créer les arbres suivants :
    
		
      
		
    •  
      • 
		
    •  
      • 
		
    
		
    2. 
		
  2. Charger les fichiers suivants :Exercice2.zip, puis interpréter le script du fichier Exercice2.zip et lancer arbre = Exercice2(). Dessinez l'arbre. 
		
    3. 
		
  3. Surcharger la fonction len. 
    4. 
		
  4. Programmer une fonction qui donne la maximum et le minimum des clef d'un arbre (les clefs doivent avoir un ordre).
    5. 
		
  5. Programmer une méthode qui donne la hauteur.
    6. 
		
  6. Programmer une méthode qui affiche les clefs par effectuant un parcours par profondeur.
    7. 
		
  7. Programmer une méthode qui affiche les clefs qui sont distants de n de la racine (i.e. profondeur de n), en les affichera de gauche à droite.
    8. 
		
  8. Afficher alors toutes les clefs de l'arbre par largeur, discuter de l'efficacité de la méthode.
    9. 
		
  9. Programmer une fonction qui retourne True si un nœud est presque équilibré et False sinon. Faire la méthode qui correspond pour la classe arbre.
    10. 
		
  10. Surcharger pour la classe Arbre __getitem__(self,chemin) ou chemin est un tableau de la forme ["d","d","g"], la fonction doit retourner la clef correspond au fils gauche, du fils droit, du fils droit de la racine. La fonction doit retourner "erreur" si le chemin n'existe pas (ce n'est pas très beau).
    11. 
		
  11. Faire une fonction qui retourne tout les chemins possibles de l'arbre,  par exemple pour le premier exercice elle doit retourner [["g","g"],["g","d"],["g"],["d"],[""]] (l'ordre des chemins n'importe pas).
    12. 
		

		

		
Exercice
		
  • Dans l'implémentation des nœuds on ne peut pas revenir au nœud parent, implémenter une version de Nœud où c'est possible (on ajoutera un attribut parent).
    • 
		
  • Refaire alors, en utilisant l'implémentation précédente, le premier exercice.
    • 
		
  • 
		Ensuite implémenter une fonction nb_parents qui retourne le nombre de parents avant d'arriver à la racine.
    • 
		
  • En utilisant cette nouvelle implémentation faire une méthode ajoute(self,clef) à la classe arbre qui a partir d'un arbre vide va ajouter une clef en veillant à ce que l'arbre soit toujours équilibré à "gauche". Pour obtenir le premier arbre de l'exercice 1, il suffira de faire a = Arbre() ; a.ajoute(0) ; a.ajoute(1) ; a.ajoute(2) ; a.ajoute(3) ; a.ajoute(4). 
    • 
		
		
    
		
    Algorithme Huffman
    
		
    Il est impossible d'avoir un algorithme capable de compresser n'importe quel fichier, cependant le résultat est théorique en effet les fichiers ne sont pas aléatoires, ils ont des particularités que l'on peu exploiter. Par exemple les fichiers texte contiennent en langue française sans doute plus de fois le 'e' que le 'z' pourtant le codage de ses deux caractère prend la même place.
    
		
    Nous allons étudier un algorithme très important et célèbre	L'algorithme de Huffman qui met en pratique cette idéee. Huffman est généralement une des couches des programmes de compression.
    
		
    Pour simplifier l'exemple nous allons imaginer un alphabet de 8 lettres "a", "b", "c", "d", "e", "f", "g", "h" on peut stocker chaque lettre dans 3 bits de la facon suivante :
    
		
    
		
    
			Charactereabcdefgh
		
    
		
    
			Codage000001010011100101110111
		
    
		
    
			Cardinal
			
			
			
			
			
			
			
			
		
    
		
    
			Compression
			
			
			
			
			
			
			
			
		
    		
		
    
		
		
    
		
		
		
    Exercice
		
      
			
    1. A la "main", construire le tableau des effectifs du texte suivant :
			"le blablabla d'ali baba".
			
        
			
      1. Construire le tableau des effectifs.
        2. 
			
      2. Construire l'arbre de Huffman.
        3. 
			
      3. Donner le codage d'Huffman du texte.
        4. 
			
      4. Comparer la taille du texte en codage ASCII, UTF-8, UTF32.
        5. 
			
      
			
			
			
      2. 
			
    2. Sur Python, faire une fonction qui prend un string en paramaètre et retourne un dictionnaire qui pour chaque caractère du texte associe son cardinal dans la chaine.
      3. 
			
    3. Faire une fonction qui a un dictionnaire associant à un caractére, un nombre entier va retourner l'arbre de Huffman correspondant.
      4. 
			
    4. Faire une fonction qui a arbre de Huffman va retourner un dictionnaire associant à chaque caractère stocké dans l'arbre le codage de Huffman qui correspond.
      5.