| Klouche-Djedid A.Département Informatique-IGMO | |
|---|
CHAPITRE-Les arbres_parcours-implémentation
Définitions :
Graphe orienté
fini : C’est un ensemble fini de points appelés « nœuds » ou
« sommets », associé à un ensemble fini de lignes appelées
« arcs », joignant chacune un nœud à un autre.
Il existe au plus un arc
joignant un nœud origine donné à un nœud extrémité donné. Si A et B sont 2
nœuds, l’arc AB (s’il existe) est différent de l’arc BA (s’il existe).
Arbres : C’est un graphe orienté défini sur un ensemble de nœuds X tel
que :
ü il existe dans X un nœud particulier r appelé la
racine de l’arbre.
ü les autres nœuds , s’il en existe, sont
partitionnés en m sous-ensembles X1,X2,…,Xm , qui sont à leur tour des arbres
de racines respectives r1,r2,…,rm, tels que pour tout i de 1 à m il existe un
arc d’origine r et d’extrémité ri .Ces arbres sont appelés les
« sous-arbres » de X.
r arbre X r1 r2 r3 sous-arbre
X3 r11 r12 r13
r14 r31 r32
r321 r322
fig 1
Filiation : Dans un arbre on définit des relations de
filiation comme suit :
Un nœud B est dit « fils »
d’un autre nœud A s’il existe un arc d’origine A et d’extrémité B. le nœud A
est appelé « père » de B. les fils d’un même père sont dits
« frères ». dans fig1 r31 est
fils de r3
Arbre ordonné : C’est un arbre dans lequel une relation
d’ordre est établie entre les fils d’un même nœud (les frères)
degré : Le degré d’un nœud est égal au nombre de
fils de ce nœud .
deg de r1 = 4
feuille : Les feuilles d’un arbre sont les nœuds de
degré 0 . Une feuille est encore appelée « nœud terminal » et par
opposition, un nœud de degré différent de 0 est appelé « nœud non
terminal ».
niveau : La relation de filiation crée des niveaux
dans un arbre. Le niveau de la racine est 1 et tout nœud fils d’un nœud de
niveau i est au niveau i+1.
niveau de r11 = 3
Profondeur : On appelle profondeur d’un arbre le niveau
maximum de ses nœuds.
arbre n-aire : C’est un arbre dans lequel chaque nœud a
au plus n fils
l’arbre X est 4-aire ; le sous –arbre X3 est binaire
arbre n-aire homogène : un
arbre n-aire est dit homogène, si tous ses nœuds non terminaux sont de degré n.
arbre équilibré : C’est un arbre où tous les nœuds terminaux
ont même niveau.
arbre n-aire complet c’est un arbre
homogène et équilibré.
Les arbres binaires
Un arbre binaire est un arbre ordonné tel que chaque nœud a au plus 2 fils, respectivement appelé « fils
gauche » et « fils droit ».
De tels arbres sont souvent utilisés et ont de multiples applications.
Exemples : représentation d’une expression :toute
opération binaire porte sur 2 opérandes, généralement ordonnés, et peut donc
être représentée par un sous_arbre dont la racine est l’opérateur et dont les
fils gauche et droit sont respectivement le premier et le deuxième opérande.
Ainsi l’opération « A+B » est représentée par le sous_arbre
suivant :
+ A B
de la même manière on représente toute opération unaire par un
sous-arbre dont la racine est
l’opérateur et dont le fils unique représente l’opérande . L’opération
« -C » est représentée comme suit :
_ C
Une expression peut se donc être représentée par un arbre binaire dont la
structure hiérarchique reflète l’ordre d’exécution des opérations constituant
l’expression. Soit à titre d’exemple l’expression suivante :
A**2-B+C*(D/-5)
Conformément à la priorité associée à chaque opérateur, cette expression
peut être interprétée comme suit :
((A**2)- B ) + (C * ( D / -5))
Il s’agit donc d’une addition avec comme 1er opérande (A**2)- B
et comme 2ème opérande C*(D/-5) . Chaque opérande constitue à son
tour une expression et sera donc représenté par un sous-arbre. L’arbre
représentant l’expression est le suivant :
+ _ * ** B C /
_ A 2 D
5
fig4
Parcours d’arbre binaire
parcourir un arbre consiste à examiner une fois et une seule chacun de ses
nœuds , dans un certain ordre. pour un arbre binaire les ordres de parcours les
plus utilsés sont :
parcours pré-ordre : Il est aussi appelé préfixé ;dans cet
ordre de parcours le père est examiné avant les fils. Il s’effectue, pour
chaque sous-arbre, en 3 étapes ordonnées comme suit :
Ø Examen du père,
Ø Parcours en pré-ordre du sous-arbre gauche,
Ø Parcours en pré-ordre du sous-arbre droit.
appliqué à l’ensemble de la fig 4 cet ordre de parcours donne le résultat
suivant :
+ _ * ** B C /
_ A 2 D
5
soit + - ** A 2 B * C / D – 5
dans cette forme d’écriture de l’expression, l’opérateur précède le(s)
opérande(s) qui lui sont associé(s). Les parenthèses ne sont pas utilisées
puisque les opérateurs apparaissent dans l’ordre de leur exécution. Cette
écriture est appelée « notation polonaise préfixée ».
parcours post-ordre :aussi appelé « post-fixé » ou terminal,
il consiste à examiner les fils avant le père en commençant par le fils gauche.
Pour chaque sous-arbre les 3 étapes s’exécutent dans l’ordre suivant :
Ø
parcours du
sous-arbre gauche,
Ø
parcours du
sous-arbre droit,
Ø
examen du
père.
pour l’ensemble de la fig4 on obtient avec cet ordre de parcours le
résultat :
+ _ * ** B C /
_ A 2 D
5
soit A 2 ** B – C D 5 - / * +
Dans cette écriture ce sont les opérandes qui précèdent l’opérateur et les
opérateurs apparaissent dans ce cas aussi dans leur ordre d’exécution ce qui
rend inutile l’utilisation des parenthèses. Cette écriture est appelée
« notation polonaise post-fixée »
parcours symétrique :
appelé aussi « infixé » le père est examiné avant le fils droit
et après le fils gauche.
cet ordre de parcours applique à la fig4 donne le résultat :
+ _ * ** B C /
_ A 2 D 5
soit A ** 2 – B + C * D / -5
Parcours en largeur : rarement appliqué, il consiste à examiner les
nœuds par niveaux successifs, de gauche à droite. Son application sur fig4
donne
+ - * ** B C / A 2 D – 5
Algorithmes de parcours
Afin de définir ces algorithmes, sans tenir compte de la représentation de
l’arbre, nous utiliserons les fonctions suivantes :
EXISTEG(X) : fonction booléenne, retourne la valeur
« vrai » si le sous-arbre gauche du nœud X transmis en entrée existe.
EXISTED(X) : fonction booléenne, retourne la valeur
« vrai » si le sous-arbre droit du nœud X transmis en entrée existe.
GAUCHE(X) : cette fonction n’est définie que si
EXISTEG (X) est vrai ; elle retourne la valeur du fils gauche du nœud X.
DROITE(X) : cette fonction n’est définie que si
EXISTED (X) est vrai ; elle retourne la valeur du fils droit du nœud X.
On utilisera également, dans l’écriture des algorithmes la primitive EXAMINER(X)
qui a pour rôle d’examiner le nœud X et éventuellement de lui faire subir un
traitement quelconque.
Les 3 types de parcours définis plus haut sont basés sur la définition
récurrente des arbres, on pourra don définir des algorithmes récursifs pour ces
3 ordres de parcours.
Les procédures à définir effectuent le parcours d’un arbre binaire non
vide,et ont pour paramètre d’entrée la racine de cet arbre.
Procédure parcours préordre récursif : PPR
procedure PPR(racine)
debut
EXAMINER(racine)
si EXISTEG (racine) alors PPR( GAUCHE (racine)) fsi
si EXISTED (racine) alors PPR( DROITE (racine )) fsi
fin (*PPR*)
Procédure parcours préordre
itératif : PPI
L’algorithme itératif nécessite
l’utilisation d’une pile P pour sauvegarder tout nœud examiné, afin de
pouvoir parcourir son sous-arbre droit
après avoir effectué le parcours de son sous-arbre gauche.
Le parcours du sous-arbre gauche d’un nœud X est réalisé par la procédure
PG définie ci-dessous.
procedure PPI (racine) procedure PG(X)
debut
debut
X ß
PG(X)
EMPILER (X)
repeter tant que EXISTEG(X)
DEPILER(X) faire
si EXISTED(X) X ß GAUCHE(X)
alors
EXAMINER(X)
X ß DROITE(X) EMPILER(X)
PG(X)
finfaire
fsi
fin PG
jusqu’à VIDE(P)
fin PPI
Procédure parcours postordre
récursif :PTR
procedure PTR(racine)
debut
si EXISTEG (racine) alors PTR( GAUCHE (racine)) fsi
si EXISTED (racine) alors PTR( DROITE (racine )) fsi
EXAMINER(racine)
fin (*PTR*)
Procédure parcours symétrique
récursif :PSR
procedure PSR(racine)
debut
si EXISTEG (racine) alors PSR( GAUCHE (racine)) fsi
EXAMINER(racine)
si EXISTED (racine) alors PSR( DROITE (racine )) fsi
fin (*PSR*)
Implémentation des arbres binaires à l’aide des
pointeurs et variables dynamiques.
Tout comme les listes chaînées,
on peut représenter les arbres binaires à l’aide de la structure des pointeurs
et variables dynamiques tels que décrits dans le chapitre « pointeurs
& variables dynamiques »
Reprenons l’exemple de
fig1 « les arbres et leurs parcours »
+ _ * ** B C /
_ A 2 D
5 fig1
soit la structure de type pointeur définie comme suit :
type lien = @objet ;
objet = record info : char
filsg :
lien
filsd : lien
end ;
shématisée par
info filsg filsd
l’exemple de la fig1 peut être représenté comme suit :
+ * / C nil nil _ B nil
nil ** 2 nil nil D nil nil A nil nil 5 nil nil _ nil