- Identifier des situations nécessitant une structure de données arborescente. - Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).
- On fait le lien avec la rubrique « algorithmique ».
…de la partie « Algorithmique »
Contenus
Capacités attendues
Commentaires
- Algorithmes sur les arbres binaires et sur les arbres binaires de recherche.
- Calculer la taille et la hauteur d’un arbre. Parcourir un arbre de différentes façons (ordres infixe, préfixe ou suffixe ; ordre en largeur d’abord). Rechercher une clé dans un arbre de recherche, insérer une clé.
- Une structure de données récursive adaptée est utilisée. L’exemple des arbres permet d’illustrer la programmation par classe. La recherche dans un arbre de recherche équilibré est de coût logarithmique.
Structures de données abstraites arborescentes : les arbres
La notion de listes chaînées est parfaite pour structurer un ensemble d’élements destinés à être énumérés séquentiellement. Elle permet aussi d’implémenter les structures de piles et de files. Elle n’est cependant pas adaptée aux accès spécifiques à des positions données dans la séquence, puisqu’il faut alors parcourir toutes les cellules depuis le début de la liste jusqu’à la position souhaitée (complexité en O(N)).
Lorsqu’on manipule une information présentant une certaine hiérarchie, il est commun de la représenter graphiquement :
Arbre généalogique
graph TD
A(Jules) --> B(Mireille)
A(Jules) --> C(Gérard)
A(Jules) --> D(Guy)
B --> E(David)
E --> F(Gabriel)
E --> G(Louise)
C --> H(Fabien)
D --> I(Sandra)
D --> J(Marion)
Arborescence d’un système de fichier
graph TD
A(/) --> B(bin)
A --> C(root)
A --> D(home)
A --> F(etc)
A --> G(var)
A --> H(usr)
A --> I(tmp)
D --> J(mats)
J --> K(Documents)
J --> L(Images)
J --> M(Vidéos)
K --> N(Terminale)
N --> O(NSI)
N --> P(PC)
Expression mathématique
graph TD
A(+) --> B(*)
B --> C(3)
B --> D(8)
A --> E(6)
Exercice
écrire l’expression mathématique représentée par l’arbre ci-dessus.
Un arbre lexicographique, ou arbre en parties communes, ou dictionnaire, représente un ensemble de mots. Les préfixes communs à plusieurs mots n’apparaissent qu’une seule fois dans l’arbre.
graph TD
A(.) --> B(m)
B --> C(a)
C --> D(i)
D --> E(s)
E --> F(o)
F --> G(n)
D --> H(t)
H --> I(r)
I --> J(i)
J --> K(s)
K --> L(e)
L --> M(r)
C --> N(t)
N --> O(e)
O --> P(l)
P --> Q(a)
Q --> R(t)
P --> S(o)
S --> T(t)
A --> U(v)
U --> V(a)
V --> W(l)
W --> X(i)
X --> Y(s)
Y --> Z(e)
Exercice
Quels sont les mots représentés dans l’arbre ?
Exercice
Ajouter les mots « matériel » et « vallon ».
Remarque : ne pas différencier les lettres é et e.
Réponse
Définitions et vocabulaire
Arbre (enraciné)
À retenir
Un arbre (nom complet arbre enraciné) est une structure de données abstraite arborescente dans laquelle les données sont hiérarchisées depuis un nœud racine.
Un arbre dont tous les nœuds sont nommés est dit étiqueté. L’étiquette (ou nom du sommet) représente la « valeur » du nœud ou bien l’information associée au nœud.
Racine, noeud, branche, feuille
À retenir
Un arbre est un ensemble organisé de nœuds dans lequel chaque nœud a un père, sauf un nœud que l’on appelle le nœud racine.
Si le nœud n’a pas de fils, on dit que c’est une feuille.
Les nœuds sont reliés par des branches.
Exercice
Nommer les nœuds puis les feuilles dans l’arbre représenté ci-dessous.
Compter le nombre de branches.
graph TD
A(a) --> B(b)
A --> C(c)
B --> D(d)
B --> E(e)
E --> F(f)
E --> G(g)
B --> H(h)
H --> I(i)
Réponses
Nœuds internes: a (racine), b, e, h et feuilles : c, d, f, g, i.
8 branches.
Profondeur d’un nœud, hauteur d’un nœud
À retenir
La profondeur d’un nœud est sa distance à la racine.
La profondeur d’un nœud dans un arbre est donc le nombre d’arrêtes qu’il faut parcourir, depuis la racine, pour parvenir au nœud.
À retenir
La hauteur d’un nœud est sa distance à la feuille la plus profonde ayant une relation de descendance avec lui.
La hauteur d’un nœud dans un arbre est donc le nombre d’arrêtes qu’il faut parcourir, depuis ce nœud jusqu’à la feuille la plus profonde ayant une relation de descendance avec lui.
Profondeur d’un arbre
À retenir
La hauteur (ou profondeur) d’un arbre est égale à la profondeur du nœud le plus profond.
Info
La hauteur d’un arbre est très importante. En effet, la plupart des algorithmes que nous verrons dans la suite ont une complexité qui dépend de la hauteur de l’arbre. Ainsi plus l’arbre aura une hauteur élevée, plus l’algorithme mettra de temps à s’exécuter.
Avertissement
Tous les auteurs n’utilisent pas la convention choisie dans ce cours !
Pour certains, la profondeur d’un nœud est égale au nombre de nœuds qu’il faut parcourir à partir de la racine (incluse) pour parvenir au nœud ; la hauteur de la racine est alors de 1.
Exercice
Donner la profondeur du nœud e dans l’arbre représenté ci-dessus.
Donner la hauteur du nœud e dans l’arbre représenté ci-dessus.
Quelle est la profondeur de cet arbre ?
Réponses
Profondeur de e : 2.
Hauteur de e : 1.
Profondeur de l’arbre : 3.
Taille d’un arbre
À retenir
La taille d’un arbre est égale au nombre de nœuds de l’arbre (nœuds internes et feuilles).
Exercice
Indiquer la taille de l’arbre représenté ci-dessus.
Réponses
Taille de l’arbre : 9.
Degré d’un noeud, degré d’un arbre
À retenir
Le degré d’un nœud est égal au nombre de ses descendants (fils).
Le degré d’un arbre est égal au plus grand des degrés de ses nœuds.
Exercice
Quel est le degré du nœud b dans l’arbre représenté ci-dessus ?
Quel est le degré du nœud a ?
Quel est le degré de l’arbre ?
Réponses
Degré de b : 3.
Degré de a : 2.
Degré de l’arbre : 3.
Relation entre les liste et les arbres
À retenir
Un arbre dont tous les nœuds n’ont qu’un seul fils est en fait une liste.
Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres
Un arbre binaire est une structure de données abstraite formée d’un ensemble de nœuds organisés hiérarchiquement selon la définition par récurrence suivante :
Un arbre binaire est :
soit un arbre vide, noté E, ne contenant aucun nœud ;
soit un nœud, appelé racine, relié à exactement deux arbres binaires g et d, respectivement appelés sous-arbres gauche et sous-arbre droit.
On note T(r,g,d) l’arbre non vide dont la racine r (on peut aussi indiquer l’étiquette de cette racine).
Vocabulaire et remarques
Un nœud dont les deux sous-arbres sont vides est appelé une feuille.
Un nœud qui n’est pas une feuille est un nœud interne.
Un arbre binaire est dit parfait si toutes les feuilles sont à la même profondeur.
La racine d’un arbre T est le seul nœud de T sans parent.
Propriétés
Position des sous-arbres
La position des sous-arbres gauche et droite est fondamentale :
T(r,g,d)=T(r,d,g)
Taille d’un arbre
La taille d’un arbre est égale au nombre de nœuds qu’il comporte.
Le nombre de nœuds d’un arbre binaire T, noté n(T), se calcule récursivement :
n(E)=0
n(T)=1+n(g)+n(d)
Profondeur d’un nœud
La profondeur d’un nœud n, notée h(n), est sa distance à la racine.
La profondeur d’un nœud n, notée h(n), est définie récursivement par :
h(racine)=0
h(n)=1+h(parent de n)
La profondeur d’un nœud dans un arbre est donc le nombre d’arrêtes qu’il faut parcourir, depuis la racine, pour parvenir au nœud.
Avertissement
La définition de la profondeur d’un nœud peut varier ! Il est impératif de vérifier celle choisie avant tout travail.
Hauteur d’un arbre
La hauteur d’un arbre est la profondeur du nœud le plus éloigné de la racine.
La hauteur d’un arbre est aussi sa profondeur.
La hauteur d’un arbre binaire T, notée h(T) est définie récursivement par :
h(E)=−1 si l’arbre est vide ;
h(T)=1+max(h(g),h(d))
Remarque
On peut aussi définir la hauteur d’un nœud : la hauteur d’un nœud est la distance entre ce nœud et la feuille la plus profonde ayant une relation de descendance avec ce nœud.
Avertissement
La définition de la hauteur d’un arbre peut varier ! Il est impératif de vérifier celle choisie avant tout travail.
Relation entre le nombre de nœuds n et la hauteur d’un arbre
Soit T un arbre binaire, n son nombre de nœuds et h sa hauteur. Ces grandeurs sont liées par les relations suivantes :
h+1≤n≤2h+1−1
le nombre de sous-arbres vides de T est n+1.
Dans quel cas a-t-on N=h+1 ?
Réponse
On a N=h+1 lorsque chaque nœud ne possède qu’un seul nœud fils. Il s’agit donc d’une structure linéaire (liste).
Dans quel cas a-t-on N=2h+1−1 ?
Réponse
On a N=2h+1−1 lorsque l’arbre binaire est parfait, c’est à dire lorsque toutes les feuilles ont la même profondeur.
Spécification d’un arbre binaire
À retenir
Créer un nœud (type) :
fonction : creer_nœud()⟶ retourne un nœud ;
fils_gauche et fils_droit sont automatiquement initialisés à None ;;
complexité : O(0) (pas tout à fait vrai mais suffisant pour comprendre la suite).
Lire dans le champ valeur :
fonction : lire_valeur(n: Noeud[T])⟶T ;
complexité : 1 opération élémentaire.
Écrire dans le champ valeur :
fonction : modifier_valeur(n: Noeud[T], valeur: T)⟶None ;
complexité : 1 opération élémentaire.
Lire dans le champ fils_gauche :
fonction : lire_filsG(n: Noeud[T])⟶Noeud[T] ;
complexité : 1 opération élémentaire.
Écrire dans le champ fils_gauche :
fonction : modifier_filsG(n: Noeud[T], m: Noeud[T])⟶None ;
complexité : 1 opération élémentaire.
Lire dans le champ fils_droit :
fonction : lire_filsD(n: Noeud[T])⟶Noeud[T] ;
complexité : 1 opération élémentaire.
Écrire dans le champ fils_droit :
fonction : modifier_filsD(n: Noeud[T], m: Noeud[T])⟶None ;
complexité : 1 opération élémentaire.
Avertissement
Tout comme on a désigné les listes chaînées par leur première cellule, on va désigner les arbres par leur nœud racine.
Implémentation de la spécification en Python à l’aide d’une classe
Il existe de nombreuses façons de d’implémenter la structure d’arbre en Python. Dans cette partie on va utiliser une classe.
Avertissement
Le paradigme de programmation utilisé ci-dessous est le paradigme impératif : on crée dans un premier temps une structure élémentaire qui ne sert qu’à stocker les différentes valeurs et on définit ensuite des fonctions qui manipulent cette structure.
La structure utilisée peut être :
Une classe qui définit trois attributs valeur, gauche et droit et aucune méthode ;
Une liste Python de trois éléments ;
Un dictionnaire comportant trois clés : valeur, gauche et droit.
On peut même imaginer utiliser un tableau ou une liste chaînée !
On ne créera pas de structure « arbre binaire » (accompagnée de méthodes) dans ce document.
Écrire le code de la classe Noeud respectant la spécification. Les trois attributs seront nommés valeur, gauche, droit.
Réponse
from__future__importannotationsclassNoeud:"""
Structure de stockage pour créer des arbres binaires.
"""def__init__(self:Noeud,val:str,g:Noeud=None,d:Noeud=None)->None:"""Initialisation de l'objet."""self.valeur=valself.gauche=gself.droit=d
Écrire le code permettant de construire l’arbre :
graph TD
A("A") --- B("B")
B --- G(None)
B --- C("C")
C --- H(None)
C --- I(None)
A --- D("D")
D --- E(None)
D --- F(None)
Écrire le code de la fonction est_vide dont la spécification est :
defest_vide(n:Noeud)->bool:"""
Teste si un arbre est vide.
"""
Réponse
defest_vide(n:Noeud)->bool:"""
Teste si un arbre est vide.
"""returnn==None
Écrire le code de la fonction ajoute_filsG dont la spécification est :
defajoute_filsG(n:Noeud,valeur:str)->None:"""
Ajoute un noeud d'étiquette valeur comme fils gauche.
"""
Réponse
defajoute_filsG(n:Noeud,valeur:str)->None:"""
Ajoute un noeud d'étiquette valeur comme fils gauche.
"""ifest_vide(n.gauche):n.gauche=Noeud(valeur)else:raiseException("Le nœud possède déjà un fils gauche !")
Écrire le code de la fonction ajoute_filsD dont la spécification est :
defajoute_filsD(n:Noeud,valeur:str)->None:"""
Ajoute un noeud d'étiquette valeur comme fils droit.
"""
Réponse
defajoute_filsD(n:Noeud,valeur:str)->None:"""
Ajoute un noeud d'étiquette valeur comme fils droit.
"""ifest_vide(n.droit):n.droit=Noeud(valeur)else:raiseException("Le nœud possède déjà un fils droit !")
Écrire le code de la fonction est_feuille dont la spécification est :
defest_feuille(n:Noeud)->bool:"""
Teste si un noeud est une feuille.
"""
Réponse
defest_feuille(n:Noeud)->bool:"""
Teste si un noeud est une feuille.
"""returnest_vide(n.gauche)andest_vide(n.droit)
Écrire le code de la fonction degre_noeud dont la spécification est :
defdegre_noeud(n:Noeud)->int:"""
Détermine le degré du noeud passé en argument.
"""
Quelques algorithmes de manipulation des arbres binaires
Tous les algorithmes qui suivent sont récursifs.
Écrire le code de la fonction taille dont la spécification est :
deftaille(n:Noeud)->int:"""
Retourne le nombre de noeud dans l'arbre.
"""
Réponse
deftaille(n:Noeud)->int:"""
Retourne le nombre de noeud dans l'arbre.
"""ifest_vide(n):# Cas de base : un arbre vide ne contient aucun noeud.return0else:# Recherche récursive dans les sous-arbres gauche et droit.taille_gauche=taille(n.gauche)taille_droit=taille(n.droit)# Calcul de la taillereturn1+taille_gauche+taille_droit
Écrire le code de la fonction profondeur dont la spécification est :
defprofondeur(n:Noeud)->int:"""
Retourne la profondeur de l'arbre.
"""
Réponse
defprofondeur(n:Noeud)->int:"""
Retourne la profondeur de l'arbre.
"""ifest_vide(n):# Cas de base : si le nœud est vide, il n'est pas dans l'arbre.return-1else:# Recherche récursive dans les sous-arbres gauche et droit.arbre_gauche=profondeur(n.gauche)arbre_droit=profondeur(n.droit)# Détermine la profondeurreturn1+max(arbre_gauche,arbre_droit)
Écrire le code de la fonction nbre_feuilles dont la spécification est :
defnbre_feuilles(n:Noeud)->int:"""
Détermine le nombre de feuilles dans l'arbre.
"""
Réponse
defnbre_feuilles(n:Noeud)->int:"""
Détermine le nombre de feuilles dans l'arbre.
"""ifest_vide(n):# Cas de base : un arbre vide ne contient aucune feuillereturn0elifest_feuille(n):# Cas de base : on ajoute 1 au total dès qu'on rencontre une feuillereturn1else:# Recherche récursive dans les sous-arbres gauche et droit.nbre_feuilles_gauche=nbre_feuilles(n.gauche)nbre_feuilles_droit=nbre_feuilles(n.droit)# Calcul du nombre de feuillesreturnnbre_feuilles_gauche+nbre_feuilles_droit
Écrire le code de la fonction profondeur_noeud dont la spécification est :
defprofondeur_noeud(n:Noeud,val:str,prof:int=0)->int:"""
Détermine la profondeur du noeud de valeur val.
"""
Réponse
defprofondeur_noeud(n:Noeud,val:str,prof:int=0)->int:"""
Détermine la profondeur du noeud de valeur val.
Retourne -1 si le noeud n'est pas dans l'arbre.
prof est la profondeur.
"""ifest_vide(n):# Cas de base : si le nœud est vide, il n'est pas dans l'arbre.return-1elifn.valeur==val:# On a trouvé le noeudreturnprofelse:# Recherche récursive dans les sous-arbres gauche et droit.# Incrémente la profondeurprof_gauche=profondeur_noeud(n.gauche,val,prof+1)prof_droite=profondeur_noeud(n.droit,val,prof+1)# Valeur retournéereturnmax(prof_gauche,prof_droite)
Exemple : recherche de la profondeur du nœud de valeur 3
Les nœuds passés en argument sont repérés par la notation 1n, 2n, …
Écrire le code de la fonction remplace dont la spécification est :
defremplace(n:Noeud,val_ini:str,val_fin:str)->None:"""
Cherche tous les noeuds de valeur val_ini et remplace ces
dernières par val_fin.
"""
Réponse
defremplace(n:Noeud,val_ini:str,val_fin:str)->None:"""
Cherche tous les noeuds de valeur val_ini et remplace ces
dernières par val_fin.
"""ifest_vide(n):returnNoneelifn.valeur==val_ini:n.valeur=val_finelse:remplace(n.gauche,val_ini,val_fin)remplace(n.droit,val_ini,val_fin)
Écrire le code de la fonction ajoute dont la spécification est :
defajoute(n:Noeud,parent:str,enfant:str,gauche:bool)->None:"""
Ajoute un noeud de valeur enfant comme enfant du noeud de valeur
parent.
Le noeud enfant est placé par défaut à gauche.
HYPOTHÈSE : Le noeud de valeur parent existe.
"""
Réponse
defajoute(n:Noeud,parent:str,enfant:str,gauche:bool)->None:"""
Ajoute un noeud de valeur enfant comme enfant du noeud de valeur
parent.
Le noeud enfant est placé par défaut à gauche.
HYPOTHÈSE : Le noeud de valeur parent existe.
"""ifest_vide(n):returnNoneelifn.valeur==parent:ifgaucheandnotest_vide(n.gauche):raiseException("Le noeud enfant gauche existe déjà !")ifnotgaucheandnotest_vide(n.droit):raiseException("Le noeud enfant droit existe déjà !")ifgauche:n.gauche=Noeud(enfant)else:n.droit=Noeud(enfant)else:ajoute(n.gauche,parent,enfant,gauche)ajoute(n.droit,parent,enfant,gauche)
Écrire le code de la fonction supprime dont la spécification est :
defsupprime(n:Noeud,val:str)->None:"""
Supprime le noeud de valeur val ainsi que tous ses descendants.
"""
Réponse
defsupprime(n:Noeud,val:str)->None:"""
Supprime le noeud de valeur val ainsi que tous ses descendants.
"""ifest_vide(n):returnNoneelifest_feuille(n):returnNoneelifn.gauche.valeur==val:n.gauche=Noneelifn.droit.valeur==val:n.droit=Noneelse:supprime(n.gauche,val)supprime(n.droit,val)
Quelles sont les complexités des algorithmes implémentés dans cette section ?
Réponse
Les algorithmes parcourent une fois chaque nœud de l’arbre. La complexité est donc proportionnelle au nombre de nœuds.
Parcours en profondeur d’un arbre
Les fonction écrites jusqu’à présent parcourent en profondeur tous les nœuds des arbres sans que l’ordre dans lequel ce parcourt est effectué ait la moindre importance.
À retenir
Si on souhaite donner un affichage de l’arbre, la façon dont on le parcourt prend alors une grande importance. On peut :
Parcourir le sous-arbre gauche, afficher la valeur du nœud racine puis enfin parcourir le sous-arbre droit. On parle d’un parcours infixe.
Afficher la valeur du nœud racine avant de parcourir le sous-arbre gauche puis le sous-arbre droit. On parle d’un parcours préfixe.
Parcourir le sous-arbre gauche, le sous-arbre droit puis afficher les valeurs. On parle d’un parcours suffixe.
Pour l’arbre ci-dessous, donner les parcours préfixe, infixe et suffixe.
Écrire le code des fonctions parcours_infixe, parcours_prefixe et parcours_suffixe dont les spécifications sont :
defparcours_infixe(n:Noeud)->str:"""
Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
Retourne le parcours sous forme d'une chaîne de caractères.
"""
Réponse
defparcours_infixe(n:Noeud)->str:"""
Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
Retourne le parcours sous forme d'une chaîne de caractères.
"""ifest_vide(n):return""else:chaine=parcours_infixe(n.gauche)chaine+=str(n.valeur)chaine+=parcours_infixe(n.droit)returnchaine
defparcours_prefixe(n:Noeud)->None:"""
Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
Retourne le parcours sous forme d'une chaîne de caractères.
"""
Réponse
defparcours_prefixe(n:Noeud)->None:"""
Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
Retourne le parcours sous forme d'une chaîne de caractères.
"""ifest_vide(n):return""else:chaine=str(n.valeur)chaine+=parcours_prefixe(n.gauche)chaine+=parcours_prefixe(n.droit)returnchaine
defparcours_suffixe(n:Noeud)->None:"""
Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
Retourne le parcours sous forme d'une chaîne de caractères.
"""
Réponse
defparcours_suffixe(n:Noeud)->None:"""
Parcourt le sous-arbre gauche, affiche la valeur du nœud puis parcourt le sous-arbre droit.
Retourne le parcours sous forme d'une chaîne de caractères.
"""ifest_vide(n):return""else:chaine=parcours_suffixe(n.gauche)chaine+=parcours_suffixe(n.droit)chaine+=str(n.valeur)returnchaine
Algorithmes itératifs — Parcours d’un arbre à l’aide d’une file ou d’une pile
Parcours en largeur d’un arbre
Décrire le fonctionnement de l’algorithme suivant et montrer qu’il réalise un parcours en largeur d’un arbre.
Fonction parcours_largeur(racine: Noeud):
File f= File() f.enfiler(racine) TantQue non f.est_vide():
n= f.defiler() print(n.valeur) Si non est_vide(n.filsG):
f.enfiler(n.filsG) FinSi
Si non est_vide(n.filsD):
f.enfiler(n.filsD) FinSi
FinTantQue
FinFonction
Implémenter en Python cet algorithme.
Réponse
defparcours_largeur(n:Noeud)->str:"""Réalise le parcours en largeur d'un arbre binaire."""message=""f=File()f.enfiler(n)whilenotf.est_vide():n=f.defiler()message+=str(n.valeur)ifnotest_vide(n.gauche):f.enfiler(n.gauche)ifnotest_vide(n.droit):f.enfiler(n.droit)returnmessage
Parcours en profondeur d’un arbre
Décrire le fonctionnement de l’algorithme suivant et montrer qu’il réalise un parcours en profondeur d’un arbre.
De quel type de parcours en profondeur s’agit-il ?
Fonction parcours_profondeur(racine: Noeud):
Pile p= Pile() p.empiler(racine) TantQue non p.est_vide():
n= p.depiler() print(n) Si non est_vide(n.filsG):
p.empiler(n.filsG) FinSi
Si non est_vide(n.filsD):
p.empiler(n.filsD) FinSi
FinTantQue
FinFonction
Réponse
L’algorithme semble realiser un parcours préfixe mais en explorant d’abord le sous-arbre droit au lieu d’explorer le sous-arbre gauche.
Modifier l’algorithme de telle sorte qu’il réalise le parcours préfixe.
Réponse
Fonction parcours_profondeur(racine: Noeud):
Pile p= Pile() p.empiler(racine) TantQue non p.est_vide():
n= p.depiler() print(n) Si non est_vide(n.filsD):
p.empiler(n.filsD) FinSi
Si non est_vide(n.filsG):
p.empiler(n.filsG) FinSi
FinTantQue
FinFonction
Implémenter en Python cet algorithme.
Réponse
defparcours_prefixe_iter(n:Noeud)->str:"""
Réalise un parcours préfixe à l'aide d'une pile.
"""message=""p=Pile()p.empiler(n)whilenotp.est_vide():n=p.depiler()message+=str(n.valeur)ifnotest_vide(n.gauche):p.empiler(n.gauche)ifnotest_vide(n.droit):p.empiler(n.droit)returnmessage
Implémentation de la spécification en Python à l’aide d’une liste Python
Reprendre toutes les fonctions de ce document en n’utilisant pas la classe Noeud mais une liste à trois éléments. Le premier est la « valeur » du noeud, le second l’adresse du fils gauche, le troisième l’adresse du fils droit.
Réponse
"""
Implémentation d'un arbre binaire en utilisant le
paradigme impératif et des listes.
Structure d'un noeud : [valeur, gauche, droit]
"""defest_vide(n:list[str,list,list])->bool:"""
Teste si un arbre est vide.
"""returnnisNonedefajoute_filsG(n:list[str,list,list],valeur:str)->None:"""
Ajoute un noeud d'étiquette valeur comme fils gauche.
"""ifest_vide(n[1]):n[1]=[valeur,None,None]else:raiseException("Le nœud possède déjà un fils gauche !")defajoute_filsD(n:list[str,list,list],valeur:str)->None:"""
Ajoute un noeud d'étiquette valeur comme fils droit.
"""ifest_vide(n[2]):n[2]=[valeur,None,None]else:raiseException("Le nœud possède déjà un fils droit !")defest_feuille(n:list[str,list,list])->bool:"""
Teste si un noeud est une feuille.
"""returnest_vide(n[1])andest_vide(n[2])defdegre_noeud(n:list[str,list,list])->int:"""
Détermine le degré du noeud passé en argument.
"""ifest_vide(n):raiseException("Le nœud est vide !")nbre=0ifnotest_vide(n[1]):nbre+=1ifnotest_vide(n[2]):nbre+=1returnnbredeftaille(n:list[str,list,list])->int:"""
Retourne le nombre de noeud dans l'arbre.
"""ifest_vide(n):return0else:return1+taille(n[1])+taille(n[2])defprofondeur(n:list[str,list,list])->int:"""
Retourne la profondeur de l'arbre.
"""ifest_vide(n):return-1else:return1+max(profondeur(n[1]),profondeur(n[2]))defnbre_feuilles(n:list[str,list,list])->int:"""
Détermine le nombre de feuilles dans l'arbre.
"""ifest_vide(n):return0elifest_feuille(n):return1else:returnnbre_feuilles(n[1])+nbre_feuilles(n[2])defparcours_pref(n:list[str,list,list])->str:"""Parcours en profondeur préfixe d'un arbre binaire."""ifest_vide(n):return""else:chaine=str(n[0])chaine+=parcours_pref(n[1])chaine+=parcours_pref(n[2])returnchainedefparcours_inf(n:list[str,list,list])->str:"""Parcours en profondeur infixe d'un arbre binaire."""ifest_vide(n):return""else:chaine=parcours_inf(n[1])chaine+=str(n[0])chaine+=parcours_inf(n[2])returnchainedefparcours_suf(n:list[str,list,list])->str:"""Parcours en profondeur infixe d'un arbre binaire."""ifest_vide(n):return""else:chaine=parcours_suf(n[1])chaine+=parcours_suf(n[2])chaine+=str(n[0])returnchaineif__name__=="__main__":arb=["A",["B",["C",None,None],["D",None,None]],["E",["F",None,None],["G",["H",None,None],None]],]print(est_vide(arb))print(f"Taille de l'arbre : {taille(arb)}")print(f"Profondeur (hauteur) de l'arbre : {profondeur(arb)}")print(f"Préfixe : {parcours_pref(arb)}")print(f"Infixe : {parcours_inf(arb)}")print(f"Suffixe : {parcours_suf(arb)}")
Implémentation de la spécification en Python à l’aide d’un dictionnaire
Reprendre toutes les fonctions de ce document en n’utilisant pas la classe Noeud mais un dictionnaire à trois clés : valeur, gauche et droit pour stocker la « valeur » du noeud, l’adresse du fils gauche et l’adresse du fils droit.
Réponse
"""
Implémentation du type arbre binaire en utilisant
le paradigme impératif et des dictionnaires.
"""defest_vide(n:dict[str,dict,dict])->bool:"""
Teste si un arbre est vide.
"""returnn==Nonedefajoute_filsG(n:dict[str,dict,dict],val:str)->None:"""
Ajoute un noeud d'étiquette val comme fils gauche.
"""ifest_vide(n["gauche"]):n["gauche"]={"valeur":val,"gauche":None,"droit":None}else:raiseException("Le nœud possède déjà un fils gauche !")defajoute_filsD(n:dict[str,dict,dict],val:str)->None:"""
Ajoute un noeud d'étiquette valeur comme fils droit.
"""ifest_vide(n["droit"]):n["droit"]={"valeur":val,"gauche":None,"droit":None}else:raiseException("Le nœud possède déjà un fils droit !")defest_feuille(n:dict[str,dict,dict])->bool:"""
Teste si un noeud est une feuille.
"""returnest_vide(n["gauche"])andest_vide(n["droit"])defdegre_noeud(n:dict[str,dict,dict])->int:"""
Détermine le degré du noeud passé en argument.
"""ifest_vide(n):raiseException("Le nœud est vide !")nbre=0ifnotest_vide(n["gauche"]):nbre+=1ifnotest_vide(n["droit"]):nbre+=1returnnbredeftaille(n:dict[str,dict,dict])->int:"""
Retourne le nombre de noeud dans l'arbre.
"""ifest_vide(n):return0else:return1+taille(n["gauche"])+taille(n["droit"])defprofondeur(n:dict[str,dict,dict])->int:"""
Retourne la profondeur de l'arbre.
"""ifest_vide(n):return-1else:return1+max(profondeur(n["gauche"]),profondeur(n["droit"]))defnbre_feuilles(n:dict[str,dict,dict])->int:"""
Détermine le nombre de feuilles dans l'arbre.
"""ifest_vide(n):return0elifest_feuille(n):return1else:returnnbre_feuilles(n["gauche"])+nbre_feuilles(n["droit"])defparcours_pref(n:dict[str,dict,dict])->str:"""Parcours en profondeur préfixe d'un arbre binaire."""ifest_vide(n):return""else:returnstr(n["valeur"])+parcours_pref(n["gauche"])+parcours_pref(n["droit"])defparcours_inf(n:dict[str,dict,dict])->str:"""Parcours en profondeur infixe d'un arbre binaire."""ifest_vide(n):return""else:returnparcours_inf(n["gauche"])+str(n["valeur"])+parcours_inf(n["droit"])defparcours_suf(n:dict[str,dict,dict])->str:"""Parcours en profondeur infixe d'un arbre binaire."""ifest_vide(n):return""else:returnparcours_suf(n["gauche"])+parcours_suf(n["droit"])+str(n["valeur"])if__name__=="__main__":arb={"valeur":"A","gauche":None,"droit":{"valeur":"B","gauche":{"valeur":"C","gauche":None,"droit":None},"droit":{"valeur":"D","gauche":None,"droit":None},},}print(est_vide(arb))print(parcours_inf(arb))arb2={"valeur":"A","droit":None,"gauche":None}ajoute_filsG(arb2,"B")ajoute_filsD(arb2,"C")noeud_C=arb2["droit"]ajoute_filsD(noeud_C,"D")ajoute_filsG(noeud_C,"E")print(f"Taille de l'arbre : {taille(arb2)}")print(f"Profondeur (hauteur) de l'arbre : {profondeur(arb2)}")print(parcours_pref(arb2))print(parcours_inf(arb2))print(parcours_suf(arb2))
À retenir
À retenir
Un arbre binaire est un ensemble fini de nœuds, qui est soit vide (la valeur None est utilisée pour représenter l’arbre vide), soit structuré à partir d’un nœud particulier, appelé racine de l’arbre, et de deux sous-ensembles de nœuds formant récursivement un sous-arbre gauche et un sous-arbre droit.
Un arbre peut-être implémenté en Python avec un objet par nœud, d’une classe qui possède trois attributs : la valeur (ou étiquette) du nœud, le sous-arbre gauche et le sous-arbre droit. Il peut aussi être implémenté en utilisant une liste à trois éléments ou un dictionnaire à trois éléments.
Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres
d’organiser les données selon un ordre donné (numérique, lexicographique, etc.) ;
d’effectuer des recherches le plus efficacement possible ;
d’accéder à, d’insérer ou de supprimer les données le plus efficacement possible.
Tableaux
Propriétés
On peut ordonner des données dans un tableau mais l’algorithme de tri le plus rapide, pour un jeu de données aléatoires, est en O(nlogn) ;
On peut accéder à une donnée en O(1) ;
On peut rechercher une valeur efficacement en utilisant la dichotomie (si le tableau est trié !) : O(logn) ;
Supprimer ou insérer une valeur n’est pas très efficace : O(n) (sauf à la fin du tableau).
Dictionnaires
Propriétés
Accéder à, supprimer et insérer une valeur se fait très efficacement : O(1) ;
Les données ne sont pas ordonnées.
Remarque
Dans la suite de ce document, on considérera que les valeurs des nœuds sont des entiers.
À retenir
Un arbre binaire de recherche, ou ABR, est un arbre binaire avec la propriété suivante : quel que soit le nœud x, tous les nœuds situés dans le sous-arbre gauche de x ont une valeur inférieure à la valeur du nœud x, et tous ceux situés dans son sous-arbre droit ont une valeur supérieure à la valeur du nœud x.
Remarque
La définition précédente est récursive.
Cet arbre binaire est-il un arbre binaire de recherche ?
graph TD
A(3) --- B(1)
B --- C(None)
B --- D(2)
D --- E(None)
D --- F(None)
A --- G(4)
G --- H(None)
G --- I(None)
Réponse
oui
Cet arbre binaire est-il un arbre binaire de recherche ?
graph TD
A(3) --- B(2)
B --- C(1)
C --- D(None)
C --- E(None)
B --- F(None)
A --- G(4)
G --- H(None)
G --- I(None)
Réponse
oui
Cet arbre binaire est-il un arbre binaire de recherche ?
graph TD
A(3) --- B(2)
B --- C(None)
B --- D(1)
D --- E(None)
D --- F(None)
A --- G(4)
G --- H(None)
G --- I(None)
Réponse
Non ! La propriété est bien vérifiée pour la racine mais pas pour le sous-arbre gauche.
La définition est récursive !
Info
Les ABR servent à maintenir un ensemble de valeurs ordonnées, avec une meilleure complexité qu’une liste chaînée par exemple. On commence par la recherche d’un élément. La structure de l’ABR permet d’éviter de le parcourir en entier.
Un ABR est un arbre binaire
Avertissement
Le paradigme de programmation utilisé ci-dessous est le paradigme impératif : on crée dans un premier temps une structure élémentaire à l’aide d’une classe et on définit ensuite des fonctions qui manipulent cette structure.
On ne crée pas de structure arbre binaire (accompagnée de méthodes).
Pour représenter un ABR, on va à nouveau utiliser la classe Noeud. Écrire à nouveau le code de cette classe. Les contraintes sur les valeurs des nœuds ne sont pas codées dans la classe.
À quel arbre binaire de recherche ce code correspond-il ?
# Création d'un arbre binaire de recherchearbre= Noeud(10)arbre.gauche = Noeud(5)arbre.droit = Noeud(15)arbre.gauche.gauche = Noeud(3)arbre.gauche.droit = Noeud(8)arbre.droit.gauche = Noeud(12)arbre.droit.droit = Noeud(18)
Réponse
graph TD
A(10) --- B(5)
A --- C(15)
B --- D(3)
B --- E(8)
C --- F(12)
C --- I(18)
Écrire à nouveau les spécifications des fonctions taille, hauteur et parcours (parcours infixe).
defest_vide(n:Noeud)->bool:"""
Teste si le noeud passé en argument est vide ou pas.
"""
Réponse
defest_vide(n:Noeud)->bool:"""
Teste si un arbre est vide.
"""returnn==None
defhauteur(a:Noeud)->int:"""
Retourne la hauteur de l'arbre binaire de recherche a.
"""
Réponse
defhauteur(n:Noeud)->int:"""
Retourne la profondeur de l'arbre.
"""ifest_vide(n):# Cas de base : si le nœud est vide, il n'est pas dans l'arbre.return-1else:# Recherche récursive dans les sous-arbres gauche et droit.arbre_gauche=hauteur(n.gauche)arbre_droit=hauteur(n.droit)# Détermine la profondeurreturn1+max(arbre_gauche,arbre_droit)
deftaille(a:Noeud)->int:"""
Retourne le nombre de noeuds dans l'arbre binaire de recherche.
"""
Réponse
deftaille(n:Noeud)->int:"""
Retourne le nombre de noeud dans l'arbre.
"""ifest_vide(n):# Cas de base : un arbre vide ne contient aucun noeud.return0else:# Recherche récursive dans les sous-arbres gauche et droit.taille_gauche=taille(n.gauche)taille_droit=taille(n.droit)# Calcul de la taillereturn1+taille_gauche+taille_droit
defparcours(n:Noeud)->None:"""
Parcours infixe de l'arbre
"""
Réponse
defparcours_inf(n:Noeud)->str:"""Parcours en profondeur infixe d'un arbre binaire."""ifest_vide(n):# Cas de base : On atteint un noeud videreturn""else:# Appel récursif à gauche, valeur du nœud, appel récursif à droitechaine=parcours_inf(n.gauche)chaine+=str(n.valeur)chaine+=parcours_inf(n.droit)returnchaine
Vérifier que la fonction parcours affiche les valeurs dans l’ordre croissant.
Avertissement
Rappel
On peut voir le parcours infixe comme la projection de l’arbre sur une droite.
Recherche dans un ABR
Écrire le code de la fonction appartient dont la spécification est
defappartient(a:Noeud,x:int)->bool:"""
Détermine si la valeur x apparaît dans l'arbre a.
"""
Réponse
defappartient(a:Noeud,x:int)->bool:"""
Détermine si la valeur x apparaît dans l'abr a.
"""ifest_vide(a):# Cas de base : on parvient à un noeud vide,# la valeur n'est pas présentereturnFalseelifa.valeur==x:# Cas de base : on parvient au noeud recherchéreturnTrue# Appels récursifselifa.valeur>x:returnappartient(a.gauche,x)else:returnappartient(a.droit,x)
Quelle est la complexité de cette recherche ?
Réponse
La complexité du pire cas de la fonction appartient dépend de la hauteur de l’arbre binaire de recherche (ABR).
Dans le pire des cas, l’arbre peut être déséquilibré au point de ressembler à une liste chaînée. Dans un tel scénario, la complexité de la recherche est linéaire par rapport au nombre total de nœuds dans l’arbre.
Complexité : O(n).
Si on écarte ce cas extrême, l’arbre binaire de recherche (ABR) est plus ou moins équilibré et la hauteur est de l’ordre du logrithme du nombre de nœuds.
Complexité : O(logn).
Ajout d’une valeur dans un ABR
Envisager un ABR et, à la main, ajouter un élément.
Quel peut-être le code de la fonction ajoute dont la spécification est
defajoute(a:Noeud,x:int)->None:"""
Ajoute x à l'arbre a (en place).
HYPOTHÈSE : a n'est pas l'arbre vide.
"""
Quelle est la complexité de cette fonction ?
Pour résoudre le problème de l’ajout d’une valeur à un arbre initialement vide et/ou pour ne pas modifier un arbre déjà constitué, il est possible de programmer la fonction ajoute_copie dont la spécification est
defajoute_copie(n:Noeud,x:int)->Noeud:"""
Ajoute la valeur x à l'ABR n. Un nouvel arbre est créé.
"""
Écrire le code de cette fonction.
Utilisation d’un arbre binaire de recherche
Créer la fonction plus_petit_element dont la spécification est
defplus_petit_element(a:Noeud)->int:"""
Retourne le plus petit élément de l'arbre binaire de recherche a.
Lève une exception si l'arbre est vide.
"""
Créer la fonction plus_grand_element dont la spécification est
defplus_grand_element(a:Noeud)->int:"""
Retourne le plus grand élément de l'arbre binaire de recherche a.
Lève une exception si l'arbre est vide.
"""
Créer la fonction est_abr dont la spécification est
defest_abr(a:Noeud)->bool:"""
Détermine si l'arbre a est un arbre binaire de recherche.
"""
Un arbre binaire de recherche est un arbre binaire contenant des valeurs ordonnées, tel que tout nœud contient une valeur plus grande (respectivement plus grande ou égale) que les valeurs de tous les nœuds situés dans son sous-arbre gauche. Cette organisation permet de procéder par dichotomie, en n’ayant à considérer qu’un seul sous-arbre pendant une opération.
Lorsqu’ils sont équilibrés, les arbres binaires de recherche constituent une méthode très efficace pour stocker et rechercher de l’information.
Physique, Chimie et Informatique > Terminales Spé. NSI > Structures hiérarchiques : les arbres
Cette séance a pour objet l’étude d’une méthode de compression de données inventée par David Albert Huffman en 1952. Cette méthode permet de réduire la longueur du codage d’un alphabet et repose sur la création d’un arbre binaire.
Différents types de codages
Info
On appelle alphabet l’ensemble des symboles (caractères) composant la donnée de départ à compresser.
Dans la suite, nous utiliserons un alphabet composé seulement des 8 lettres A, B, C, D, E, F, G et H.
On cherche à coder chaque lettre de cet alphabet par une séquence de chiffres binaires.
Combien de bits sont nécessaires pour coder chacune des 8 lettres de l’alphabet ?
Réponse
Il faut coder 8 caractères, on a donc besoin de 3 bits, puisque 23=8.
Quelle est la longueur en octets d’un message de 1 000 caractères construit sur cet alphabet ?
Réponse
1000×3=3000 bits sont nécessaires.
83000=375 octets sont nécessaires.
Proposer un code de taille fixe pour chaque caractère de l’alphabet de 8 lettres.
Réponse
A : 000 ; B : 001 ; C : 010 ; D : 011 ; E : 100 ; F : 101 ; G : 110 et H : 111.
On considère maintenant le codage suivant, la longueur du code de chaque caractère étant variable.
Lettre
A
B
C
D
E
F
G
H
Code
10
001
000
1100
01
1101
1110
1111
Info
Ce type de code est dit préfixe, ce qui signifie qu’aucun code n’est le préfixe d’un autre (le code de A est 10 et aucun autre code ne commence par 10, le code de B est 001 et aucun autre code ne commence par 001). Cette propriété permet de séparer les caractères de manière non ambiguë.
En utilisant la table précédente, donner le code du message : CACHE.
Réponse
CACHE : 00010000111101
Quel est le message correspondant au code 001101100111001.
Réponse
001101100111001 : BADGE
Dans un texte, chacun des 8 caractères a un nombre d’apparitions différent. Cela est résumé dans le tableau suivant, construit à partir d’un texte de 1 000 caractères.
Lettre
A
B
C
D
E
F
G
H
Nombre
240
140
160
51
280
49
45
35
En utilisant le code de taille fixe proposé à la question 3., quelle est la longueur en bits du message contenant les 1 000 caractères énumérés dans le tableau précédent ?
Réponse
Si on utilise 3 bits pour chaque caractère, il faut 1000×3=3000 bits pour coder le message.
En utilisant le code de la question 4., quelle est la longueur du même message en bits ?
Réponse
N=f(A)⋅l(A)+f(B)⋅l(B)+f(C)⋅l(C)+f(D)⋅l(D)+f(E)⋅l(E)+f(F)⋅l(F)+f(G)⋅l(G)+f(H)⋅l(H) où f(xi) est la fréquence du caractère xi et l(xi) la longueur (en bits) du codage du caractère xi.
A.N.N=240×2+140×3+160×3+51×4+280×2+49×4+45×4+35×4=2660
Info
Ce type de codage réserve le codage le plus court aux caractères les plus fréquents.
Codage de Huffman
L’objectif du codage de Huffman est de trouver le codage proposé à la question 4.
Info
Le codage de Huffman minimise la taille en nombre de bits du message codé en se basant sur le nombre d’apparition de chaque caractère (un caractère qui apparaît souvent aura un code plutôt court).
Pour déterminer le code optimal, on considère 8 arbres, chacun réduit à une racine, contenant le symbole et son nombre d’apparitions.
On fusionne ensuite les deux arbres contenant les plus petits nombres d’apparitions (valeur inscrite sur la racine), et on affecte à ce nouvel arbre la somme des nombres d’apparitions de ses deux sous-arbres. Lors de la fusion des deux arbres, le choix de mettre l’un ou l’autre à gauche n’a pas d’importance. Nous choisissons ici de mettre le plus fréquent à gauche (s’il y a un cas d’égalité, nous faisons un choix arbitraire).
On recommence jusqu’à ce qu’il n’y ait plus qu’un seul arbre.
Combien d’étapes (combien de fusions d’arbres) sont nécessaires pour que cet algorithme se termine ?
En suivant l’algorithme précédent, construire l’arbre de Huffman.
Info
Le code à affecter à chaque lettre est déterminé par sa position dans l’arbre. Précisément, le code d’un symbole de l’alphabet décrit le chemin de la racine à la feuille qui le contient : un 0 indique qu’on descend par le fils gauche et un 1 indique qu’on descend par le fils droit.
graph TD
A(" ") --> B(" ")
B --> X("X")
B --> Y("Y")
A --> Z("Z")
Dans le cas de l’arbre ci-dessus le code de X est 00 (deux fois à gauche), le code de Y est 01, et celui de Z est 1.
Sur chaque arête de l’arbre construit à la question 10., inscrire 0 ou 1 selon que l’arête joint un fils gauche ou un fils droit.
Quel est le code de F ?
Le code suivant permet, à partir d’un fichier nommé texte.txt, de construire l’arbre de Huffman puis un dictionnaire qui associe à chaque caractère du fichier d’entrée son code sous forme d’une séquence de bits (liste de 0 et de 1).
Implémentation en Python de l’algorithme
Écrire le code (et la spécification !) de la classe Noeud, nœud d’un arbre binaire.
Par rapport à l’implémentation réalisée lors des TP précédenrs, ajouter le champ lettre initialisé à la chaîne de caractères vide et la méthode suivante :
def__lt__(self,n:Noeud):"""
Comparaison de deux noeuds = comparaison des valeurs
"""returnself.valeur<n.valeur
Réponse
classNoeud:def__init__(self:Noeud,val:int,let:str="")->None:"""
Initialisation de l'objet.
"""self.valeur=valself.lettre=letself.gauche=Noneself.droit=Nonedef__lt__(self:Noeud,n:Noeud)->bool:"""
Comparaison de deux noeuds = comparaison des valeurs
"""returnself.valeur<n.valeur
Écrire les codes (et la spécification !) des fonctions est_vide, est_feuille, parcours_prefixe qui, respectivement teste si un nœud est vide, teste si un nœud est une feuille et finalement affiche l’arbre.
Réponse
defest_vide(n:Noeud)->bool:"""
Détermine si l'arbre est vide.
"""returnnisNonedefest_feuille(n:Noeud)->bool:"""
Détermine si le noeud est une feuille.
"""return(n.gaucheisNone)and(n.droitisNone)defparcours(n:Noeud)->str:"""
Parcours en profondeur préfixe de l'arbre.
"""ifnisNone:return""else:chaine=str(n.valeur)chaine+=parcours(n.gauche)chaine+=parcours(n.droit)returnchaine
15. Écrire le code de la fonction creation_table_frequences dont la spécification est
defcreation_table_frequences(message:str)->dict[str,int]:"""
Établit la table des fréquences des caractères dans message.
"""
defcreation_table_frequences(message:str)->dict[str,int]:"""
Établit la table des fréquences des caractères dans message.
"""dic={}forcarinmessage:ifcarindic.keys():dic[car]+=1else:dic[car]=1returndic
Lire le document sur les files de priorité.
Écrire le code de la fonction construction_arbre_huffman dont la spécification est
defconstruction_arbre_huffman(dic_frequences:dict[str,int])->Noeud:"""
Construction de l'arbre de Huffman.
"""
et l’algorithme (cf. Cormen, Algorithmes)
Avertissement
Cet algorithme est un exemple d’algorithme glouton dans lequel on prend la décision qui semble la meilleure à un instant donné.
Réponse
defconstruction_arbre_huffman(dic_frequences:dict[str,int])->Noeud:"""
Construction de l'arbre de Huffman.
"""file=[]# Création de tous les noeuds et insertion dans la fileforlettre,frequenceindic_frequences.items():noeud=Noeud(frequence,lettre)heappush(file,noeud)# Construction de l'arbreforiinrange(len(dic_frequences)-1):noeud_droit=heappop(file)noeud_gauche=heappop(file)# Nouvel arbrenouvelle_valeur=noeud_droit.valeur+noeud_gauche.valeurnoeud=Noeud(nouvelle_valeur)noeud.droit=noeud_droitnoeud.gauche=noeud_gauche# Intégration à la fileheappush(file,noeud)# Retour de l'arbrereturnheappop(file)
Écrire une fonction nommée codes_huffman_parcours dont la spécification est :
defcodes_huffman_parcours(a:Noeud,dic:dict[str,str],code:str)->None:"""
Parcours de l'arbre et construction des codes et du dictionnaire passé en argument.
Les lettres constituent les clés et les codes les valeurs.
Algorithme récursif.
"""
Réponse
defcodes_huffman_parcours(a:Noeud,dic:dict[str,str],code:str)->None:"""
Parcours de l'arbre et construction des codes et du dictionnaire passé en argument.
Les lettres constituent les clés et les codes les valeurs.
Algorithme récursif.
"""ifest_feuille(a):# Cas de base : on modifie le dictionnairedic[a.lettre]=codereturnNoneelse:codes_huffman_parcours(a.gauche,dic,code+"0")codes_huffman_parcours(a.droit,dic,code+"1")
Écrire une fonction nommée encodage dont la spécification est :
defencodage(message:str,codes:dict[str,str])->str:"""
Retourne la chaîne de bits produite par le codage de Huffman pour la chaîne message.
"""
Réponse
defencodage(message:str,codes:dict[str,str])->str:"""
Retourne la chaîne de bits produite par le codage de Huffman pour la chaîne message.
"""message_code=""forcarinmessage:message_code+=codes[car]returnmessage_code
Avertissement
Il est impératif de savoir écrire le code de cette fonction !
Écrire une fonction nommée decodage dont la spécification est :
defdecodage(message_compresse:str,codes:dict[str,str])->str:"""
Retourne le message non compressé à partir du codage de Huffman.
"""
Réponse
defdecodage(message_compresse:str,codes:dict[str,str])->str:"""
Retourne le message non compressé à partir du codage de Huffman.
Étape intermédiaire : passer d'un dictionnaire 'A': '001' à
'001' : 'A'
"""# Inversion clés - valeursdic_inverse={}forcle,valeurincodes.items():dic_inverse[valeur]=cle# Décodageresultat=""code=""forcarinmessage_compresse:code+=carifcodeindic_inverse.keys():resultat+=dic_inverse[code]code=""returnresultat
Avertissement
Il est impératif de savoir écrire le code de cette fonction !
Appels de toutes les fonctions dans la partie principale du programme
if__name__=="__main__":arb=Noeud(12,"A")arb.gauche=Noeud(23,"B")arb.droit=Noeud(48,"C")arb.gauche.gauche=Noeud(49,"K")arb.droit.gauche=Noeud(9,"H")arb.droit.droit=Noeud(78,"X")print(parcours(arb))print(arb<Noeud(67,"E"))assertcreation_table_frequences("ABRACADABRA")=={"A":5,"B":2,"R":2,"C":1,"D":1,}message="ABRACADABRA"# nom_fichier = "livre.txt"# with open(nom_fichier, 'r') as f:# message = f.read()table_frequences=creation_table_frequences(message)arbre=construction_arbre_huffman(table_frequences)print(parcours(arbre))dic_codes={}codes_huffman_parcours(arbre,dic_codes,"")print(dic_codes)message_code=encodage(message,dic_codes)print(message_code)message_decode=decodage(message_code,dic_codes)print(message_decode)