31/01/2021

Introduction:
Inconvénients des structures séquentielles :
– En format contigu, les mises à jour sont
fastidieuses,
Chapitre 3 – En format chaîné, les parcours sont de
Les structures arborescentes complexité linéaire.
􀂄 Les structures arborescentes permettent une
amélioration globale des accès aux informations

N. HADI N. HADI
79 80
2019/2020 2019/2020

Exemple 1: une expression arithmétique peut être représentée par

un arbre en utilisant les priorités usuelles:
Place des arbres en informatique ((x – (2*y)) + (3*((y / z) + x)) )
La structure d’arbre est l’une des structures les plus importantes
et des plus spécifiques de l’informatique. +
Les systèmes d’exploitation (Windows, Unix) organisent les
fichiers/répertoires sous forme d’arbre. _
*

Les compilateurs utilisent la structure d’arbre pour représenter

la syntaxe d’un programme et détecter les éventuelles erreurs *
+
x 3
syntaxiques.
Les arbres sont les structures de données, les mieux adaptées /
aux algorithmes issus de l'intelligence artificielle. 2
y x

y z

N. HADI N. HADI
81 82
2019/2020 2019/2020

Exemple 3: Un type de donnée structuré peut être représenté sous format d’arbre
Exemple 2 : Structure d'un dictionnaire composé des mots suivants dans tout langage de programmation :
{AIL, AIN, AIR, AXE, AS, ANE, ANTE, ANTI, ANS, ANGE, ANGU} Type Date = structure {Jour, Mois, An : entier} ;
Type Lieu = structure { Ville : Chaîne (30) ; Département: Chaîne (20) } ;
A Type Identité = structure { Nom, Prénom: Chaîne (30) ; Dat-Nais : date ;Lieu-nais :
Lieu} ;
N Type Etablissement = structure { Université: Chaîne (30) ; Lieu-etud : Lieu} ;
I Type Etudiant = structure {Inscription : Etablissement ; Filiation : Identité} ;
X
S

G
Etudiant

T
S Inscription Filiation
L N R E E

Université Lieu-etud Nom Prénom Dat-nais Lieu-nais

E I E U
Ville Département Mois Jour AN Ville Département

N. HADI N. HADI
83 84
2019/2020 2019/2020

1
 31/01/2021

Propriété des arbres

Une propriété inhérente à la structure d’arbre est la récursivité. Exemples:
On écrit très naturellement de manière récursive :
Les définitions caractéristiques des arbres
Les algorithmes qui manipulent les arbres

Qu’est-ce qu’un arbre ?

Un arbre A est un ensemble fini, éventuellement vide, de nœuds
organisés hiérarchiquement comme suit :
Il existe un nœud particulier appelé racine de l’arbre A.
Les autres nœuds (s’ils existent) sont organisés en m classes
disjointes A1, A2, Am. Chacune de ces classes étant elle
même structurée en arbre : On parle des « sous-arbres » de la
racine.
N. HADI N. HADI
85 86
2019/2020 2019/2020

Terminologie associée aux arbres

La terminologie utilisée pour les arbres informatiques s’inspire du Feuilles et branches:
vocabulaire de la botanique et de la généalogie. Un nœud qui n’a pas de fils est un
Notion de noeud: Nœud externe ou nœud terminal
Tout nœud d’un arbre donne accès à : ou feuille. Les nœuds d, e, f, g et i
Un élément de l’arbre (si l’arbre est étiqueté) sont des feuilles.
Aux nœuds du sous-arbre dont il est la racine Un nœud qui a au moins un fils est
Relations entre nœuds: un nœud interne ou nœud non
Le noeud b est père des nœuds d, e et f terminal. Les nœuds b, c, h sont internes
Les noeuds d, e et f sont les fils du noeud b On appelle branche de l’arbre A tout
Les noeuds d, e et f sont frères chemin (suite de nœuds consécutifs) allant
Les noeuds a, c et h sont des de la racine à une feuille de A.
Un arbre a donc autant de branches
ascendants ou ancêtres du noeud i
Le noeud i est un descendant des nœuds que de feuilles.
a, c et h

N. HADI N. HADI
87 88
2019/2020 2019/2020

Pour calculer la hauteur d'un arbre, nous allons nous baser sur la définition récursive :

Notion de Profondeur (Hauteur)

La profondeur d’un nœud : (ou hauteur ou niveau) est le Importants
nombre de liens du chemin allant de la racine à ce nœud. La hauteur de l'arbre est alors la profondeur maximale de
La profondeur P d’un nœud x d’un arbre A est définie ses nœud. C'est à dire la profondeur à laquelle il faut
récursivement comme suit : descendre dans l'arbre pour trouver le nœud le plus loin de la
racine.
On peut aussi définir la hauteur de manière récursive : la
hauteur d'un arbre est le maximum des hauteur de ses fils.
La profondeur d’un arbre : (ou hauteur) est le niveau  C'est à partir de cette définition que nous pourrons
maximal de ses feuilles. exprimer un algorithme de calcul de la hauteur de l'arbre.
 La hauteur d'un arbre est très importante. En effet, c'est un
repère de performance. La plupart des algorithmes que nous
verrons dans la suite ont une complexité qui dépend de la
Donc Pour calculer la hauteur d'un arbre, nous hauteur de l'arbre.
allons nous baser sur la définition récursive : Ainsi plus l'arbre aura une hauteur élevée, plus l'algorithme
-un arbre vide est de hauteur 0 mettra du temps à s'exécuter.
-un arbre non vide a pour hauteur 1 + la hauteur
maximale entre ses fils. N. HADI
89
N. HADI
90
2019/2020 2019/2020

2
 31/01/2021

Qu’est-ce qu’un arbre binaire ?

•Un arbre binaire est un arbre ordonné tel que tout noeud a
au plus deux fils.
•La structure d’arbre binaire est utilisée dans de très
nombreuses applications informatiques.
3-1 LES ARBRES BINAIRES •De plus les arbres généraux peuvent toujours être représentés
par des arbres binaires.
•Pour les Exemples précédents:
L’exemple 1 est représenté par un arbre binaire, alors que les
exemples 2 et 3 sont des arbres généraux.
•Définition : un arbre binaire est soit vide, soit de la forme B =
<0, B1, B2> où B1 et B2 sont des arbres binaires disjoints et '0' un
nœud appelé racine.
Remarque:
'0' est appelé racine de l'arbre B, B1 est appelé sous arbre gauche,
B2 sous arbre droit de B.
Il faut noter la non symétrie gauche et droite des arbres binaires
N. HADI
2019/2020
91 <0, B1, B2>  <0, B2, B1>. N. HADI
2019/2020
92

Définition
Un arbre binaire est un ensemble fini qui est :
ou bien vide
Exemple 1 ou bien composé d’une racine et de deux sous-arbres
Exemple 2
binaires respectivement appelés sous-arbre gauche et sous-
arbre droit.
Notations
Arbre binaire B vide
B=ᶲ
Arbre binaire B non vide
B = < r, Bg, Bd >
Définition récursive d’un arbre binaire
B = ᶲ + < r, B, B >

N. HADI N. HADI
93 94
2019/2020 2019/2020

Arbres binaires particuliers : 2-Arbre binaire complet

1-Arbre binaire dégénéré •Un arbre binaire complet est un
Un arbre binaire dégénéré ou arbre où tout noeud autre qu’une
filiforme est un arbre où tout nœud feuille a deux fils et toutes les
autre qu’une feuille a un seul fils. feuilles ont même niveau.
•On dit que chaque niveau d’un tel
arbre est complètement rempli,
Un arbre binaire dégénéré est un c’est-à-dire, que l’arbre contient :
arbre formé uniquement de 1 nœud au niveau 0
points simples: c'est une liste. 2 nœuds au niveau 1
4 nœuds au niveau 2
…
2n nœuds au niveau n

N. HADI N. HADI
95 96
2019/2020 2019/2020

3
 31/01/2021

Arbre binaire parfait

•Un arbre binaire <0, B1, B2> est dit arbre équilibré si les
Un arbre binaire parfait est un arbre où chaque niveau est
tailles de B1 et B2 sont égales.
complètement rempli, sauf éventuellement le dernier niveau.
•Un peigne gauche (respectivement peigne droit) est un arbre
Cependant, si le dernier niveau n’est pas complètement rempli, les
binaire localement complet dans lequel tout fils droit
Nœuds présents sont regroupés à gauche de l’arbre.
(respectivement gauche) est une feuille.

Peigne gauche Peigne droit

N. HADI N. HADI
97 98
2019/2020 2019/2020

Compte tenu de la nature récursive d’un arbre, la

représentation la plus couramment utilisée est celle
chaînée dont le principe est de désigner un arbre
binaire par un ensemble de cellules mémoire à trois
champs :
G Val D

3-2 Représentation chaînée par pointeurs G est un pointeur vers le sous arbre gauche.
 Val représente l'information apportée par le
nœud pour un arbre étiqueté.
 D est un pointeur vers le sous arbre droit.

L’accès à un arbre est donc déterminé par l'adresse (pointeur)

de sa racine.

N. HADI N. HADI
99 100
2019/2020 2019/2020

On a la définition (déclaration) suivante : Remarques:

Type cellule = Structure {Val : type; G, D : pointeur sur cellule}; Arbre A est vide : A = nil
Type Arbre = pointeur sur cellule; Accès à l’élément (étiquette) du nœud A : *A.val
Exemple: Le sous-arbre gauche de A est non vide si : *A.g ≠ nil
Accès au sous-arbre gauche de A : *A.g
Le sous-arbre droit de A est non vide si : *A.d ≠ nil
Accès au sous-arbre droit de A : *A.d

N. HADI N. HADI
101 102
2019/2020 2019/2020

4
 31/01/2021

Parcours d’un arbre binaire:

L’opération de parcours d’un arbre consiste à examiner
systématiquement (visiter), dans un certain ordre, chacun des
nœuds de l’arbre pour y effectuer un même traitement.
L'algorithme le plus utilisé appelé parcours en profondeur à main
gauche consiste à tourner autours de l'arbre en partant à gauche de
la racine et en allant toujours le plus à gauche possible en suivant
l'arbre.
3-3 Parcours d’un arbre binaire Dans ce parcours, chaque nœud est rencontré exactement 3 fois:
1- A la descente:

2- En remontée à gauche après le sous arbre gauche :

3- En remontée à droite après le sous arbre droit :

N. HADI N. HADI
103 104
2019/2020 2019/2020

Un parcours en profondeur à gauche est simple à +

comprendre, cela signifie que l'on parcours les
branches de gauche Algorithme récursif de parcours :
avant les branches de droite.
On aura donc deux types de parcours :
Lors d'un parcours en profondeur à main gauche d'un arbre B,
_
un parcours à gauche et un parcours à droite. * on peut faire correspondre à chacune des rencontres (passage)
Dans la plupart des cas, nous utiliserons
un parcours à gauche. d'un nœud un traitement particulier.
x
*
3 + Soient traitement 1 (respectivement traitement 2 puis
traitement 3) la suite d'actions à exécuter lorsqu'on passe pour la
/
première fois (respectivement la deuxième fois puis la troisième
2
y x fois).
On envisage pour les arbres vides un traitement spécial appelé
y
z TERMINAISON.
On Suppose de plus que B est implémenté sous forme chaînée.

Exemple : Parcours en profondeur

à main gauche de l’arbre binaire
associé à l’expression arithmétique
(X-(2*Y))+(3*((Y/Z)+X))
N. HADI N. HADI
105 106
2019/2020 2019/2020

Algorithme récursif de parcours

La deuxième caractéristique de notre arbre est:
Procédure Parcours (↓↑ B :ArbreP)  le parcours dit préfixe. Cela signifie que l'on affiche la racine de l'arbre, on
Début parcourt tout le sous arbre de gauche, une fois qu'il n'y a plus de sous arbre
Si (B = Vide) alors TERMINAISON gauche on parcourt les éléments du sous arbre droit.
Sinon Ce type de parcours peut être résumé en trois lettres :
Traitement 1; R G D (pour Racine Gauche Droit).
On a aussi deux autres types de parcours :
Parcours (*B.G); le parcours infixe et le parcours suffixe (appelé aussi postfixe).
Traitement 2; Le parcours infixe affiche la racine après avoir traité le sous arbre gauche,
Parcours (*B.D); après traitement de la racine, on traite le sous arbre droit
Traitement 3; (c'est donc un parcours G R D).
FSi;  Le parcours postfixe effectue donc le dernier type de schéma :
sous arbre gauche, sous arbre droit puis la racine, c'est donc un parcours G D R.
FIN. Bien sur, nous avons fait l'hypothèse
d'un parcours à gauche d'abord mais on aurait pû aussi faire un parcours à droite
d'abord.
Les types de parcours infixe, suffixe et postfixe sont les plus importants,
N. HADI
en effet chacun à son application particulière.
N. HADI
107 108
2019/2020 2019/2020

5
 31/01/2021

Exemple:
Ordres de parcours en profondeur:

Donc Le parcours en profondeur à main gauche contient

comme cas particuliers 3 ordres classiques d'exploration
d'arbre :

1. Ordre préfixé ou parcours en pré-ordre : les nœuds sont

traités à la descente (1ère rencontre). Le père est traité avant
les fils.
2. Ordre infixé ou symétrique : les nœuds sont traités à la
remontée gauche (2ème rencontre). Le père est traité après
son fils gauche et avant son fils droit.
3. Ordre postfixé ou parcours en post-ordre ou terminal : les
Nœuds sont traités à la remontée droite (3ème rencontre). Le
père est traité après les fils.

N. HADI N. HADI
109 110
2019/2020 2019/2020

Procédure préordreréc (↓↑A : racine de l’arbre) Procédure infixéréc (↓↑A : racine de l’arbre)
début début
si (A ≠ arbrevide) Alors traiter (A) Si ( A ≠ arbrevide) alors infixéréc (g(A));
préordreréc (g(A)) traiter (A);
préordreréc (d(A)) infixéréc (d(A))
Fsi; Fsi;
Fin. Fin.
NB: A est un élément d’accès à la racine de l’arbre NB: A est un élément d’accès à la racine de l’arbre
(pointeur ou indice) (pointeur ou indice)
Traitement 2 et Traitement 3 n'existent pas, Traitement 1 C'est l'ordre obtenu lorsque seul traitement 2 (et terminaison)
est appliqué aux nœuds de l'arbre. sont appliqués.
Ce parcours consiste à effectuer dans l’ordre : Ce parcours consiste à effectuer dans l’ordre :
•Le traitement de la racine ; R •Le parcours du sous arbre gauche ; G
•Le parcours du sous arbre gauche ; G •Le traitement de la racine ; R
•Le parcours du sous arbre droit. D •Le parcours du sous arbre droit. D
N. HADI N. HADI
111 112
2019/2020 2019/2020

Exemples:
1-soit la fonction taille qui définie la taille d’un arbre Binaire ABR
Procédure postordreréc (↓↑A : racine de l’arbre)
début Fonction Taille (ABR : PTR) :Entier
si (A ≠arbrevide) alors postordreréc (g(A)); Début
Si (ABR = NIL) alors Taille  0
postordreréc (d(A));
Sinon Taille  1+ Taille(*ABR.G)+ Taille (*ABR.D)
traiter (A) Fsi ;
Fsi; Fin.
Fin. 2-soit la fonction Somme qui calcule la somme des nœuds d’un arbre
NB: A est un élément d’accès à la racine de l’arbre Binaire ABR.
(pointeur ou indice)
Fonction Somme (ABR : PTR) : Entier
seules les actions traitement 3 et terminaison sont appliquées. Début
Ce parcours consiste à effectuer dans l’ordre : Si (ABR= Nil) alors Somme  0
Le parcours du sous arbre gauche ; G Sinon Somme  Somme (*ABR.G) + Somme
Le parcours du sous arbre droit ; D (*ABR.D) + *ABR.val
Fsi ;
Le traitement de la racine. R
Fin.
N. HADI N. HADI
113 114
2019/2020 2019/2020

6
 31/01/2021

3- la fonction moyenne qui calcule la moyenne des nœuds d’un

Arbre Binaire ABR.

Fonction Moyenne (ABR : PTR) : Réel

Début
Si (Taille (ABR)≠ 0)) alors Moyenne  Somme(ABR) / Taille (ABR)
Fsi ;
Fin.

N. HADI
115
2019/2020