ISET Nabeul

LOG
O

Cours Algorithmique ii

Classe: TI1*
Enseignantes: Mme Afef FKIRI
 ISET Nabeul

LOG
O

Chapitre 5:
Les structures Arborescentes
 Introduction

 Des nombreuses informations peuvent être organisées sous

forme arborescente telles que : un arbre généalogique, un
dictionnaire, une expression syntaxique, une relation
d’inclusion.
 Il est fortement nécessaire d’étudier cette structure de données.

3
Définitions, Notations et représentations

 Définition générale d’un arbre :

 On peut donner cette définition récursive : Un arbre est :
- Soit vide
- Soit constitué d’un élément auquel sont rattachés 1 ou
plusieurs arbres.

4
Définitions, Notations et représentations
 Terminologie :

 Un arbre est constitué des sommets ou nœuds. EXP A, B, C, D,

E, F, G
 Un nœud possède un certain nombre des fils. EXP A possède B
et C comme fils.
 Chaque nœud possède 1 seul père sauf la racine qui n’a pas de
père. EXP Le père de D est B, A n’a pas de père (c’est la racine
de l’arbre).
5
 Le lien qui relie 2 nœuds s’appelle Arc ou Branche.
Définitions, Notations et représentations
 Arbre n-aire et Arbre binaire :
 Un arbre est dit n-aire Lorsqu’il admet pour chaque nœud au
plus n fils.

 Si n=2, l’arbre est dit « Binaire », si n=1, l’arbre est dit liste ou
arbre dégénéré. 6
Définitions, Notations et représentations
 Arbre n-aire et Arbre binaire :
 Un arbre binaire est
• Soit vide.
• Soit composé d’un élément auquel sont chaînés un sous-arbre
gauche et un sous-arbre droit.

7
Définitions, Notations et représentations
 Représentation d’un arbre binaire :
 La représentation chaînée des arbres binaires

TYPE Arbre = ↑ Nœud

TYPE Nœud = ENREGISTREMENT

Gauche : Arbre

Droite : Arbre

Info : élément

FIN ENREGISTREMENT

8
 Définitions, Notations et représentations
 Soit l’arbre suivant :

 Racine : contenant l’adresse du nœud

racine de l’arbre. Si l’arbre n’est pas
vide (Racine <> NIL).
 Racine↑.Info : l’information du nœud.
 Racine↑.Gauche : sous-arbre gauche.

 Racine↑.Droite : sous-arbre droit. 9

Définitions, Notations et représentations
 Niveau:
 On dit que 2 nœuds sont à un même niveau dans un arbre, s’ils
sont issus d’un même nœud après le même nombre de filiations.
 Exemple:

10
Définitions, Notations et représentations
 Mot des feuilles d’un arbre binaire:
 Le mot des feuilles d’un arbre binaire est la chaîne formée de
gauche à droite de la valeur des feuilles de l’arbre.
 Exemple Pour l’arbre de la figure précédente, le Mot des
feuilles est « DEH ».

11
Définitions, Notations et représentations
 Arbre binaire complet:
 Si chaque nœud autre qu’une feuille admet exactement 2
descendants et si toutes les feuilles sont au même niveau, on dit
que l’arbre binaire est « complet »,
 La taille d’un arbre binaire complet = 2k-1 où k est le niveau des
feuilles.

12
Définitions, Notations et représentations
Hauteur d’un nœud:
 La hauteur d’un arbre est égale
au maximum du niveau des
feuilles.
• La hauteur d’un arbre est
égale à la hauteur de sa
racine.
• La hauteur d’un arbre vide =
=Max + 1
0
• La hauteur d’un nœud = au
maximum des hauteurs du
sous-arbre gauche et du Max = 1
sous-arbre droit + 1.
13
Définitions, Notations et représentations
 Facteur d’équilibre :
 Le facteur d’équilibre de chaque sous-arbre est associé à sa racine.
 Le facteur d’équilibre d’un nœud = hauteur du sous-arbre gauche –
hauteur du sous-arbre droit

14
Définitions, Notations et représentations

 Arbre équilibré :
 Un arbre est dit équilibré si pour tout nœud p de cet arbre, la
valeur absolue de facteur d’équilibre est inférieure ou égale à 1.
 |facteur d’équilibre (p)| <=1
 L’arbre de la figure précédente n’est pas équilibré car il existe
des nœuds tels que A, E qui possèdent des facteurs d’équilibre
dont la valeur absolue > 1.

15
Définitions, Notations et représentations

 Arbre équilibré :Exemple d’arbre équilibré

16
Définitions, Notations et représentations
 Arbre dégénéré:
 Un arbre est dit dégénéré si tous les nœuds de cet arbre ont au
plus un descendant.
 Un arbre dégénéré est équivalent à une liste linéaire.
 Exemple:

17
Définitions, Notations et représentations

 Arbre ordonné (de Recherche) :

 Dans un arbre ordonné, chaque valeur d’un nœud est telle que :
• (Nœud↑.droite <> NIL et Nœud↑.gauche<> NIL et
Nœud↑.gauche↑.info < Nœud↑.info <= Nœud↑.droite↑.info)
• Ou(Nœud↑.droite = NIL et Nœud↑.gauche<> NIL et
Nœud↑.gauche↑.info < Nœud↑.info)
• Ou(Nœud↑.droite <> NIL et Nœud↑.gauche = NIL et
Nœud↑.info <= Nœud↑.droite↑.info)
 Un arbre vide et un arbre réduit à un seul élément sont
ordonnés.
 Tous les sous-arbres d’un arbre ordonné sont ordonnés.
18
 Arbres binaires
 Parcours d’un arbre binaire :

 Les parcours préfixé, infixé, postfixé.

19
 Arbres binaires
 Parcours d’un arbre binaire : Préfixé
 Ce parcours consiste à effectuer dans l’ordre :
1. Le parcours de la racine (Son traitement)
2. Le parcours du sous-arbre gauche.
3. Le parcours du sous-arbre droit.
 Pour l’arbre précèdent, on traite les nœuds dans cet ordre :
A, B, F, P, M, H, J, C, D, I, R, E
1

2 8

3
6
9 12
7
4 5 20
10 11
 Arbres binaires
 Parcours d’un arbre binaire : Infixé
 Ce parcours consiste à effectuer dans l’ordre :
1. Le parcours du sous-arbre gauche.
2. Le parcours de la racine (Son traitement)
3. Le parcours du sous-arbre droit.
 Pour l’arbre précèdent, on traite les nœuds dans cet ordre :
P, F, M, B, H, J, A, I, D, R, C, E
7

4 11

2
5
9 12
6
1 3 21
8 10
 Arbres binaires
 Parcours d’un arbre binaire : Postfixé
 Ce parcours consiste à effectuer dans l’ordre :
1. Le parcours du sous-arbre gauche.
2. Le parcours du sous-arbre droit.
3. Le parcours de la racine (Son traitement)
 Pour l’arbre précèdent, on traite les nœuds dans cet ordre :
P, M, F, J, H, B, I, R, D, E, C, A
12

6 11

3
5
9 10
4
1 2
7 822
 Arbres binaires
 Parcours d’un arbre binaire : Préfixé
 Version récursive de l’algorithme

PROCEDURE Préfixé (Racine : Arbre)

DEBUT
SI Racine <> NIL ALORS
Traiter (Racine)
Préfixé (Racine↑.gauche)
Préfixé (Racine↑.droite)
FIN SI
FIN
 Arbres binaires
 Parcours d’un arbre binaire : Préfixé
 Version récursive de l’algorithme

Afficher(A)
Préfixé(B) Afficher(B)
Préfixé(D) Afficher(D)
Préfixé(Nil)
Préfixé(Nil)
Préfixé(E) Afficher(E)
Préfixé(Nil)
Préfixé(Nil)
Préfixé(F) Afficher(F)
Préfixé(Nil)
Préfixé(G) Afficher(G)
Préfixé(H) Afficher(H) A B D E F G H
Préfixé(Nil)
Préfixé(Nil)
Préfixé(Nil)
 Arbres binaires
 Parcours d’un arbre binaire : Préfixé
 Version Itérative de l’algorithme
Rac ←rac↑.gauche
FIN FAIRE PROCEDURE Préfixé (Racine : Arbre)
Dépiler (p, rac) VAR
Rac ←rac↑.droite Rac : Arbre, p : Pile
FIN FAIRE DEBUT
FIN Init_pile (p)
Rac ←Racine
TANT QUE (rac <> NIL) ou (non Pile_vide
(p)) FAIRE
TANT QUE rac <> NIL FAIRE
Traiter (rac)
Empiler (p, rac)
 Arbres binaires
 Parcours d’un arbre binaire : Préfixé
 Version Itérative de l’algorithme
Rac

@D
@B
@H A B D E F G H
@A
@G
@F
Nil
@
@
P Nil
 Arbres binaires
 Parcours d’un arbre binaire : Préfixé
 Version Itérative de l’algorithme

Jusqu’à
Afficher (rac) rac = NIL
Empiler (p, rac)
Jusqu’à Rac ←rac↑.gauche
rac = NIL

@D
@D Dépiler (p, rac)
Rac ←rac↑.droite
@D
@D
@B
@E
@D
@H
@G
@D
@F
@A
@D
A B D E F G H
Rac @H
@G
Nil
@H
Nil
@E
@F
@G
@E
NIL
@B
Nil
Nil
@A
@B
@A
@D
P Nil
@
 Arbres binaires
 Parcours d’un arbre binaire : Infixé
 Version récursive de l’algorithme

PROCEDURE Infixé (Racine : Arbre)

DEBUT
SI Racine <> NIL ALORS
Infixé (Racine↑.gauche) Traiter
(Racine)
Infixé (Racine↑.droite)
FIN SI
FIN
 Arbres binaires
 Parcours d’un arbre binaire : Infixé
 Version Itérative de l’algorithme
FIN FAIRE PROCEDURE Infixé (Racine : Arbre)
Dépiler (p, rac) VAR
Traiter (rac) Rac : Arbre, p : Pile
Rac ←rac↑.droite DEBUT
FIN FAIRE Init_pile (p)
FIN Rac ←Racine
TANT QUE (rac <> NIL) ou (non Pile_vide
(p)) FAIRE
TANT QUE rac <> NIL FAIRE
Empiler (p, rac)
Rac ←rac↑.gauche
 Arbres binaires
 Parcours d’un arbre binaire : Postfixé
 Version récursive de l’algorithme

PROCEDURE Postfixé (Racine : Arbre)

DEBUT
SI Racine <> NIL ALORS
Postfixé (Racine↑.gauche)
Postfixé (Racine↑.droite)
Traiter (Racine)
FIN SI
FIN
 Arbres binaires
 Parcours d’un arbre binaire : Postfixé
 Version Itérative de l’algorithme
Dépiler (p, (Rac, indic)) PROCEDURE Postfixé (Racine : Arbre)
SI Indic = VRAI ALORS VAR
Empiler (p,(Rac,faux)) Rac : Arbre, p : Pile
Rac ←Rac↑.droite Indic : booléen
SINON DEBUT
Traiter (Rac) Init_pile (p)
Rac ← NIL Rac ←Racine
FINSI TANT QUE (rac <> NIL) ou (non Pile_vide
FIN FAIRE (p)) FAIRE
FIN TANT QUE rac <> NIL FAIRE
Empiler (p, (rac, vrai))
Rac↑.gaucheRac ←
FIN FAIRE
 Arbres binaires
 Algorithmes sur les arbres binaires
 Calcul de la taille d’un arbre binaire

FONCTION Taille (Racine : Arbre) : entier

DEBUT
SI Racine = NIL ALORS
RETOURNER (0)
SINON
RETOURNER (1+Taille (Racine↑.gauche) + Taille (Racine↑.droite))
FIN SI
FIN
 Arbres binaires
 Algorithmes sur les arbres binaires
 Nombre des feuilles d’un arbre binaire
FONCTION Feuille (Nœud : Arbre) : Booléen
DEBUT
RETOURNER ((Nœud↑.gauche = NIL) et (Nœud↑.droite = NIL))
FIN

FONCTION Nb_feuille (Racine : Arbre) : entier

DEBUT
SI Racine = NIL ALORS
RETOURNER (0)
SINON
SI Feuille (Racine) ALORS
RETOURNER (1)
SINON
RETOURNER (Nb_feuille (Racine↑.gauche) +Nb_feuille (Racine↑.droite))
FIN SI
FIN SI
FIN
 Arbres binaires
 Algorithmes sur les arbres binaires
 Vérifier qu’un arbre n’est pas dégénéré

FONCTION Normal (Racine : Arbre) : booléen

DEBUT
SI Racine = NIL ALORS
RETOURNER (FAUX)
SINON
SI (Racine↑.gauche <> NIL) et (Racine↑.droite <>NIL) ALORS
RETOURNER (VRAI)
SINON
SI (Racine↑.gauche = NIL) ALORS
RETOURNER (Normal (Racine↑.droite))
SINON
RETOURNER (Normal (Racine↑.gauche))
FIN SI
FIN SI
FIN SI
FIN
 Arbres binaires
 Algorithmes sur les arbres binaires
 Recherche associative dans un arbre binaire
FONCTION Recherche (Racine : Arbre, val : élément) : booléen
DEBUT
SI Racine = NIL ALORS
RETOURNER (FAUX)
SINON
SI Racine↑.info = val ALORS
RETOURNER (VRAI)
SINON
SI Recherche (Racine↑.gauche, val) ALORS
RETOURNER (VRAI)
SINON
RETOURNER (Recherche (Racine↑.droite, val))
FIN SI
FIN SI
FIN SI
FIN