NOTIONS D’ARBRES

ARBRES : DÉFINITION 1
 Un arbre est un graphe non orienté connexe qui
ne contient pas de cycle
 Explications de la définition
 Non orienté : pas de flèche aux arêtes
 Connexe : possibilité, à partir de n’importe quel sommet, de
rejoindre tous les autres en suivant les arêtes
 Pas de cycle : pas de boucle au sein du graphe

 Pourun arbre, on citera davantage nœud d’un

graphe, synonyme de sommet
ARBRES : EXEMPLES

Un arbre généalogique
ARBRES : CATÉGORIES
 Unarbre enraciné est un arbre hiérarchique dans
lequel on peut établir des niveaux. Il ressemblera
plus à un arbre généalogique tel qu'on le conçoit
couramment

Cf. Exemple 1 (de la dia précédente)

ARBRES : CATÉGORIES
 Un arbre non enraciné est un arbre où il n'y a pas
de relation d'ordre ou de hiérarchie entre les
éléments qui composent l'arbre

Cf. Exemple 2
ARBRES ENRACINÉS : TERMINOLOGIE
 Chaque nœud a un père et un seul
 Un seul nœud n’a pas de père, appelé racine

Exemples
• 2 a comme seul père
le nœud 1
• 9 a comme seul père
le nœud 7
• …
• 1 n’a pas de père ; il
est appelé racine de
l’arbre
ARBRES ENRACINÉS : TERMINOLOGIE
 Les fils d’un nœud p sont les nœuds dont le père
est p
 Les feuilles d’un arbre sont les nœuds qui n’ont
pas de fils, sinon c’est un nœud interne

Exemples
• 3 a comme fils 7 et 8
• 7 n’a qu’un fils:9
• 9 est un nœud interne
• Les nœuds de 1 à 8 sont
appelés feuilles
ARBRES ENRACINÉS : EXEMPLE
ARBRES BINAIRES
 Les arbres binaires sont des arbres enracinés
dont les nœuds n’ont jamais plus de 2 fils (donc
0, 1 ou 2 fils)
 Dans le cas de 2 fils -> on parle de fils gauche et
de fils droit
ARBRE BINAIRE : EXEMPLE
ARBRES BINAIRES : EXEMPLES
Arbre avec 0, 1, 2 ou 3 arêtes
CODAGE DES ARBRES BINAIRES
Chaque arête est étiquetée par 0 si fils gauche par
1 si fils droit
CODAGE DES ARBRES BINAIRES
 L’étiquette du chemin qui mène de la racine à un
nœud est la suite des nombres binaires
rencontrés 
 Le code de l’arbre A est l’ensemble des
étiquettes des chemins issus de la racine
 Code de l’exemple:
PARCOURS D’ARBRE
 Un parcours d’arbre est une énumération des
nœuds de l’arbre
 Chaque parcours définit un ordre sur les nœuds,
déterminé par leur ordre d’apparition dans cette
énumération
PARCOURS D’ARBRE
 Exemple de parcours d’arbre 
Un parcours d’arbre :
F-B-A-D-C-E-G-I-H
PARCOURS D’ARBRE
On définit trois parcours privilégiés qui sont

 le parcours préfixe: chaque nœud est visité avant que ses fils
soient visités, en abrégé NGD (Nœud, Gauche, Droite)

 le parcours infixe: chaque nœud est visité après son fils

gauche mais avant son fils droit, en abrégé GND (Gauche,
Nœud, Droite)

 le parcours suffixe, ou postfixe : chaque nœud est visité après

que ses fils soient visités, en abrégé GDN (Gauche, Droite,
Nœud)
PARCOURS D’ARBRES : EXEMPLE 1
EXPRIMEZ SON PARCOURS PRÉFIXE
(NGD)

Réponse :

5-9-7-4-2-3

Cliquez sur la
forme pour voir
la réponse

C’est le plus intuitif

EXPRIMEZ SON : PARCOURS INFIXE
(GND)

Réponse :

7-9-4-5-2-3

Cliquez sur la
forme pour voir
la réponse
EXPRIMEZ SON PARCOURS POSTFIXE
(GDN)

Réponse :

7-4-9-3-2-5

Cliquez sur la
forme pour voir
la réponse
PARCOURS D’ARBRES : EXEMPLE 2
EXPRIMEZ SON PARCOURS PRÉFIXE
(NGD)

Réponse :

a-b-d-e-h-c-f-i-g-k

Cliquez sur la
forme pour voir
la réponse
EXPRIMEZ SON : PARCOURS INFIXE
(GND)

Réponse :

d-b-h-e-a-f-i-c-k-g

Cliquez sur la
forme pour voir
la réponse
EXPRIMEZ SON : PARCOURS POSTFIXE
(GDN)

Réponse :

d-h-e-bi-f-k-g-c-a

Cliquez sur la
forme pour voir
la réponse
APPLICATION 1 : EXPRESSIONS
ARITHMÉTIQUES

Les nœuds n’ont pas toujours la même spécificité. Dans ce

cas, les feuilles sont des lettres et les autres nœuds des
opérations arithmétiques
APPLICATION 1 : EXPRESSIONS
ARITHMÉTIQUES

 Réalisez le parcours infixe

Réponse : a + b x c – d : e + f
APPLICATION 1 : EXPRESSIONS
ARITHMÉTIQUES

 Pour le parcours infixe, on ajoute la convention

suivante : on ajoute une parenthèse ouvrante à
chaque fois qu’on entre dans un sous-arbre et on
ajoute une parenthèse fermante lorsqu’on quitte ce
sous-arbre -> lève les ambiguités
 L’arithmétique suit la norme du parcours infixe

(a + b) x (c – d) : (e + f)
APPLICATION 1 : EXPRESSIONS
ARITHMÉTIQUES

 Réalisez le parcours infixe

Réponse : a + b x c – d : e + f

Faites ensuite l’exercice inverse : partez du parcours obtenu et voyez

comment vous auriez pu reconstruire l’arbre
APPLICATION 1 : EXPRESSIONS
ARITHMÉTIQUES

 Réalisez le parcours postfixe

Réponse : a b + c d – x e f + :
APPLICATION 1 : EXPRESSIONS
ARITHMÉTIQUES

 Pour le parcours postfixe, on lui associe la

notation polonaise inversée -> Utilisée par les
calculatrices HP (1960-1970)
 Avantages : fonctionne sans parenthèse
APPLICATION 1 : EXPRESSIONS
ARITHMÉTIQUES

 Réalisez le parcours postfixe

Réponse : a b + c d – x e f + :

Faites ensuite l’exercice inverse : partez de la réponse obtenue et voyez

comment vous auriez pu reconstruire l’arbre
APPLICATION 2 : EXPRESSIONS
ARITHMÉTIQUES
Exemple : (y/2-t)*(75+z)
 A partir de l’expression (parcours infixe)
représentez l’arbre

Cliquez sur la
forme pour voir
la réponse
APPLICATION 2 : EXPRESSIONS
ARITHMÉTIQUES
 Notation polonaise inversée :
 = parcours postfixe

 L’exemple donne :
y 2 / t – 75 z + x
APPLICATION 3 : EXPRESSIONS
BOOLÉENNES
Exemple : Non(((non x1) et x2) ou (x3 et x4))
 Représentez l’arbre
Rappel : les variables x1, .., x4 sont les feuilles de l’arbre
 Réalisez la notation polonaise inverse
COMPRESSION DE DONNÉES : CODAGE
DE HUFFMAN
 Tout fichier informatique est constitué de
caractères. Un caractère est une lettre (majuscule
ou minuscule), un chiffre, un signe de
ponctuation ou un symbole non imprimable
 De façon générale, à tout caractère sur le clavier
est associé un mot binaire
 Cet ensemble de caractères est appelé code
ASCII (ASCII étendu -> 8bits)
CODAGE DE HUFFMAN
 Partie du code ASCII
CODAGE DE HUFFMAN : MÉTHODE
 Parmi ces caractères, certains sont plus
fréquemment employés que d’autres
 Plus astucieux donc d’utiliser des mots binaires
de longueur variable :
o Associer des mots binaires courts aux
caractères les plus employés
o Réserver les mots longs aux caractères
rarement utilisés

OBJECTIF : COMPRESSION
CODAGE DE HUFFMAN : ARBRE
 Les feuilles sont étiquetées avec les caractères
originaux, les arêtes par 0 ou 1
 Les chemins depuis la racine jusqu'aux feuilles
épellent les codes des caractères originaux (code
préfixe)
 Le fils gauche d’un nœud est étiqueté par 0, le
fils droit par 1
CODAGE DE HUFFMAN : ALGORITHME
 Comptage des fréquences des caractères
 Initialisation : création liste des nœuds
candidats : chaque caractère à coder est un
nœud (associé à sa fréquence/poids)
 Tant que nous avons au moins deux nœuds dans
la liste des nœuds candidats :
o On identifie deux nœuds de fréquence la plus faible
de la liste actuelle des nœuds candidats
o Nous les relions à l’aide d’un nouveau nœud, le père
dont son poids sera la somme des poids de ses fils
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 Initialisation : liste des nœuds candidats : chaque
caractère à coder est une feuille de l’arbre
(associé à sa fréquence)
o On détermine la fréquence de chaque

caractère
o On ignore ici les espaces

o Ordonné selon leur fréquence (si égal, selon

code ANSI)
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 Tableau :

Caractère a c e h i n r t

fréquence 3 4 3 4 1 1 2 2
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 Feuilles de l’arbre: par ordre croissant des
fréquences

i n r t a c h
e3
1 1 2 2 3 4 4
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 Tant que au moins deux nœuds : on identifie 2
nœuds de fréquence plus faible*:

i n r t a c h
e3
1 1 2 2 3 4 4

*: En cas d’égalité, priorité au 1er caractère selon

ordre codage ANSI
Placer le plus vite possible les feuilles
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 On les «relie» par un père ayant la somme des
fréquences (=son seul contenu)

i n r t a c h
e3
1 1 2 2 3 4 4
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 Nouvelle itération : les deux caractères de
fréquence minimale sont …

2 4

i n r t a c h
e3
1 1 2 2 3 4 4
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 Nouvelle itération : les deux caractères de
fréquence minimale sont …
5

a
2 4
3

i n r t c h
e3
1 1 2 2 4 4

On a choisi le caractère a (priorité au code ANSI)

CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 Nouvelle itération : les deux caractères de
fréquence minimale sont …
 Et ainsi de suite jusqu’à ce qu’il ne reste plus
deux nœuds à pouvoir être reliés (autrement dit
jusqu’à ce qu’on arrive à la racine de l’arbre)
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 On associe un 0 à chaque arête de gauche et 1 à
chaque arête de droite
 Ce qui va nous permettre de coder chaque lettre
(selon le code préfixe)
o Le codage de r donne …
o Le codage de e donne …
CODAGE DE HUFFMAN : EXEMPLE
 Coder la phrase : recherche chat chatain
 La phrase ainsi codée donne:
CODAGE DE HUFFMAN : TAUX DE
COMPRESSION
 Taux de compression = 1 – (taille_texte_ compressé
/ taille_texte_source)
 Dans l’exemple, la phrase contient 20 caractères,
chacun codé sur 8 bits, soit un fichier de poids de
20*8 bits (160)
 Le nombre de bits obtenu par l’algorithme est de …
 Taux de compression = …

* compris entre 0 et 1
CODAGE DE HUFFMAN : EXEMPLE2
 Coder le mot abacebd
CODAGE DE HUFFMAN : EXEMPLE3
EXERCICES SUPPLÉMENTAIRES
 Donner le parcours préfixe, infixe et suffixe de
l’arbre suivant:
EXERCICES SUPPLÉMENTAIRES
 Déterminer l’arbre de l’expression :

 Déterminer la notation polonaise inversée

correspondante
EXERCICES SUPPLÉMENTAIRES
 Coder à l’aide de Huffman le mot suivant:
« cagataagagaa »
CODAGE ANSI OU WINDOWS-1252