La structure dynamique:
Arbre
Plan
• Définition d’un arbre
• Arbre binaire
• Arbre binaire de recherche ABR
• Les tableaux, les listes, les piles et les files : structures linéaires
• Les arbres :
• structures hiérarchiques
• Composées d’une racine et des nœuds
• Chaque Nœud possède un parent sauf la racine
• Un nœud peut avoir des fils
• Une feuille = un nœud qui n’a pas de fils
Arbre Binaire
Dans un arbre binaire:
Chaque nœud possède au maximum 2 fils : 0, 1 ou 2
Structure d’un arbre binaire:
TYPE
Nœud=Enregistrement
fg: ^Nœud
Info: Element
fd:^Nœud
FinEnregistrement
Arbre= ^Nœud
Procédure InitArbre(VAR A: Arbre)
Début
A NIL
Fin
Parcours d’un arbre binaire
• Parcours en longueur
• Préfixé: R-G-D
• Infixé: G-R-D
• Postfixé: G-D-R
• Parcours en largeur
Préfixé: R-G-D – solution récursive
Procédure Prefixe (A: Arbre)
Début
Si A <> Nil Alors
Ecrire(A → Info)
Prefixe(A → fg)
Prefixe(A→ fd)
Finsi
Fin
Préfixé: G-R-D
Procédure Infixe (A: Arbre)
Début
Si A <> Nil Alors
Infixe(A → fg)
Ecrire(A → Info)
Infixe(A→ fd)
Finsi
Fin
Préfixé: G-D-R
Procédure Postfixe (A: Arbre)
Début
Si A <> Nil Alors
Postfixe(A → fg)
Postfixe(A→ fd)
Ecrire(A → Info)
Finsi
Fin
Préfixé: R-G-D – solution itérative
N Sommet(P)
Procédure PrefixeIt (A: Arbre) Si N <> Nil Alors
Var Ecrire (N→ Info)
P: Pile Depiler (P)
N: Arbre FinSi
Début Si N→fd <> Nil Alors
CréerPileVide (P) Empiler (P→fd)
NA FinSi
Si N <> NIL Alors Si N→fg <> Nil Alors
Empiler (P, N) Empiler (P→fg)
Tant que Non PileVide(P) faire FinSi
FinTant que
FinSi
Fin
Parcours en largeur N Sommet(F)
Procédure Largueur (A: Arbre) Si N <> Nil Alors
Var Ecrire (N→ Info)
Defiler (F)
F: File FinSi
N: Arbre Si N→fg <> Nil Alors
Début Enfiler (P→fg)
FinSi
CréerFileVide (P) Si N→fd <> Nil Alors
NA Enfiler (P→fd)
Si N <> NIL Alors FinSi
FinTant que
Enfiler (F, N) FinSi
Tant que Non FileVide(F) faire Fin
Arbre Binaire de Recherche
ABR
Un ABR est un arbre où
• tous les nœuds du sous-arbre gauche sont < à la racine
• et tous les nœuds du sous-arbre droit sont > à la racine
Deux ABR différents peuvent contenir les mêmes valeurs
Recherche dans un ABR
Fonction ABRRecherche(a: Arbre , x: Entier) :Booleen
Début
Si a = Nil Alors
Retourner Faux
Sinon Si x = a→ info Alors
Retourner Vrai
Sinon Si x < a->info Alors
Retourner ABRRecherche(a→fg , x)
Sinon
Retourner ABRRecherche(a→fd , x)
FinSi
FinSi
FinSi
Fin
Recherche itérative dans un ABR
ARBRE-RECHERCHE_ITE(A , x)
VAR
P : Arbre
Début si x = P → info Alors
P←A retourner vrai
Tant que P ≠ NIL et P → info <> x Faire sinon
si x < P → info Alors retourner faux
P ← P → fg fin si
sinon FIN
P ← P → fd
fin si
fin tant que
Insertion dans un ABR
Fonction créer Noeud
Fonction creerNoeud(y: Entier): ^Noeud
VAR
nv: ^Noeud
Début
nv Allouer(Nœud)
nv →info y
nv →fg NIL
nv →fd NIL
Retourner nv
Fin
Procedure AjouterNoeud(VAR A: Arbre,y: Entier)
VAR
P: Arbre
Insert: Entier
Début
P ← A sinon // Insertion droite
Si P=NIL Alors P creerNoeud (y) Si (P→fd = NIL) Alors
Sinon P→fd creerNoeud(y)
Insert 0 Insert 1
Tant que Insert = 0 Faire Sinon
si (y < P → info) alors P P→ fd
//Insertion gauche FinSi
Si P→fg = NIL Alors finsi
P→fg creerNoeud(y) fin tant que
Insert 1 Fin
Sinon
P P→ fg
FinSi
Insertion Nœud: fonction récursive
Fonction InsererNoeudRec (A: Arbre, N: Arbre):Arbre
Si A=NIL Alors
retourner N
Sinon si A→info < N→info Alors
retourner (InsererNoeudRec(A→fd, N)
Sinon
retourner (InsererNoeudRec(A→fg, N)
FinSi
FinSi
Fin
Minimum dans un ABR
Fonction ABRMinimum (A: Arbre): Arbre
VAR
x: Arbre
Début
xA
Tantque x →fg <> Nil Faire
x x → fg
FinTantQue
Retourner (x)
Fin
Maximum dans un ABR
Fonction ABRMaximum(A: Arbre): Arbre
VAR
x: Arbre
Début
xA
TantQue x->fd <> Nil Faire
x <- x → fd
FinTantQue
Retourner (x)
Fin
Suppression dans un ABR
Ecrire une fonction Successeur, qui retourne le successeur d’un nœud.
Fonction successeur (a: arbre ):^Noeud
VAR
courant: arbre
Début
Si a→fd <> NIL Alors
courant a→fd
FinSi
Tant que (courant->fg <> NIL) faire
courant courant ->fg
FinTantQue
retourner courant
Fin
Fonction SuppABR (a : Arbre, x: Entier): Arbre
VAR Si (a->fd = NIL)
s, succ : ^Noeud s a->fg
Début
Libérer (a)
Si (a = NIL)
retourner NIL
retourner s
FinSi sinon
Si (x < a->info) Alors succ successeur (a ->fd)
a->fg = SuppABR(a->fg, x) a->info succ->info
sinon Si (x > a->info) a->fd SuppABR(a->fd, succ->info)
a->fd SuppABR(a->fd, x) Finsi
sinon // x = a-> info FinSi
Si (a->fg = NIL) FIN
s a->fd
Libérer (a)
retourner s
FinSi
Arbre SuppABR (arbre a, int x) if (a->fd == NULL)
{ noued *s, * succ; { s= a->fg;
if (a == NULL) free (a);
return NULL; return s;
if (x < a->info) }
a->fg = SuppABR(a->fg, x); else
else if (x > a->info) { succ = successeur (a ->fd);
a->fd = SuppABR(a->fd, x); a->info = succ->info;
else // x == a-> info
a->fd = SuppABR(a->fd, succ->info);
{if (a->fg == NULL) }
{ s= a->fd; }
free (a);
return s;
}
Complexité
• Les opérations dépensent un temps proportionnel à la hauteur d’un
arbre.
• Pour un ABR à n nœud: O(log2 n)
