ALGORITHMIQUE ET
STRUCTURES DE DONNEES
DYNAMIQUES
LES ARBRES
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 1
Les arbres
Un arbre est une structure de données sous forme de nœuds.
Chaque nœud « PÈRE » contient de zéro à plusieurs nœuds appelés « FILS ».
Un nœud qui n’a pas de père s’appelle « RACINE ».
Un nœud qui n’a pas de fils s’appelle « FEUILLE ».
R
X Cet arbre contient 11 nœuds dont:
Y Z
R: Racine
F: Feuille
F F F
F F
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 2
Arbre
Exemple d’une famille
•A titre d’exemple, nous pouvons représenter une
famille sous forme d’un arbre.
•La racine est, par exemple, le grand père.
•Le grand père, a de un à plusieurs fils.
•Chaque fils, a lui-même, de zéro à plusieurs fils.
•Et ainsi de suite.
•Celui qui n’a pas de fils, est une feuille.
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 3
Arbre
Voiture
• Nous pouvons représenter une voiture sous forme d’un arbre.
• La racine est la voiture
• La voiture est composée de trois fils: Carrosserie, Moteur et
Accessoires.
• La carrosserie est composée d’éléments qui, eux-mêmes peuvent
avoir des fils.
• Le Moteur est composé d’éléments, qui, eux-mêmes peuvent avoir
des fils.
• La partie Accessoires est composée d’éléments, qui, eux-mêmes
peuvent avoir des fils
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 4
Les arbres
Terminologie
Chaque Nœud de l’arbre est la racine d’un sous-arbre.
Sous-arbre B est composé de la racine B et des nœuds C, D et E.
Descendants d'un nœud X: ce sont tous les nœuds se trouvant sur les sous-arbres de racine (X).
Descendants de F sont les nœuds G, H et I.
Descendants de E : Aucun.
Ascendants d'un nœud X: ce sont tous les nœuds se trouvant sur le chemin de X jusqu’à la racine.
Ascendants de D : les nœuds B et A. A
Ascendants de A : Aucun.
B F J
C D G H K
E I
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 5
Les arbres
Terminologie
Père est un nœud qui a au moins un fils. (J est le père de K. F est le père de G et de H).
Fils est un nœud qui a un Père. (F est le fils de A. C est le fils de B).
Freres d'un nœud X: ce sont tous les nœuds ayant le même père que X (B,F,J sont frères de père A).
Niveau d’un noeud est égal au nombre d’ascendants pour arriver à la racine. La racine a le niveau
0. Ses fils le niveau 1 et ainsi de suite. Le nœud C a le niveau 2.
Profondeur d’un arbre est égale au plus grand niveau des nœuds (certainement une Feuille) de
l’arbre. (3 pour notre exemple).
A
Nœud interne est un nœud qui a au moins un fils.
C’est le contraire d’une feuille. Tous les nœuds de B F J
notre arbre sont internes, sauf E, D, G, I et K.
C D G H K
E I
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 6
Les arbres
Implémentation
Maintenant qu’on a compris ce que c’est un arbre et ses différentes
caractéristiques, nous allons voir comment le définir.
Nous allons voir, comme c’était le cas des files et des piles, comment
l’implémenter avec des structures dynamiques ensuite, on verra comment
avec des structures contiguës.
Nous prenons l’exemple d’un arbre ou chaque nœud a au maximum deux fils.
Nous devons, a partir de la racine, accéder a n’importe quel nœud de l’arbre.
Il suffit alors de pouvoir accéder de n’importe quel nœud a ses fils.
Donc, dans chaque nœud, on doit avoir la partie données et les deux
pointeurs qui nous permettent d’accéder a ses fils (s’ils existent, sinon NIL).
La partie donnée est une chaine de caractères S, et les pointeurs FG et FD
(pour Fils Gauche et Fils Droit)
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 7
Les arbres
Implémentation
Type T=^TT;
TT=Record
S:String;
◦ FG,FD:T
End;
Var R:T; //R est la racine de notre arbre.
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 8
Les arbres
Terminologie
On va voir comment créer l’arbre ci-dessous:
Var X:T;
Begin
New(R); R^.S:=‘A’;
New(R^.FG); R^.FG^.S:=‘B’;
New(R^.FD); R^.FD^.S:=‘J’;
X:= R^.FG;
New(X^.FG); X^.FG^.S:=‘C’; X^.FG^.FG:=NIL; X^.FG^.FD:=NIL; A
New(X^.FD); X^.FD^.S:=‘D’; X^.FD^.FG:=NIL; X^.FD^.FD:=NIL;
X:= R^.FD; B J
X^.FG:=NIL;
New(X^.FD); X^.FD^.S:=‘K’; X^.FD^.FG:=NIL; X^.FD^.FD:=NIL; C D K
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 9
Les arbres
Types de parcours: En Largeur
Parcours se fait niveau par niveau (Niveau 0: A, Niveau 1: B,J, Niveau 2: C,D,K)
Procedure ParcoursLargeur(R:T); File:
A
BJ A
Var X:T; JCD B
Begin CDK J
If R<>Nil Then DK C
K D
Begin
K
F:=Nil; Enfiler(R);
While Not FileVide(F) Do
Begin A
X:=Defiler(F); Writeln(X^.S);
If X^.FG<> Nil Then Enfiler(X^.FG); B J
If X^.FD<> Nil Then Enfiler(X^.FD);
End C D K
End
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 10
Les arbres
Parcours en profondeur
Trois types de parcours en profondeur:
Parcours en Préfixe: (R,FG,FD) A, B, C,E, D, F,G,H, I
Parcours en Postfixe: (FG,FD,R) E,C,D,B, G,I,H,F,A
Parcours en Infixe: (FG,R,FD) E,C,B,D, A, G, F,H,I
Procedure AFFPREFIXE(R:T);
Begin
IF R<>NIL THEN
BEGIN A
WRITELN(R^.S);
AFFPREFIXE(R^.FG); B F
AFFPREFIXE(R^.FD)
C D G H
END
End;
E I
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 11
Parcours en profondeur
Procedure AFFPOSTFIXE(R:T);
Begin
IF R<>NIL THEN
BEGIN
AFFPOSTFIXE(R^.FG);
AFFPOSTFIXE(R^.FD)
WRITELN(R^.S);
END
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 12
Types de Parcours
Procedure AFFINFIXE(R:T);
Begin
IF R<>NIL THEN
BEGIN
AFFINFIXE(R^.FG);
WRITELN(R^.S);
AFFINFIXE(R^.FD)
END
End
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 13
RECURSIVITE
On appelle récursive toute fonction ou procédure qui s’appelle elle-même
Exemple de la somme des N premier nombres entiers positifs:
S(N)=1+2+3+…..+N
S(N)=N+S(N-1)
S(N-1) =N-1+S(N-2)
Etc….
Exemple de la factorielle(N) :
F(N)=1*2*3*…..*N
F(N)=N*F(N-1)
F(N-1) =(N-1)*F(N-2)
Etc….
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 14
Programmation avec de la récursivité
Exemple:
Function Somme(N:Integer):Integer; Somme(5)=5+Somme(4)
Begin
Somme(4)=4+Somme(3)
If N=0 Then Somme:=0 Somme(3)=3+Somme(2)
Else Somme:=N+Somme(N-1)
Somme(2)=2+Somme(1)
End;
Somme(1)=1+Somme(0)
Somme(0)=0
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 15
Programmation avec de la récursivité
Exemple:
Function Fact(N:Integer):Integer; Fact(5)=5*Fact (4)
Begin
Fact(4)=4*Fact (3)
If N=1 Then Fact:=1
Else Fact:=N*Fact(N-1) Fact(3)=3*Fact (2)
End;
Fact(2)=2*Fact (1)
Fact(1)=1
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 16
Somme des éléments arbre binaire
Function Somme(R:T):Integer;
begin
If R=Nil Then Somme:=0
Else Somme:=R^.Valeur+Somme(R^.FG) +Somme(R^.FD)
End;
Function Taille (R:T):Integer;
begin
If R=Nil Then Taille :=0
Else Taille :=1+ Taille(R^.FG) + Taille(R^.FD)
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 17
Recheche dans un arbre binaire
Function TROUVE(R:T;V:integer):BOOLEAN;
begin
If R=Nil Then TROUVE:=False Else
If R^.Valeur=V Then TROUVE:= True
Else TROUVE := TROUVE (R^.FG,V) Or TROUVE(R^.FD,V)
End;
Function TROUVE(R:T;V:integer):BOOLEAN;
Var B:Boolean;
begin
If R=Nil Then TROUVE:=False Else
If R^.Valeur=V Then TROUVE:= True
Else Begin B:= TROUVE (R^.FG,V); If Not B then B:= TROUVE(R^.FD,V); TROUVE:=B End
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 18
Exercices: Proposez pour chaque exercice les deux solutions
Itérative et récursive
Fonction récursive qui détermine la taille d’une liste simplement chainée
Fonction récursive qui détermine la somme des valeurs d’une liste simplement chainée
d’entiers
Fonction récursive qui recherche une valeur dans une liste simplement chainée d’entiers
Fonction récursive qui calcule le nombre d’occurrences d’un caractère dans une String;
Fonction récursive de recherche d’un caractère dans un tableau de 1000 caractères
Fonction récursive qui inverse le contenu d’un tableau de 1000 caractères
Procedure qui inverse le contenu d’une liste
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 19
Type T=^TT;
Record
S:string;
Suivant:T Function Somme(L:T):Integer;
End; Begin
Function Taille(L:T):Integer; If L=Nil Then Somme:=0
Begin
Else
Somme:=L^.Valeur+Somme(L^.Suivant)
If L=Nil Then Taille:=0
End;
Else Taille:=1+Taille(L^.Suivant)
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 20
Liste simplement chainée
Une liste chainée (simplement chainée) est une structure de données pouvant
être vide ou contenir plusieurs éléments de même type.
Ces éléments sont chainées. Chaque élément contient l’adresse de l’élément
suivant.
L’accès au contenu de la liste se fait à partir de l’adresse du premier élément
(Debut)
Trouve(P(A),’C’)=Trouve(P(B),’C’)=Trouve(P(C),’C’)=True
A
B Trouve(Debut,’C’)=Trouve(Debut^.suivant,’C’)
Debut C = Trouve(Debut^.suivant ^.suivant,’C’)=True
D
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 21
Function Occ(S:string;C:Char):Integer; Function Occ(S:String;C:Char):Integer;
Begin Begin
Cpt:=0; If S=‘’ Then Occ:=0 Else
For I:=1 To Length(s) Do If S[1]=C Then Occ:=1+Occ(Copy(S,2,Length(s)-1),C)
If S[I]=C Then Cpt:=Cpt+1; Else Occ:=Occ(Copy(S,2,Length(s)-1),C)
Occ:=Cpt End;
End;
Occ(‘ABCD’, ‘C’)=
Occ(‘BCD, ‘C’)=
Occ(‘CD’, ‘C’)=1+ Occ(’D’,’C’)
Occ(’D’,’C’)= Occ(’’,’C’)=0
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 22
Récursivité pour un tableau
Type Tab = array[1..1000] of char;
Type Tarray{1..1000] Of Char;
Function Trouve(T:Tab;C:char;P:integer):boolean;
Function Trouver (S:T;C:Char):Boolean;
Var I:Integer;
Begin
Begin If P>1000 then Trouve := False
I:=1; else if T[P] = C then Trouve:= True
While (I<1000)And(S[I]<>C) Do else Trouve := Trouve(T,P+1,c)
I:=I+1; end;
Trouver:=S[I]=C ABCD
End; Trouve(Tab,’C’,1)=Trouve(Tab,’C’,2)=
Trouve(Tab,’C’,3)=True
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 23
Récursivité pour un tableau
Type Tab = array[1..1000] of char;
Type Tarray{1..1000] Of Char; Procedure Inverser(Var T:Tab;D,F:Integer);
Procedure Inverse (Var S:T); Begin
Var I:Integer; If D<F Then
Begin Begin
I:=1; Permuter(T,D,F);
For i:=1 To 1000 Div 2 Do
Inverser(T,D+1,F-1)
Permuter(S[I],S[1000-I+1])
End; End
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 24
Function Trouve(L:T;V:String):Booelan;
Begin
If L=Nil Then Trouve:=False
Else If L^.S=V Then Trouve:=True Else
Trouve:=Trouve(L^.Suivant,V)
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 25
Inverser une chaine de caracteres:
Function Inverse(Var S:T):String;
Var c:char;
Begin
If S<>'' Then
Begin
C:=S[Length(S)];
S:=Copy(S,1,length(s)-1);
Inverse(S);
S:=C+S
End
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 26
Inverser liste (récursivité)
Function Inverser(L:T):T;
Begin
If L=Nil Then Inverser:=Nil
Else If L^.Suivant=Nil Then Inverser:=L
Else InsererFin(Inverser(L^.Suivant),L)
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 27
Les arbres
Implémentation
Type T=^TT;
TT=Record
S:String;
◦ FG,FD:T
End;
Var R:T;
Procedure Afficher(R:T);
Begin
If R<>Nil Then
Begin
Writeln(R^.S);
Afficher(R^.FG);
Afficher(R^.FD);
End
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 28
Fonction qui donne le nombre
d’éléments d’un arbre binaire
Function Nombre(R:T):Integer;
Begin
If R=Nil Then Nombre:=0
Else Nombre:=1+Nombre(R^.FG)+Nombre(R^.FD)
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 29
Fonction qui recherche une valeur dans
un arbre binaire
Function Trouve(R:T;X:Char):Boolean;
Var B:Boolean;
Function Trouve(R:T;X:Char):Boolean;
Begin Var B:Boolean;
If R=Nil Then Trouve:=False Begin
If R=Nil Then Trouve:=False
Else If R^.S=X Then Trouve:=True Else Else If R^.S=X Then Trouve:=True Else
Begin
If Trouve(R^.FG) then Trouve:True B:=Trouve(R^.FG);
Else Trouve:=Trouve(R^.FD): If B then Trouve:True
Else Trouve:=Trouve(R^.FD):
End; End
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 30
Fonction qui donne le nombre d’occurrences
d’une valeur dans un arbre binaire
function occ(R:T;c:char):integer;
begin
if R = nil then occ:=0 else
if R^.S:=c then occ:=1+occ(R^.fg,c)+occ(R^.fd,c) else
occ:=occ(R^.fg,c)+occ(R^.fd,c)
end;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 31
Les arbres
Parcours d’un arbre
Procedure AfficherInf(R:T); Procedure AfficherPost(R:T);
Procedure AfficherPref(R:T);
Begin Begin
Begin
If R<>Nil Then If R<>Nil Then
Parcours Préfixe: If R<>Nil Then
Begin Begin
A,B,C,D,J,K Begin
Afficher(R^.FG);
Writeln(R^.S); Afficher(R^.FG);
Writeln(R^.S) Afficher(R^.FD);
Parcours Infixe: Afficher(R^.FG);
Afficher(R^.FD); Writeln(R^.S)
C,B,D,A,J,K Afficher(R^.FD);
End End
End
End; End;
End;
Parcours Postfixe: A
C,D,B,K,J,A
B J
C D K
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 32
Définitions relatives aux arbres
Un arbre est composé de noeuds.
Chaque nœud a un père. Celui qui n’a pas de père s’appelle Racine.
Chaque nœud un ou plusieurs fils. Celui qui n’a pas de fils s’appelle Feuille.
Un nœud est soit la racine, soit une feuille, soit un nœud interne.
Arité d’un arbre: Le nombre de fils maximum pour un nœud dans l’arbre. Si le nombre maximum
de fils pour un nœud dans un arbre est égal à N alors on parlera d’arbre N-aire.
Un arbre 2-aire est appelé arbre binaire.
Un arbre peut être vide.
Un nœud dans un arbre binaire comporte au maximum 2 fils (0, 1 ou 2 fils).
Les deux fils d’un arbre binaire sont appelés Fils Gauche et Fils Droit.
La hauteur d’un arbre est égale à la longueur du trajet le plus long de la racine à une feuille. La
hauteur d’un arbre qui ne contient que la racine est égale à 1. La hauteur d’un arbre vide est
égale à 0.
Dans notre exemple précédant, hauteur=6.
Profondeur ou hauteur ou niveau d’un nœud: Nombre de nœuds pour arriver à la racine. Niveau
de la racine est égale à 1.
Hauteur d’un arbre est égale à la hauteur maximale des feuilles.
La taille d’un arbre est égale au nombre de nœuds de l’arbre.
La taille d’un arbre vide est égale à 0
Un arbre binaire est complet si chacun de ses nœuds a exactement deux fils (sauf les feuilles
bien sûr)
Sa taille=power(2,h)-1
function Hauteur(T:TT) :Integer;
Begin
IF T=Nil Then Hauteur:=0
Else Hauteur:=1+max(hauteur(T^.FG),hauteur(T^.FD))
End;
function NbreNoeuds (T:TT):Integer;
Begin
IF T=Nil Then NbreNoeuds :=0
Else NbreNoeuds :=1+ NbreNoeuds (T^.FG), NbreNoeuds (T^.FD)
End;
function NbreFeuilles (T:TT):Integer;
Begin
IF T=Nil Then NbreFeuilles :=0 Else
If (T^.FG=Nil)and (T^.FD=Nil) Then NbreFeuilles:=1
Else NbreFeuilles :=NbreFeuilles(T^.FG) + NbreFeuilles(T^.FD)
End;
function Niveau(T:TT;S:String;Niveau:Integer):Integer;
Var N:Integer;
Begin
IF T=Nil Then
If T^.S=S Then N:=Niveau+1 Else
If Niveau(T^.FG,S,Niveau+1)<Niveau(T^.FD,S,Niveau+1) Then
N:=Niveau(T^.FG,S,Niveau+1) Else N:=Niveau(T^.FD,S,Niveau+1);
Niveau:=N
End;
Arbres binaires de recherche (ABR)
Un arbre binaire est un arbre binaire de recherche (ABR) si:
◦ Valeur du fils gauche < =Valeur de la racine (Père)
◦ Valeur de la racine (Père) < Valeur du fils Droit
Il facilite la recherche, Le nombre d’éléments parcourus est réduit, car en
parcourt l’arbre soit sur le sous arbre gauche, soit sur le sous arbre droit. Cela
rappelle la dichotomie.
L’insertion dans un ABR
Parcourir l’arbre jusqu’à un feuille. La comparaison de la valeur actuelle avec les deux fils permet de choisir le sous arbre.
Procedure inserer(R:T;S:String);
Begin
If R=Nil Then
Begin
New(R);R^.Valeur:=S;
R^.FG:=Nil; R^.FD:=Nil;
End
Else If S<R^.Valeur Then Inserer(R^.FG,S)
Else Inserer(R^.FD,S)
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 39
Recherche dans un ABR
Function Trouve(R:T;S:String):Boolean;
Begin
If R=Nil Then Trouve:=False
If S=R^.Valeur Then Trouve:=True
Else If S<R^.Valeur Then Trouve:= Trouve(R^.FG,S)
Else Trouve:= Trouve(R^.FD,S)
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 40
Ecrire une procédure qui détermine la valeur maximale d’un arbre ABR
Function Max(R:T):String;
Begin
Function Max(R:T):String;
If R^.FD=Nil Then Max:=R^.Valeur Var P:T;
Begin
Else Max:=Max(R^.FD) P:=R;
End; While P^.FD<>Nil Do P:=P^.FD;
Max:=P^.Valeur
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 41
Ecrire une procédure qui détermine la valeur minimale d’un arbre ABR
Function Min(R:T):String;
Begin
Function Max(R:T):String;
If R^.FG=Nil Then Min:=R^.Valeur Var P:T;
Begin
Else Min:=Min(R^.FG) P:=R;
End; While P^.FG<>Nil Do P:=P^.FG;
Min:=P^.Valeur
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 42
Inserer 5,9,15,18,22
Inserer 18,15,12,9,5
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 43
Solution exercice
Function Egaux(P1,P2:T):Boolean;//Comparer 2 arbres
Procedure afficher(R:T); //Afficher le contenu d’un arbre binaire Var B:Boolean;
Begin Begin
If R<>Nil Then If (P1=Nil)And(P2=Nil) Then Egaux:=True
Begin Else If (P1=Nil) Or (P2=Nil) Then Egaux:=False
Afficher(R^.FG); Else If P1^.S<> P2^.S Then Egaux:=False
AA:=AA+R^.S; Else Begin
Afficher(R^.FD); B:=Egaux([Link],[Link]);
End If Not B Then Egaux:=False
End; Else Egaux:= (Egaux(P1^.FD,P2^.FD))
End
Function maxim3(X,Y,Z:String):String; //Max entre trois strings End;
Var A:String; //Max entre deux strings
Begin Function maxim2(X,Y:String):String;
If X>Y then A:=X Else A:=Y; Var A:String;
If A>Z then maxim3:=A Else maxim3:=Z; Begin
If X>Y then maxim2:=X Else maxim2:=Y;
End; End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 44
Function Max(P:T):string; //Max d’un arbre binaire
Var a,b,c,m:string;
Begin
If P<>Nil Then
Begin
a:=P^.S;
//Niveau d’un élément If (P^.FG<>Nil)and(P^.FD<>Nil) Then
function Niveau(T:T;S:String;Niv:Integer):Integer; Begin
Var N:Integer; b:=Max(P^.FG);c:=Max(P^.FD);
Begin m:=maxim3(a,b,c);
IF T<>Nil Then End
If T^.S=S Then N:=Niv+1 Else Else If (P^.FG<>Nil) Then
If Niveau(T^.FG,S,Niv+1)<Niveau(T^.FD,S,Niv+1) Then Begin
N:=Niveau(T^.FG,S,Niv+1) Else N:=Niveau(T^.FD,S,Niv+1); b:=Max(P^.FG); M:=Maxim2(a,b)
Niveau:=N End
End; Else If (P^.FD<>Nil) Then
Begin
b:=Max(P^.FD); M:=Maxim2(a,b)
End
Else M:=a;Max:=M
End;
End;
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 45
ARBRE BINAIRE COMPLET
Un arbre binaire complet est un arbre h:Hauteur d’un ABR
F:Nombre de feuiles d’un ABR
binaire dans lequel chaque nœud (en Nombre de feuiles=2h-1
dehors des feuilles) a exactement deux h:Hauteur d’un ABR
T: Taille d’un ABR
fils, et toutes les feuilles ont la même T= 2 h-1
A
profondeur.
B J
C D L K
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 46
ARBRE BINAIRE COMPLET
Un arbre binaire complet de hauteur h contient
2 h-1 nœuds
Un arbre binaire complet de hauteur h contient
2h-1 Feuilles
NASREDDINE SI MOHAMMED ECOLE SUPERIEURE D'INFORMATIQUE DE SIDI BEL-ABBES ALGÉRIE 47
