Sommaire

Sommaire ................................................................................................................................................ 1
Chapitre 1 : Les piles et les files.............................................................................................................. 2

I – Les piles et l’évaluation des expressions arithmétiques : ........................................................... 2

II – Les files :................................................................................................................................... 8

Chapitre 2 : Les listes chaînées ............................................................................................................. 12

Chapitre 3 : Les Arbres ......................................................................................................................... 17

I – Préarbre (arborescence) ............................................................................................................ 17

II – Arbres et ensembles de mots : ................................................................................................ 20
III- Représentation en machine: .................................................................................................... 22
IV- Parcours d’arbres: ................................................................................................................... 24
V- Exemples d’arbres en informatique: ........................................................................................ 25
VI- Arbres Binaires: ...................................................................................................................... 28
VII – Mesures sur les arbres: ......................................................................................................... 30
VIII – Arbres binaires particuliers:................................................................................................ 31

Chapitre 4:Arbres binaires de recherche ............................................................................................... 33

I - Définition : ................................................................................................................................ 33
II – Implémentation : ..................................................................................................................... 34

Chapitre 5:Arbres binaires complets ..................................................................................................... 37

I – Définitions et propriétés ........................................................................................................... 37

II – Propriétés fondamentales : ...................................................................................................... 42
III – Permutations et arbres binaires :............................................................................................ 44

Chapitre 6 : Les Graphes ....................................................................................................................... 46

I- Représentations :............................................................................................................................ 46

I-1 Listes de successeurs (ou listes d’adjacences) : ....................................................................... 46

I-2 Matrice d’adjacences : ............................................................................................................. 47

II- Définitions : .................................................................................................................................. 49

III- Permutation associée à un graphe symétrique simple : ............................................................... 50

Chapitre 7 : Cheminement dans un Graphe ........................................................................................... 52

I- Parcours en largeur : ...................................................................................................................... 52

II- Parcours en profondeur : .............................................................................................................. 54
III- Fermeture transitive d’un graphe : .............................................................................................. 56
IV- Algorithme de forte connexité : .................................................................................................. 57

1
Chapitre 1 : Les piles et les files
Les piles et les files sont des ensembles dynamiques d’objets auxquels on accède en respectant des
stratégies bien définies.

I – Les piles et l’évaluation des expressions arithmétiques :

I.1 Définition formelle :

La stratégie d’accès à une pile est la stratégie F.I.L.O. (First In Last Out).
Soit E un ensemble d’éléments. On note PE l’ensemble des piles sur E.

I.1.a Actions :
créer : réserver de l’espace libre pour une pile.

ajouter : E x PE → PE (On ajoute l’élément en haut de la pile)

supprimer : PE → PE (On retire l’élément en haut de la pile)

remarque : cette opération n’est pas définie si la pile est vide.

valeur : PE → E (valeur de l’élément en haut de la pile)

remarque : cette opération n’est pas définie si la pile est vide.

vide : PE → {VRAI, FAUX} (VRAI et FAUX sont des constantes booléennes)

I.1.b Axiomes :
Soient p une pile et x un élément (objet).

vide (créer) = VRAI

vide(ajouter(x,p)) = FAUX

valeur(créer) = non défini

valeur(ajouter(x,p)) = x

supprimer(créer) = non défini

supprimer(ajouter(x,p)) = p

I.1.c Exemple :
valeur(supprimer(supprimer(ajouter(3,ajouter(2,supprimer(Ajouter(1,ajouter(8,créer))))))))=8

I.2 Implémentation formelle :

Implémenter veut dire remplacer une structure algébrique par un programme.

Nous utiliserons toujours une implémentation approchée car la pile aura toujours une capacité limitée
(limite d’ajout =N)
la pile sera notée p et l’indice de tête de pile sera noté ipile.

2
créer (p) :
déclarer ou allouer de l’espace pour un tableau p indicé de 1 à N et de même type que
les éléments de E.
ipile ← 0

vide(p) : si ipile=0 alors

retourner VRAI
sinon
retourner FAUX

valeur(p) :
si ipile=0 alors
afficher(’valeur non définie’)
sinon
retourner p[ipile]

ajouter(x,p) :
ipile ← ipile+1
si (ipile > N) alors
afficher(’implémentation insuffisante’)
sinon p[ipile] ← x

supprimer(p) :
si ipile=0 alors
afficher(’opération non définie’)
sinon
ipile ← ipile-1

I.3 Expressions polonaises postfixées :

L’écriture postfixée est une forme d'écriture d'expressions algébriques qui se distingue par la position
relative qu'y prennent les opérateurs et leurs opérandes. Un opérateur est écrit après ses opérandes en
notation postfixée.

8+2 → 8 2 +
8+2*3 → 8 2 3 * +
8 6 + 3 5 – 12 * + → 8+6+(3-5)*12

On se passe de l’utilisation des parenthèses dans l’écriture postfixée.

Définition formelle :

a - une variable ou une constante est une expression postfixée.

b - deux expressions postfixées suivies d’un opérateur binaire est une expression postfixée.
c - une expression postfixée suivie d’un opérateur unaire est une expression postfixée.

exemple :
8 5 + * ou 432– sont incorrectes

Passage de la notation usuelle à la notation postfixée :

Priorité des opérateurs :

priorité(^) > priorité(*, / ) > priorité( + , - ) > priorité(‘(‘)

3
 par convention, on pose :
priorité(^) = 3 ; priorité(*, / )=2 ; priorité( + , - ) =1 ; priorité(‘(‘) =0

Algorithme :

données : expression arithmétique usuelle représentée par une constante de type chaine de caractères.

résultats : affichage de l’expression postfixée effectuant le même calcul.

structure de données auxiliaire: une pile de caractères

on définit comme opérandes les noms de variables écrits avec une seule lettre.

on définit comme opérateurs les caractères suivants : ( , ) , * , + , - , / , ^

Transformation en notation postfixée : (écriture formelle)

x=premier caractère //les caractères sont issus de la chaine donnée en

//entrée de l’algorithme
créer(p)
ajouter(’(’,p)
répéter
si (x est une opérande) alors
afficher(x)
sinon
si (x est ’(’ ou ’^’) alors
ajouter(x,p)
sinon
si (x est ’)’) alors
tant que (valeur(p) != ’(’) faire
afficher(valeur(p))
supprimer(p)
supprimer(p)
sinon
tant que(priorité(valeur(p)>=priorité(x)) faire
afficher(valeur(p))
supprimer(p)
ajouter(x,p)
x = caractère suivant
jusqu’à la fin de la chaine d’entrée
tant que (valeur(p) != ’(’) faire
afficher(valeur(p))
supprimer(p)

Exercice : Exécuter cet algorithme avec "a*c+b+(c-d)*a" comme entrée.

4
I.4 Implémentation en langage c d’un module de gestion de piles

Déclaration des fonctions : fichier à entête pile.h

#define N 50
typedef struct { int tab_p[N];//le tableau sera indicé de 0 à N-1
int ip;
} pile;
void creerp(pile *);
int videp (pile );
int valeurp(pile );
int ajouterp(int,pile *);
int supprimerp(pile *);
void aff_pile(pile ); // affichage du contenu d’une pile
void remplir_pile(pile *);

Définition des fonctions : fichier pile.c

void creerp(pile *p){

(*p).ip=0;
}

int videp(pile p){

if ([Link]) return 0;
return 1;
}

int valeurp(pile p){

if (!videp(p)) return p.tab_p[[Link]];
printf("valeur non definie\n");
exit(-1);
}

int ajouterp(int x,pile *p){

(*p).ip++;
if ((*p).ip < N) {
(*p).tab_p[(*p).ip]=x;
return 1;
}
printf("implementation insuffisante\n");
exit(-1);
}

int supprimerp(pile *p){

if (videp(*p)) {
printf("suppression dans pile vide non definie\n");
exit(-1);
}
(*p).ip--;
return 1;
}
void aff_pile(pile p){//cette fonction viole les contraintes d’accès mais peut
//servir à vérifier le contenu de la pile sans la modifier
int i;
for (i=1;(i<= [Link]);i++)
printf("%c ",p.tab_p[i]);
printf("\n");
}

5
void remplir_pile(pile *p){
int i;
printf("remplir_pile_int\n");
for (;;) {
printf("donner un entier: (-1 pour arreter) :");
scanf("%d",&i);
if (i>=0) ajouterp(i,p);
else break;
}
}

I.5 Implémentation en langage c de l’algorithme de la transformation en notation

postfixée :

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#include "pile.h"

#define TBLOC 8

char *lireChaine() //lecture d’une chaine de caractère

{
int taille = TBLOC;
char *buffer = (char *) malloc(taille*sizeof(char));
char *p=buffer;
printf("taper une phrase ou un mot: ");
for (;;) { /* boucle de lecture */
if ((*p=getchar()) == '\n'){ /* lecture d'un \n */
if ((p==buffer) || (*(p-1) != '\\'))
break;
p--; /* annulation du \n (precede de \)*/
continue;
}
if (++p == buffer + taille) {
/* Agrandissement de la memoire de lecture*/
buffer= (char *) realloc(buffer,taille+TBLOC);
p=buffer+taille;
taille+=TBLOC;
}
}
*p='\0';
/*Allocation d'un zone de la taille de la chaine*/
p= (char *)malloc(p-buffer+1);
strcpy(p,buffer);
/*liberation de la memoire intermediaire*/
free(buffer);
return p;
}
int operande(char x){
if (((x>='a') &&(x<='z')) || ((x>='A') && (x<='Z'))) return 1;
if (isdigit(x)) return 1;
return 0;
}

6
int prio(char x) {
switch (x) {

case '(' : return 0;

case '+':
case '-': return 1;
case '*':
case '/': return 2;
case '^':{return 3; break;}
default: {printf("erreur d''operateur\n");getchar();exit(1);}
}
}

void postfixee(char *e){

pile p;
char x=e[0];
int i=0;
creerp(&p);
ajouterp('(',&p);
for (i=1;x != '\0';i++) {
if (operande(x)) printf("%c",x);
else if (x=='(') ajouterp(x,&p);
else if (x==')') {
while(valeurp(p)!='(') {
printf("%c",valeurp(p));
supprimerp(&p);
}
supprimerp(&p);
}
else {
while(prio(valeurp(p)) >= prio(x)) {
printf("%c",valeurp(p));
supprimerp(&p);
}
printf(" ");
ajouterp(x,&p);
}
x=e[i];
}
while (valeurp(p)!='(') {
printf("%c",valeurp(p));
supprimerp(&p);
}
printf("\n");
}
main(){
char *s=lireChaine();
postfixee(s);
}

7
II – Les files :

II.1 Définition formelle :

La stratégie d’accès à une file est la stratégie F.I.F.O. (First In First Out).
Soit E un ensemble d’éléments. On note FE l’ensemble des files sur E.

II.1.a Actions
créer : réserver de l’espace libre pour une file f.

ajouter : E x FE → FE (On ajoute l’élément à la fin (queue) de la file)

supprimer : FE → FE (On retire l’élément en début (tête) de la file)

remarque : cette opération n’est pas définie si la file est vide.

valeur : FE → E(valeur de l’élément en tête de file)

remarque : cette opération n’est pas définie si la file est vide.

vide : FE → {VRAI, FAUX}

II.1.b Axiomes :
Soient f une file et x un élément (objet).

vide (créer) = VRAI

vide(ajouter(x,f)) = FAUX

valeur(créer) = non défini

valeur(ajouter(x,f)) = si vide(f) alors x sinon valeur(f)

supprimer(créer) = non défini

supprimer(ajouter(x,f)) = si vide (f) alors créer sinon ajouter(x,supprimer(f))

II.1.c Exemple :
valeur(ajouter(3,supprimer(ajouter(4,supprimer(Ajouter(1,ajouter(2,créer)))))))=4

II.2 Implémentation formelle d’une file « linéaire » :

Nous utiliserons toujours une implémentation approchée car la file aura toujours une capacité limitée
(limite d’ajout =N)
la file sera notée f et nous avons besoin d’utiliser deux informations :
la place du dernier élément entré dans la file : indice de queue de file = iq
la place du plus ancien élément résidant dans la file : indice de tête de file = it

remarque : la différence entre iq et it nous donne le nombre d’éléments présents dans la file.

créer (f) : déclarer ou allouer de l’espace pour un tableau f indicé de 1 à N et de même type que
les éléments de E.

it ← 0
iq ← 0
8
vide(f) : si it=iq alors
retourner VRAI
sinon
retourner FAUX

valeur(f) : si it=iq alors

afficher(‘valeur non définie’)
sinon
retourner f[it+1]

ajouter(x,f) : iq ← iq+1
si (iq > N) alors
afficher(‘implémentation insuffisante’)
sinon f[iq] ← x

supprimer(f) : it ← it+1
si it > iq alors
afficher(‘opération non définie’)

II.3 Implémentation en langage c d’un module de gestion de files

Déclaration des fonctions : fichier à entête file.h

#define N 50
typedef struct { int tab_f[N];// //le tableau sera indicé de 0 à N-1
int it,iq;
} file;
void creerf(file *);
int videf(file );
int valeurf(file );
int ajouterf(int,file *);
int supprimerf(file *);
int aff_file(file );
void remplir_file(file *);

Définition des fonctions : fichier file.c

void creerf( file *f){

(*f).it=(*f).iq=0;
}

int videf(file f){

if ([Link]==[Link])
return 1;
return 0;
}

int valeurf(file f){

if (!videf(f))
return f.tab_f[[Link]+1];
printf("valeur non définie\n");
exit(-1);
}

9
int ajouterf(int x,file *f){
(*f).iq++;
if ((*f).iq < N) {
(*f).tab_f[(*f).iq]=x;
return 1;
}
printf("implementation insuffisante\n");
exit(-1);
}

int supprimerf(file *f){

if (videf(*f)) {
printf("suppression dans pile vide non definie\n");
exit(-1);
}
(*f).it++;
return 1;
}

int aff_file(file f){ //cette fonction viole les contraintes d’accès mais peut
//servir à vérifier le contenu de la file sans la modifier
int i;
if (videf(f)) {
printf("file vide\n");
return 0;
}
printf("tete de file = %d\n",valeurf(f));
for (i=[Link]+1;(i<= [Link]);i++)
printf("%d ",f.tab_f[i]);
printf("\n");
}

void remplir_file(file *f){

int i;
printf("remplir_file_int\n");
for (;;) {
printf("donner un entier: (-1 pour arreter) :");
scanf("%d",&i);
if (i>=0)
ajouterf(i,f);
else break;
}
}

10
II.4 Files circulaires

Etats possibles de la représentation contiguë d’une file circulaire :

it <iq

///////////////////vide///////////////////// éléments de f //////////////vide//////////////////////////

0 it iq N

it >iq

........f ///////////////////////////////vide/////////////////////////////////////////////// éléments de ....

0 iq it N

it = iq file vide

///////////////////////////////vide/////////////////////////////////////////////// /////////////////////////////////////////////////////////
0 it N
iq
it = iq file pleine

.............................................................................................f éléments de .........................................

0 it N
iq
Implémentation formelle d’une file circulaire :

créer (f) : déclarer ou allouer de l’espace pour un tableau de taille N et de même type que les
éléments de E.
it ← 0
iq ← 0

vide(f) : si it=iq alors retourner VRAI

sinon retourner FAUX

valeur(f) : si it=iq alors afficher(‘valeur non définie’)

sinon
si it = N alors retourner f[0]
sinon retourner f[it+1]

ajouter(x,f) : si iq = N alors iq=0

sinon iq ← iq+1
si (iq = it) alors
afficher(‘file pleine’)
sinon f[iq] ← x

supprimer(f) : si vide(f) alors afficher(‘opération non définie’)

sinon
it = it+1
si it = N+1 alors
it ← 0

11
Illustration :
it

iq

Exercice : Développer un module en langage c de gestion de files circulaires d’entiers.

Chapitre 2 : Les listes chaînées

Une liste chaînée est un ensemble de cellules contenant une information et une adresse. Cette structure
peut être implémentée par des tableaux ou des pointeurs. La stratégie d’accès à une liste chaînée est
basée sur l’adresse du premier élément de la liste.

Illustration

La liste vide est représentée par le pointeur NULL

Implémentation :

Une cellule est une structure auto-référencée qui peut être déclarée sous forme d’un enregistrement
contenant une information (val) et un pointeur (lien) référençant la cellule suivante ou la fin de la liste.

typedef struct cellule {

int val;
struct cellule *lien;
} cellule;

Comme toute structure de donnée complexe, nous avons besoin de construire des outils d’accès et de
modification de la structure en respectant des règles bien définies.

12
Allocation mémoire pour une cellule

cellule *creer_cellule(){
cellule *c;
c=(cellule *) malloc(1*sizeof(cellule));
c->lien=NULL;
return c;
}

Test de liste vide

int vide(cellule *p) {return (p==NULL);}

Affectation d’une information à une cellule

void remplir(cellule *p){

int x;
printf("donner un entier: "); scanf("%d",&x);
(*p).val=x;
}

Affichage du contenu d’une liste

Pour accéder aux éléments d’une liste chainée, on doit débuter la lecture à partir de la tête de liste et
ensuite effectuer un parcours jusqu’à la fin de la liste. Pour cela, on est obligé d’utiliser un pointeur
auxiliaire de parcours. En effet, si on modifie la valeur du pointeur de tête de liste, on perd
définitivement l’accès à la liste.

void afficher_liste(cellule *liste){

cellule *p=liste; // p est le pointeur de parcours
while(p!=NULL){ printf(" %d",(*p).val);p=p->lien;}
printf("\n");
}

Affichage de la valeur des pointeurs (adresses) de la liste

Cette fonction montre comment se fait le chainage des adresses mémoire.

void afficher_liste_p(cellule *liste){

cellule *p=liste;
while(p!=NULL){
printf(" %p %d %p\n",p,(*p).val,p->lien);p=p->lien;}
printf("\n");
}

Calcul de la longueur d’une liste chaînée (nombre de cellules existantes dans la liste)

int longueur(cellule *p){

cellule *q=p;
int c=0;
while (q!=NULL) { c++; q=q->lien;}
return c;
}

13
Insertion d’une cellule en début de liste

Lors de la construction d’une liste chainée, on doit adopter une stratégie d’ajout de cellules dans la
liste. En effet, l’ordre final des éléments de liste dépend de l’endroit ou on insère les nouvelles
cellules.

cellule *inserer_debut(cellule *liste,cellule *c) {

c->lien=liste;
liste=c;
return liste;
}

Insertion d’une cellule en fin de liste

cellule *inserer_fin(cellule *liste,cellule *c) {

if (vide(liste)) liste=c;
else {
cellule *q=liste;
while(q->lien != NULL) q=q->lien;
q->lien =c;
}
return liste;
}

Rechercher une information dans la liste

Cette fonction retourne l’adresse de la cellule contenant l’information recherchée ou le pointeur NULL
si non trouvé. On suppose que la liste n’est pas triée.

cellule *recherche_elt(int x,cellule *liste){

cellule *p=liste;
while ((p!=NULL)&&((*p).val !=x)) p=p->lien;
if (p == NULL) return NULL;
return p;
}

Suppression d’un élément de la liste

Pour supprimer (déchainer) une cellule, il nous faut d’abord identifier le pointeur de l’élément
précédent qui pointe vers la cellule à supprimer. Pour cela, on effectue d’abord un parcours de
recherche qui nous donne ce pointeur nommé pp dans la fonction : recherche_elt_s().

pp p

liste

cellule *recherche_elt_s(int x,cellule *liste){

cellule *p=liste,*pp=NULL;
while ((p!=NULL)&&((*p).val !=x)) {pp=p;p=p->lien;}
return pp;
}

14
Lors de la suppression nous devons faire attention à la position de la cellule à supprimer. Cette
opération ne se déroulera pas de la même façon selon que la cellule soit en début ou au milieu de la
liste.

cellule *supprimer(cellule *liste,int x){

cellule *pp,*q;
if (liste==NULL) return NULL;
if ((*liste).val==x)
{q=liste;liste=liste->lien;free(q);return liste;}
if ((pp=recherche_elt_s(x,liste))->lien==NULL)
printf("non trouvé\n");
else {
q=pp->lien;
pp->lien=q->lien;
free(q);
return liste;
}
}

Insertion d’un élément dans une liste triée :

L’insertion en milieu de liste n’a de sens que si celle ci est triée. Comme la suppression, cette
opération nécessite la recherche de l’endroit où on doit effectuer l’insertion. Nous choisissons
arbitrairement l’ordre croissant pour la liste triée.

cellule *recherche_precedent(int x,cellule *liste){

// cas où l’insertion doit se dérouler en début de liste

if ((liste==NULL) || ((*liste).val >x)) return NULL;

// cas où l’insertion doit se dérouler au milieu ou en fin de liste

cellule *pp=liste;
cellule *p=liste->lien;
while ((p!=NULL)&&((*p).val <=x)) {pp=p;p=p->lien;}
return pp;
}

cellule *inserer(cellule *liste,cellule *c){

cellule *p,*pp;
if (c==NULL) return liste ;
pp=recherche_precedent((*c).val,liste);
p=liste;
if ((p==NULL)||(pp==NULL)) liste=inserer_debut(liste,c);
else {
c->lien=pp->lien;
pp->lien=c;
}
return liste;
}

15
Voici un exemple de programme principal permettant de tester ces fonctions.

#include "listes_cours.h"
main(){
int i,x; cellule *liste = (cellule *) NULL; cellule *p;
for (;;){
printf("1:inserer_debut 2:inserer_fin 3: afficher\n");
printf("4:longueur 5: rechercher 6: inserer \n") ;
printf("7:supprimer;\n");
scanf("%d",&i);
switch (i){
case 1: p=creer_cellule();remplir(p);
liste=inserer_debut(liste,p);break;
case 2: p=creer_cellule();
remplir(p);
liste=inserer_fin(liste,p);break;
case 3: afficher_liste(liste);
afficher_liste_p(liste);break;
case 4: printf("longueur= %d\n",longueur(liste));break;
case 5: printf("donner l'info a rechercher:");
scanf("%d",&x);
printf("%d %p\n",x,recherche_elt(x,liste));break;
case 6: p=creer_cellule();
remplir(p);
liste=inserer(liste,p);break;
case 7: printf("donner l'info à supprimer:");
scanf("%d",&x);
liste=supprimer(liste,x);break;
default: exit(0);
}
}
}

16
Chapitre 3 : Les Arbres

I – Préarbre (arborescence)

Un préarbre est un ensemble dynamique fini S qu’on définit sous la forme d’une application de S dans
l’ensemble des parties de S :

soit un élément r  S la racine du préarbre

 s  S, il existe une suite unique s1, s2, ... , sp / s1 = r et sp =s ; et si+1  (si ) pour i=1,2, ... , p-1

Exemple :
S={ s0, s1, s2, s3, s4, s5, s6, s7, s8} ; r = s0

| s0 s1 s2 s3 s4 s5 s6 s7 s8
______|______________________________________________________
| s1 s4 s3 s6  s8   
 | s2 s5
| s7

Pour montrer que (S,r,) est un préarbre, il faut montrer qu’il existe une suite unique reliant r et tous
les éléments de S.
On dénombre les suites qui vérifient si+1  (si ) pour i=1,2, ... , p-1

- s0 s1 s4
- s0 s1 s5 s8
- s0 s1 s7
- s0 s2 s3 s6

I.1 Représentation :

a)On relie s à (s) par une ligne droite :

s0

s1 s2

s4 s5 s7 s3

s8 s6

17
b) Ensembles imbriqués:

s5 s8

s6

s4 s7

s3
s1

s2

s0

c) Parenthèses imbriquées :

(s0(s1(s4) (s5(s8))(s7))(s2(s3(s6))))
d) Identation :

s0
s1 s2
s4 s5 s7 s3
s8 s6

I.2 Définitions :

Soit S un ensemble d’éléments et  une application de S dans l’ensemble des parties de S :

On appelle :
Chemin : une suite s1, s2, ... , sp telle que si+1  (si ).
Nœud : s  S tel que (s) .
Feuille : s  S tel que (s)= .
Sommet : un nœud ou une feuille.
Branche : le chemin s1=r, s2, ... , sp et (sp)=.

18
I.3 Propriétés :

a) Si st alors (s)(t)= .

Démonstration : si u  (s ) (t) alors il existe deux chemins :

r, s1, ... , s,u et r, s’1, ... , t,u

ce qui contredit l’unicité de la suite partant de r à u.

b)  s  S ; r  (s)

c) si S est un ensemble fini alors il existe au moins une feuille :

Démonstration :
Soit n le nombre de sommets de S et il existe un chemin de longueur n+1 :

s1,s2 ... , si , si+1, ... , sn, sn+1

donc, il existe si=sj / (si-1)(sj-1)  .

I.4 Restriction :

soit (S,r,) un préarbre et T un sous ensemble de S qui contient r :

  (t) = (t)

Exemple 1 Exemple 2
T1={ s0, s2, s5, s8} T2={ s0, s1, s4, s5}
(s0) = { s2} (s0) = { s1}
(s5) = { s8} (s1) = { s4, s5}
(s2) =  (s4) = 
(s8) =  (s5) = 

ceci n’est pas un préarbre c’est un préarbre

il n’existe pas de chemin reliant s0 à s5, s8.

I.5 Propriétés :

d) Si f est une feuille, la restriction de  à S\f est un préabre.

e) Soit S,  un préarbre :

par récurrence :

si card(S)=1 alors S={r}

(r) =  ==> card((r)) = 0 = 1-1
supposons la propriété vraie pour un certain k.
considérons un préarbre S avec k+1 sommets : card(S) = k+1,
il existe une feuille f / S’=S\f
19
’ est une restriction de  à S’ et est un préarbre.

Il existe un unique t S’ / f  (t).

II – Arbres et ensembles de mots :


soit un élément s/ s { s1,s2 ... , si}, on dit que sk  (s) est fils de s.

II.1 Définition :

Soit un arbre définit par (S, r ,).

 fait correspondre à chaque sommet s une suite ordonnée de sommets de S.
un arbre est un préarbre  muni d’un ordre sur les éléments de (s).

s0

s1 s2

s4 s5 s7 s3

s8 s6

(s0)={s1, s2} ; (s1)={s4, s5, s7} ; (s2)={s3} ;(s3)={s6} ; (s5)={s8} .

(s0)= s1 s2
(s0)= s2 s1

(s1)= s4 s5 s7
s4 s7 s5
s5 s4 s7
s5 s7 s4
s7 s4 s5
s7 s5 s4
Ce qui nous donne douze arbres possibles.

20
II.2 Ensembles de mots associés à un arbre :

Soit un arbre définit par (S, r ,)

On pose : (sur l’exemple : k=3)

pour chaque sommet de S, on associe un mot :

soit s, s  r, il existe une chemin r=s1, s2, ... , s=sp / w(s)=w(sp-1).ai si s intervient au ième rang dans la
suite (sp-1).

(s0)= s2 s1
(s1)= s5 s7 s4

s0

s2 s1

s3 s5 s7 s4

s6 s8

w(s0)={}
w(s1)= w(s0).ai=a2
w(s2)= w(s0).ai=a1
w(s3)= w(s2).ai= a1 a1
w(s4)= w(s1).ai= a2 a3
w(s5)= w(s1).ai= a2 a1
w(s6)= w(s3).ai=a1 a1 a1
w(s7)= w(s1).ai= a2 a2
w(s8)= w(s7).ai= a2 a2 a1

Propriété :

Si W est l’ensemble des mots associés à un arbre alors :

(1) f.g  W  f W
(2) [Link]  W  [Link] W et j  i

Exemple : {a1, a2, a1 a1, a2 a3, a2 a1,a1 a1 a1, a2 a2, a2 a2 a1}

Réciproque :

Si vérifie (1) et (2) alors il existe un arbre dont l’ensemble des mots associés est
W.

exemple : {a1 a4 a2, a1a3 a1, a1 a2, a1 a3, a1 a4 a1 ,a2 ,a1, a1 a1, a1 a4 }
21
 

a1 a2

a1a1 a1a2 a1a3 a1a4

a1a3a1 a1a4a1 a1a4a2

Remarque : Si on ne considère que l’ensemble des mots associés aux feuilles d’un arbre qui vérifie (1)
et (2) alors cet ensemble est un code.



a2 a1

a2a3 a2a2 a2a1 a1a1

a2a2a1 a1a1a1

{a2a3, a2a2a1, a2 a1, a1a1a1} est un code.

III- Représentation en machine:

III-1 Implémentation statique

On définit trois tableaux de la façon suivante:

le premier tableau contiendra les étiquettes (informations ou valeurs) associées aux sommets de
l’arbre.

le deuxième tableau contiendra les indices des cases où se trouve le premier fils (fils ainé) pour chaque
sommet et -1 si pas de fils.

le troisième tableau contiendra les indices des cases où se trouve le fils suivant du père (frère) pour
chaque sommet et -1 si pas de frère.

Exemple:

1 2 3 4 5 6 7 8 9 10 11 12 13
Val S0 S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12
Fils 2 3 -1 6 8 -1 10 -1 12 -1 -1 -1 -1
frere -1 4 5 -1 -1 7 -1 9 -1 11 -1 13 -1
pere -1 1 2 1 2 4 4 5 5 7 7 9 9

Remarque: le tableau père n’est pas nécessaire à l’implémentation et peut être calculé à partir des autres tableaux
comme nous le verrons plus loin.

22
 s

s1 s3

s2 s4 s5 s6

s7 s8 s9 s10

s11 s12

Exemple d’implémentation en langage c:

#include <stdio.h>
#include <stdlib.h>
#define N 20 /* N=Nombre maximal de sommets possibles */

typedef int sommet[N];

typedef char *valeur[N];

main(){
int racine;

valeur val={"","s0","s1","s2","s3","s4","s5","s6","s7","s8","s9",
"s10","s11","s12"};
sommet fils={-1,2,3,-1,6,8,-1,10,-1,12,-1,-1,-1,-1};

sommet frere={-1,-1,4,5,-1,-1,7,-1,9,-1,11,-1,13,-1};

sommet pere={-1,-1,1,2,1,2,4,4,5,5,7,7,9,9};
//Appels aux fonctions utilisant cet arbre
}

III-2 Exemples de fonctions utilisant cet arbre :

a) calcul du nombre de feuilles d'un arbre

int nbr_feuilles(sommet n, valeur val){

int i,nbf=0;
for (i=1;i<N;i++)
if (n[i]==-1) {nbf++; printf("%s\n",val[i]);}
return nbf;
}
b) trouver les éléments de (s)

void phi(char *s,sommet fils,sommet frere, valeur val){

int sommet,i,t;
for (i=1;i<N;i++)
if (!strcmp(s,val[i])) {sommet=i; break;}
t=fils[sommet];
while (t!=-1) {
printf(" %s",val[t]);
t=frere[t];
}
}

23
c)trouver l'indice du père de t :

On suppose qu’on ne dispose pas du tableau père, que t n’est pas forcement le premier fils et que
l’arbre n’est pas binaire (i.e. cas général)

char *ind_pere(char *s,sommet fils,sommet frere,valeur val){

int i,t;
for (i=1;i<N;i++)
if (!strcmp(s,val[i])) {t=i; break;}
int pere=-1;
if (t == 1) { printf("pas de pere\n");getchar();exit(0);}
while (pere == -1){
for (i=1;i<N;i++)
if (t==fils[i]) pere=i;
for (i=1;i<N;i++)
if (t==frere[i]) t=i;
}
return val[pere];
}

IV- Parcours d’arbres:

Un parcours est une suite ordonnée de l’ensemble des sommets qui contient chaque sommet une fois et
une seule. Il existe trois façons de parcourir un arbre :

Parcours en préordre :
visiter la racine
parcourir les sous arbres de gauche à droite

Parcours en postordre :
parcourir les sous arbres de gauche à droite
visiter la racine

Parcours en ordre symétrique « inorder » :

parcourir le sous arbre gauche
visiter la racine
parcourir le sous arbre droit

Exemple :

s

s1 s3

s2 s4 s5 s6

s7 s8 s9 s10

s11 s12
24
préordre(s0) = s0, préordre(s1), préordre(s3)
= s0, s1, préordre(s2), préordre(s4), s3, préordre(s5), préordre(s6)
= s0, s1, s2, s4, préordre(s7), préordre(s8), s3, s5, s6, préordre(s9), préordre(s10)
= s0, s1, s2, s4, s7, s8, préordre(s11), préordre(s12), s3, s5, s6, s9, s10
= s0, s1, s2, s4, s7, s8, s11, s12, s3, s5, s6, s9, s10

parcours récursif en preordre

void preordre(int s,sommet fils,sommet frere,valeur val){

int t;
printf(" %s",val[s]);
t=fils[s];
while (t!=-1) {
preordre(t, fils,frere,val);
t=frere[t];
}
}

parcours itératif en preordre

void preordre_it(int s,sommet fils,sommet frere,valeur val){
pile p;
int x;
creer(&p);
ajouter(-1,&p);
while (!vide(p)) {
printf(" %s",val[s]);
if (fils[s]!=-1) {
if (frere[s]!=-1) ajouter(frere[s],&p);
s=fils[s];
}
else
if (frere[s]!=-1) s=frere[s];
else{
x=valeurp(p);
supprimer(&p);
if (x==-1) break;
else s=x;
}
}
}

V- Exemples d’arbres en informatique:

Arbre associé à une expression arithmétique:

l’arbre associé à la forme: expression1 opérateur expression2 peut être représenté par:

opérateur

expression1 expression2

25
exemple: (a+b)*(a-b)-(a**2+b)/(c+a)

* /

+ - + +

a b a b ** b c a

a 2

Le parcours en postordre de cet arbre donne l’expression postfixée.

Arbre associé à un système de fichier:

bin dev mnt home root etc boot sys var

nom_user1 nom_user2

Bureau Documents Téléchargements Bureau Documents Téléchargements

Arbre associé à un programme:

int nbr_feuilles(sommet n, valeur val){

int i,nbf=0;
for (i=1;i<N;i++)
if (n[i]==-1) {nbf++; printf("%s\n",val[i]);}
return nbf;
}

26
 fonction

type de retour nom liste_paramètres corps

int nbr_feuilles paramètre1 paramètre2

type nom type nom

sommet n valeur val

corps

déclarations instructions

type for return nbf

int initialisation condition incrémentation corps

i = = < =

nbf 0 i 1 i N i +

i 1

if

condition corps

== = printf

n[i] -1 nbf + format liste d‘arguments

nbf 1

27
VI- Arbres Binaires:

VI-1 Définition et représentation :

Chaque sommet a :
ou bien deux fils
ou bien pas de fils
ou bien un fils gauche
ou bien un fils droit

On définit deux applications :

fils gauche :
fils droit :

Pour tout sommet, il existe une façon et une seule de l’obtenir par fg et fd à partir de la racine.

Exemple :

s

g s1 s2 d

dg s3

s4 dgd

dgdg s5 s6 dgdd

s7 dgdgd

Cet arbre peut être représenté (codé) par l’ensemble de mots suivant :
M={, g, d, dg, dgd, dgdg, dgdd, dgdgd}

Remarque sur les ensembles de mots associés aux arbres binaires :

VI-2 Implémentation statique :

On peut représenter un arbre binaire par deux tableaux fg et fd contenant les indices des fils gauche et
droit de chaque sommet respectivement ainsi qu’un tableau valeur contenant l’information associées à
chaque sommet.

28
 1

2 3

4 5 6

7 12

8 9 13 14

10 11 15

s 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
fg 2 4 5 0 0 0 8 0 10 0 0 13 0 15 0
fd 3 0 6 7 12 0 9 0 11 0 0 14 0 0 0
val

#define N 100
typedef struct sommet{int val; int fg; int fd;}sommet;
typedef sommet tab[N];
typedef struct arbre {int racine; tab table;} arbre;

VI-3 Implémentation dynamique:

On utilise une structure auto-référencée avec deux pointeurs pour désigner les « suivants » fils gauche
et/ou droit.

arbre

b c

d
k
l
e
m

f g

29
typedef struct sommet{ int val ;
struct sommet *fg;
struct sommet *fd;
}sommet;
sommet *arbre ;

VII – Mesures sur les arbres:

VII – 1 Taille d’un arbre :

C’est le nombre de ses sommets et on peut le définir récursivement.

taille(arbre_vide)=0 ;
taille(<r,B1,B2>)=1+taille(B1)+taille(B2)
avec :
<r,B1,B2>
r

B1 B2

VII – 2 Hauteur d’un sommet :

Soit x un sommet d’un arbre B.

h(x)=0 si x est la racine de B.
h(x)=h(y)+1 si y est le père de x.
Ainsi, la hauteur d’un sommet est comptée par le nombre de liens (arcs) sur l’unique chemin de la
racine à ce sommet.

VII – 3 Hauteur d’un arbre :

h(B)=Max(h(x)) et x est un sommet de B.

VII – 4 Longueur de cheminement d’un arbre :

LC(B)= h(x) et x est un sommet de l’arbre B.

- Longueur de cheminement externe :

LCE(B)= h(f) et f est une feuille de l’arbre B.

- Longueur de cheminement interne :

LCI(B)= h(x) et x est un sommet interne de l’arbre B.

On a la relation : LC(B)=LCE(B)+LCI(B).

30
VII – 5 Profondeur moyenne externe :

Si B possède nf feuilles alors : PE(B)=LCE(B)/nf

Exemple :
n1 h(B)=4

n2 n4 LC(B)=22

n3 n5 n7 LCI(B)=9

n6 n9 LCE(B)=13

n8 n10 PE(B)=13/4=3.25

VIII – Arbres binaires particuliers:

Ce sont des formes extrêmes d’arbres binaires.

VIII – 1 Arbre binaire dégénéré ou filiforme :

taille(B)=h(B)+1
n1

n2

n3

n6

n8

VIII – 2 Arbre binaire complet :

Il contient un nœud au niveau 0, 2 nœuds au niveau 1, 4 nœuds au niveau 2 ..... 2h nœuds au niveau h.
(chaque niveau est complètement rempli)

taille(B)=1+2+4+ ... + 2h=2h+1-1

31
 s

s1 s3

s2 s4 s5 s6

s11 s12 s7 s8 s13 s14 s9 s10

VIII – 3 Arbre binaire parfait :

C’est un arbre binaire dont tous les niveaux sont complètement remplis sauf éventuellement le dernier,
et dans ce cas les feuilles sont groupées le plus à gauche possible.

Parfait

Non Parfait

Non Parfait

32
VIII – 4 Arbre binaire localement complet :

C’est un arbre binaire non vide dans lequel tous les nœuds qui ne sont pas des feuilles ont deux fils.

VIII – 5 Peigne gauche (respectivement droit) :

C’est un arbre binaire localement complet dans lequel tous fils droit (respectivement gauche) est une
feuille.

Peigne gauche

Chapitre 4:Arbres binaires de recherche

I - Définition :

Soient  un arbre binaire et S un ensemble totalement ordonné.

Soient x et t deux sommets de l’arbre.

On définit récursivement l’ensemble descendant(x) de la façon suivante :

descendant(x)= {x} U descendant(fg(x)) U descendant(fd(x))

Un ABR est un arbre binaire dans lequel tout sommet t satisfait les conditions suivantes :

- si t est un descendant du fils gauche de x alors (t) < (x)

- si t est un descendant du fils droit de x alors (t) > (x)

33
II – Implémentation :

#define N 20
typedef struct sommet { int val;
struct sommet *fg;
struct sommet *fd;} sommet;

1)Allocation de l’espace pour un sommet :

sommet *creer(int a){

sommet *s= (sommet *) malloc(sizeof(sommet));
(*s).val=a;
s->fg=s->fd=NULL;
return s;
}

2)Insertion d’un nouveau sommet dans l’arbre

Un ABR croît par les feuilles : On doit effectuer un parcours en comparant les valeurs des sommets de
l’arbre à celle du sommet à insérer jusqu’à atteindre une feuille.

sommet *ajouter(sommet *r, sommet *z){

int a=(*z).val;
sommet *x=r;
sommet *y=NULL;
while ((x!=NULL) && ((*x).val != a)) {
y=x;
if ((*x).val > a) x=x->fg;
else x=x->fd;
}
if (x==NULL) {
if (a > (*y).val) y->fd=z;
else y->fg=z;
}
else
printf("insertion impossible \n");
return r;
}

3) Recherche de l’existence d’un élément dans l’arbre

int trouve(sommet *r, int a){

sommet *x=r;
while ((x!=NULL)&& ((*x).val != a))
if ( (*x).val > a) x=x->fg;
else x=x->fd;
if (x==NULL) return 0;
return 1;
}
4) vérifier si un sommet donné est une feuille

int feuille(sommet *u){

if (u!=NULL)
if ((u->fg==NULL) && (u->fd==NULL)) return 1;
return 0;
}

34
5) parcours récursif en préordre

void preordre(sommet *r){

sommet *x;
x=r;
if (x==NULL) return;
printf(" %2d",(*x).val);
preordre(x->fg);
preordre(x->fd);
}

6)parcours récursif en ordre symétrique

void inordre(sommet *r){

sommet *x;
x=r;
if (x==NULL) return;
inordre(x->fg);
printf(" %d",(*x).val);
inordre(x->fd);
}
7) parcours recursif en postordre

void postordre(sommet *r){

sommet *x;
x=r;
if (x==NULL) return;
postordre(x->fg);
postordre(x->fd);
printf(" %d",(*x).val);
}

8) parcours itératif en préordre

void preordre_it(sommet *r){

pile p;
sommet *z,*x=r;
creerp(&p);
z=creer(0);
ajouterp(z,&p);
while (!videp(p)) {
printf(" %2d",(*x).val);
if (x->fg!=NULL) {
if (x->fd != NULL) ajouterp(x->fd,&p);
x=x->fg;
}
else
if (x->fd != NULL) x=x->fd;
else{
x=valeurp(p); supprimerp(&p);
if ((*x).val==0) break;
}
}
printf("\n");
}

35
9)Retirer un sommet de l’arbre
Pour supprimer un sommet, nous devons d’abord chercher son pointeur ainsi que celui de son père.
Nous devons aussi traiter différemment les cas où ce sommet possède un fils gauche, un fils droit, ou
deux fils.
sommet *supprimer(sommet *r,int a){
sommet *u,*v,*x,*y;
rechercher(r,&u,&v,a);
if (u==NULL) {printf("non trouve\n"); return r;}
if ((u->fg==NULL) || (u->fd==NULL)) oter1(&r,&u,&v);
else {
oter2(u,&x,&y);
(*u).val=(*x).val;
oter1(&r,&x,&y);
}
return r;
}
Recherche du pointeur du sommet à supprimer ainsi que celui de son père
int rechercher(sommet *r,sommet **u,sommet **v,int a){
*u=r; *v=NULL;
while ((*u!=NULL) && ((**u).val!=a))
if ((**u).val > a) {*v=*u ; *u=(*u)->fg;}
else {*v=*u ; *u=(*u)->fd;}
}

Recherche du descendant le plus à droite dans le sous arbre gauche

Dans le cas où le sommet à supprimer possède deux fils, on choisi de le remplacer par la valeur de son
prédécesseur qui est le descendant le plus à droite dans le sous arbre gauche (on aurait pu choisir son
successeur qui est le descendant le plus à gauche dans le sous arbre droit). Celui ci possède forcément
un ou zéro fils. Une fois le remplacement effectué, on supprime le prédécesseur.

void oter2(sommet *u,sommet **x,sommet **y){// x est le prédécesseur

*x=u->fg;
*y=u;
if ((*x)!= NULL)
while ( (*x)->fd !=NULL) { *y=*x; *x=(*x)->fd;}
}
Suppression effective du sommet u (v est son père)
void oter1(sommet **r,sommet **u,sommet **v){
if (feuille(*u)){
if (*v==NULL) *r=NULL;
else if (*u == (*v)->fg) (*v)->fg=NULL;
else (*v)->fd=NULL;}
else
if (*v==NULL)
if ((*u)->fg != NULL) *r=(*u)->fg;
else *r=(*u)->fd;
else
if (*u==(*v)->fg)
if ((*u)->fg!=NULL) (*v)->fg =(*u)->fg;
else (*v)->fg =(*u)->fd;
else
if ((*u)->fg != NULL) (*v)->fd=(*u)->fg;
else (*v)->fd=(*u)->fd;
free(u);
}

36
Chapitre 5:Arbres binaires complets
I – Définitions et propriétés

I-1 Définition :

Soient  un arbre binaire et S un ensemble totalement ordonné.

   : S → S X S U {}

(s) =  ==> s est une feuille.
(s) = (s1, s2) ==> s est un nœud, s1 est fils gauche et s2 est fils droit.
vérifie les conditions sur les arbres.

I-2 Exemple :

S={s0,s1, ..., s12}

s0 est la racine de l’arbre

s

s1 s3

s2 s4 s5 s6

s7 s8 s9 s10

s11 s12

(s0)= (s1,s3) (s5)= 

(s1)= (s2,s4)  (s6)= (s9,s10)
(s2)=  (s7)= 
(s3)= (s5,s6)  (s8)= (s11,s12)
(s4)= (s7,s8)  (s9) ... (s12)= 

I-3 Propriété :

Si N est la nombre de sommets d’un arbre binaire complet, alors le nombre de ses feuilles est (N+1)/2.

corollaire : N est impair et le nombre de nœuds (sommets internes) est (N-1)/2.

37
Preuve :

Soient : Nf : nombre de feuilles

Nn : nombre de nœuds
N : nombre de sommets

(Les nœuds ont deux fils et les feuilles 0 fils)

I-4 Codes associés à un arbre binaire :

On peut associer à un arbre binaire des mots d’un alphabet à deux lettres {g, d}.


a1 a2

a1a1 a1a2 a2a1 a2a2

a1a2a1 a1a2a2 a2a2a1 a2a2a2

a1a2a2a1 a1a2a2a2

Propriété : L’ensemble des mots associés aux feuilles d’un arbre binaire complet constitue un code C
tel que : C U m n’est pas un code  m  C.

Codage de Huffman :

a) Construction de l’arbre de Huffman :

 Pour chaque symbole, créer un arbre avec un nœud et ordonner ces arbres suivants la
fréquence d’apparition.
 Tant qu’il reste plus d’un arbre faire :

Prendre les deux arbres a1 et a2 ayant les plus petites fréquences f1 et f2 / f1 <= f2 et
créer un arbre avec a1 et a2 comme fils gauche et droit.
La fréquence associée au nouvel arbre sera f1 + f2.

Exemple :
Z K F C U D L E
2 7 24 32 37 42 42 120

38
étape 1 :

Z K F C U D L E
2 7 24 32 37 42 42 120

étape 2 :

9 F C U D L E
24 32 37 42 42 120

Z K
2 7

étape 3 :
C 33 U D L E
32 37 42 42 120

9 F
24

Z K
2 7

étape 4 :

U D L 65 E
37 42 42 120

C
33
32

F
9 24

Z K
2 7

39
étape 5 :

L 65 E
42 79
120

C
33 U D
32
37 42

F
24
9

K
Z
7
2

étape 6 :
E
79 107 120

U D L
65
37 42 42

C
33
32

F
24
9

K
Z
7
2

40
étape 7 : E 186
120

79 107

U D L
37 42 65
42

C
33
32

9 F
24

Z K
2 7
étape 8 :
306
0 1
E 186
120

0 1
107
79

0 1 0 1

U D L 65
37 42 42

0 1
C 33
32
0 1

9 F
24
0 1

Z K
2 7

41
b) Le code de Huffman :

On étiquette les arêtes gauches avec 0 et droites avec 1.

Le code d’un symbole est obtenu en concaténant les 0 et les 1 sur le chemin reliant la racine à la feuille
qui contient la fréquence du symbole en question.

Symbole fréquence code nbre de bits

C 32 1110 4
D 42 101 3
E 120 0 1
F 24 11111 5
K 7 111101 6
L 42 110 3
U 37 100 3
Z 2 111100 6

Exemple : codage du mot ULULE = 1001101001100

pour le décodage on utilise l’arbre.

II – Propriétés fondamentales :

II – 1 Encadrement de la hauteur et de la longueur de cheminement :

Rappel : soient x un réel et n un entier.

Lemme 1 :

Pour un arbre binaire ayant n sommet au total et de hauteur h, on a :

Preuve :

Pour une hauteur donnée, nous obtenons deux cas extrêmes :

Soit B un arbre de hauteur h :

1er cas extrême : B est un arbre dégénéré :
2ème cas extrême : B est un arbre complet :

Remarque : Un arbre binaire parfait de hauteur h contient entre 2h et 2h+1-1 sommets et

42
Lemme 2 :

B étant un arbre binaire de taille n et LC étant la longueur de cheminement de B.

Preuve :

- Si B est dégénéré alors :

Un arbre dégénéré maximise la longueur de cheminement.

- Pour l’autre cas extrême, on a un arbre parfait :

On commence par numéroter les nœuds suivant l’ordre hiérarchique.

1 h=0

2 3 h=1

4 5 6 7 h=2

8 9 10 11 12 h=3

un sommet k se trouve à la hauteur

On montre cette propriété par récurrence sur la hauteur des sommets d’un arbre parfait.

- B a un sommet : LB(B)=0=
- supposons la propriété vraie pour les nœuds à la hauteur k : (numérotés de 2k à 2k+1-1)
- considérons le niveau k+1 :

le nœud le plus à gauche a pour numéro (2k+1-1)+1=2k+1

le nœud le plus à droite a pour numéro 2k+1+2k+1-1=2k+2-1
pour le niveau k :
pour le niveau k+1 :

II – 2 Dénombrement des arbres binaires :

Proposition : le nombre d’arbres binaires de taille n est :

rappel : pour

n=0  b0=1
43
n=1 o b1=1

o o

n=2 o o b2=2

o o o o o

n=3 o o o o o o b3=5

o o o o

Le nombre d’arbres binaires localement complets ayant 2n+1 nœuds est :

Exemple : 7 sommets

o o

o o o o

o o o o

o o o o
o o

o o o o

o o o o o o

o o

o o

o o

o o

III – Permutations et arbres binaires :

Définition : Arbre binaire décroissant :

c’est un arbre binaire <S,fd,fg,> dont les sommets sont valués :

44
Théorème : L’image par  de l’ordre symétrique sur un arbre binaire représentant une permutation
détermine cet arbre de manière unique.

Rappel : Soit  une permutation.

Algorithme : Détermination de l’arbre à partir de la suite : l’image par  des sommets

en ordre symétrique.

sommet détermine(sommet 1, 2, ..., n)

si n=1 alors
r ← n
fg(r) ← 0
fd(r) ← 0
sinon
soit i le plus grand de 1, 2, ..., n
r ← i
si i  1 alors
fg(r) ← détermine(1, 2, ..., i-1)
si i  n alors
fd(r) ← détermine(i+1, 2, ..., n)
retourner r

Etapes :

1) Trouver l’ordre symétrique de l’arbre

2) Construire un arbre binaire décroissant, son parcours en ordre symétrique va constituer la

permutation.

3) Utiliser l’algorithme.

Rappel sur l’ordre symétrique :

o3 o3 o3 o3 o3

o2 o2 o1 o2 o2 o2

o1 o1 o1 o1
123 213 132 312 321

o3

o2 o1
231

45
Chapitre 6 : Les Graphes
I- Représentations :

I-1 Listes de successeurs (ou listes d’adjacences) :

Graphe non orienté

Exemple :
Adj
1 2 5
1 2
2 1 5 3 4
3
3 2 4

5 4 4 2 5 3

5 4 1 2

G est un graphe constitué d’un ensemble S de sommets et un ensemble A d’arêtes et noté G=(S,A).
Sur l’exemple le nombre de sommets de S est noté |S|=5, et le nombre d’arcs de A est noté |A|=7.
Une liste de successeurs est un ensemble de |S| listes chaînées. C’est une représentation efficace pour
les graphes peu denses :
Pour chaque sommet , la liste d’adjacences est une liste de sommets v tels qu’il existe un
arc .
Les sommets de chaque liste d’adjacences sont en général chaînés selon un ordre arbitraire.

Graphe orienté

Exemple :

Adj
1 2 3 1 2 4

2 5

3 6 5
4 5 6
4 2

5 4

6 6

Si G est un graphe orienté, la somme des longueurs de toutes les listes d’adjacences vaut |A|.
Si G est non orienté, cette somme vaut 2|A|.

46
L’avantage principal de la représentation par listes d’adjacences est que l’espace mémoire nécessaire
pour stocker le graphe ne dépend que du nombre de sommets et du nombre d’arcs. Par contre, toute
recherche dans le graphe nécessite un parcours des listes d’adjacences.
les listes d’adjacences peuvent être aisément adaptées aux graphes pondérés. Le poids d’un arc (u,v)
peut être stocké dans la cellule contenant le sommet v dans la liste d’adjacences de u.

I-2 Matrice d’adjacences :

Les sommets sont arbitrairement numérotés de 1 à |S|.

Pour un graphe (S,A), la représentation par une matrice d’adjacences M consiste en une matrice
|S| X |S| et M=(aij) telle que :

1 2 M

1 2 3 4 5
3
1 0 1 0 0 1
2 1 0 1 1 1
5 4 3 0 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0

L’espace mémoire nécessaire pour stocker le graphe est O(|S|2) quelque soit le nombre d’arcs.

1 2 3 1 2 3 4 5 6
1 0 1 0 1 0 0
2 0 0 0 0 1 0
3 0 0 0 0 1 1
4 5
4 0 1 0 0 0 0
6
5 0 0 0 1 0 0
6 0 0 0 0 0 1

Transposée :

1 2 3 4 5 6
1 2 3 1 0 0 0 0 0 0
2 1 0 0 1 0 0
3 0 0 0 0 0 0
4 1 0 0 0 1 0
4 5 6 5 0 1 1 0 0 0
6 0 0 0 0 0 1

La transposée d’un matrice d’adjacences d’un graphe non orienté est égale à elle même. On ne
conserve dans ce cas que la diagonale et la partie supérieure de la matrice. Ce qui réduit de presque la
moitié la quantité de mémoire requise pour stocker le graphe.

47
Graphes pondérés :

Si le graphe n’est pas pondéré, on utilise une matrice de bits.

Propriétés des matrices d’adjacences :

Plus généralement, on définit Mij comme le nombre d’arcs d’origine xi et d’extrémité xj. (xi et xj sont
deux sommets du graphe).

Exemple :
1 2 3 4
1 0 1 1 0
2 0 1 1 1
3 0 1 0 2
4 1 0 0 0

Propriété :
Soit M2 la matrice obtenue en multipliant M par M : M2ij représente le nombre de chemins de longueur
2 d’origine xi et d’extrémité xj.
En effet :

( représente le nombre de chemins de longueur 2 passant par k)

xi xj

Mik Mkj

xk

Généralisation :

Propriété :
S’il existe un chemin entre xi et xj , alors il y en a un de longueur inférieur à |S|-1.

Algorithme : Soit M, la matrice d’adjacences d’un graphe G=(S,A) : |S|=n et |A|=m

a=1
N=M
tant que (( < n-1) et Nij=0) faire
N←M*N
←+1
si (Nij = 0) alors
afficher("pas de chemin")
sinon
afficher("Il existe un chemin de longueur:",,"entre",i, "et",j)

48
Remarque :

M*N nécessite n3 opérations.

cet algorithme calcule n-1 fois un produit de matrice  n4 opérations.
opérations.
opérations.
opérations.

II- Définitions :
Soit un graphe G=(S,A). On définit deux applications : org : A → S et ext : A → S.

Chemin :
c’est une suite a1, a2, ..., ak d’arcs telle que : ext(ai)=org(ai+1) pour i=1, ..., k-1.

Chemin propre:
ai=aj ==> i=j
chemin qui ne repasse pas deux fois par le même arc.

Chemin élémentaire:
Si ext(ai)=ext(aj) alors i=j
Il n’existe pas deux arcs ayant la même extrémité.

Circuit :
c’est un chemin propre tel que ext(ak)=org(a1).

Origine d’un chemin :

c’est l’origine du premier arc.

Extrémité d’un chemin :

c’est l’extrémité du dernier arc.

Longueur d’un chemin :

c’est le nombre d’arcs du chemin.

Exemple :

a1 a2 a3 a4 a5 a6 a7 a8 a9
org x1 x2 x2 x1 x3 x2 x3 x4 x3
ext x2 x3 x2 x3 x2 x4 x4 x1 x4
a3

x2
a1 a6 a1 a6 a8 a1 a2 a9 = chemin.
a5 a2 a1 a6 a8 a4 a5 = chemin propre non
x4 élémentaire.
x1 a4 a9 a6 a8 a4 = chemin élémentaire.

x3 a7 a8

49
Graphes symétriques :
Un graphe est symétrique si pour tout arc a, il existe un arc a’ tel que :

ext(a)=org(a’) et ext(a’)=org(a)
Notations

Dans les cas des graphes symétriques on note :

E = ensemble des arêtes. .
X= ensemble des sommets
Un chemin est appelé une chaîne et un circuit est appelé un cycle.

Exemple :
x1 x3
X={ x1, x2 , x3 , x4}
E={ x1, x3},{ x2, x4},{ x2, x3}
x2

x4
Représentation :
x2
x2

===> x1
x1
x3
x3

III- Permutation associée à un graphe symétrique simple :

Soit le graphe symétrique simple :

x1 a9 x2

a6

a7 a8 x3 a5

a4
a3
x5 x4

a1 a2

x6

Soit , on définit a-i comme l’opposé de ai et les arcs seront définis ainsi :
a1 ... am et a-1 ... a-m

a-9 a-8 a-7 a-6 a-5 a-4 a-3 a-2 a-1 a1 a2 a3 a4 a5 a6 a7 a8 a9

org x2 x4 x5 x3 x3 x3 x4 x4 x6 x5 x6 x5 x4 x3 x2 x1 x2 x1
ext x1 x2 x1 x2 x3 x4 x5 x6 x5 x6 x4 x4 x3 x3 x3 x5 x4 x2

50
On définit l’ensemble des arcs ayant xi pour origine :

x1={a7, a9} ; x2={a-9, a6, a8} ; x3={a-6, a-5, a-4, a5}

x4={a-8, a-3, a-2, a4} ; x5={a-7, a1, a3} ; x6={a-1, a2}
On note N le nombre de sommets et M le nombre d’arêtes.
Soit  une permutation sur {1,2, ... , M} U {-1, -2, ..., -M} dont les cycles correspondent aux
ensembles d’arcs ayant un sommet donné pour origine :

= (7,9) (-9,6,8) (-6,-5,-4,5) (-8,-3,-2,4) (-7,1,3) (-1,2)

On peut implémenter un graphe avec trois tableaux de la façon suivante :

Structures de données associées :

SIGMA : tableau[-M ... -1 1 ... M] // permutation 
ORIG : tableau[-M ... -1 1 ... M] //origine de l’arc ai .
PREM : tableau[1 ... N] //pour un sommet xi correspond un arc d’origine xi.

Illustration :
-9 -8 -7 -6 -5 -4 -3 -2 -1 1 2 3 4 5 6 7 8 9
SIGMA 6 -3 1 -5 -4 5 -2 4 2 3 -1 -7 -8 -6 8 9 -9 7
ORIG x2 x4 x5 x3 x3 x3 x4 x4 x6 x5 x6 x5 x4 x3 x2 x1 x2 x1

1 2 3 4 5 6
PREM 7 -9 -6 -3 -7 -1

Algorithme de recherche des successeurs d’un sommet xi :

A=PREM[i] // on cherche un arc qui a xi pour origine

B=SIGMA[A]
afficher(ORIG[-A])
tant que (B  A) faire
afficher(ORIG[-B])
B=SIGMA[B]

Exercice : calculer les successeurs de x1, x3 et x4.

Résumé : Définitions équivalentes d’un graphe symétrique simple :

1) Deux ensembles S et A plus deux applications : org : A → S et ext : A → S plus la condition de

symétrie.
2) Matrice d’adjacences symétrique
3) Listes de successeurs  telle que :

4)  permutation sur {1,2, ... , M} U {-1, -2, ..., -M}.

51
Chapitre 7 : Cheminement dans un Graphe
I- Parcours en largeur :
Données : un graphe G(S,A) orienté simple et un sommet x début de parcours.
Résultats : la liste de tous les sommets y, extrémités d’un chemin d’origine x.

Le parcours en largeur emprunte systématiquement les arcs de G pour « découvrir » tous les sommets
accessibles depuis x. Il peut aussi calculer la distance (plus petit nombre d’arcs) entre x et tous les
sommets accessibles.
Il construit également une arborescence de parcours en largeur de racine x. Cette arborescence
correspond aux plus courts chemins de x à tous les sommets y qu’on peut atteindre dans G. La
méthode fonctionne aussi bien sur les graphes orientés que sur les graphes non orientés.

L’utilisation d’un algorithme empirique pour réaliser un parcours peut conduire à des problèmes
comme la non terminaison (boucle infinie) ou l’oubli d’un sommet.
Pour éviter la non terminaison, on utilise un tableau de booléens Marque[] permettant de marquer les
sommets visités.
Pour enregistrer les distances, on utilise un tableau d’entier d[].
Pour enregistrer l’arbre recouvrant, on utilise un tableau P[] représentant le père de chaque sommet
dans l’arbre.
ParcoursLargeur(G,x)
//initialisation
creerf(f) // une file de sommets
pour i← 1 à N faire
Marque[i] ← 0
d[i] ←
P[i] ← NULL
d[x] ← 0
P[x] ← NULL
Marque[x] ← 1
ajouterf(x,f)
//phase centrale
tant que non vide(f) faire
y ← valeurf(f)
supprimerf(f)
pour tout successeur z de y faire
si (marque[z]=0) alors
Marque[z] ← 1
d[z] ← d[y]+1
P[z] ← y
ajouterf(z,f)
//phase de sortie des résultats
pour i← 1 à N faire
si (Marque[i]=1) alors
afficher(xi)

52
Exemple :
Adj
1 2 5
1 2
2 1 5 3 4
3
3 2 4

5 4 4 2 5 3

5 4 1 2

Résultats du parcours en largeur à partir de x1 :

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
Marque 1 1 1 1 1 d 0 1 2 2 1 p NULL 1 2 2 1

arbre recouvrant :
1 2

5 4

L’arbre obtenu par cet algorithme dépend de l’ordre des successeurs dans les listes. Reprenons le
même graphe implémenté avec les mêmes listes mais avec un ordre différent pour les successeurs.
Adj
1 2 1 5 2

2 3 4 5 1
3
3 4 2
5 4
4 5 3 2

5 4 2 1

Résultats du parcours en largeur à partir de x1 :

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
Marque 1 1 1 1 1 d 0 1 2 2 1 p NULL 1 2 5 1

arbre recouvrant :
1 2

5 4

Exercice : Construire les arbres recouvrant du parcours en largeur en utilisant un autre sommet
comme départ du parcours

53
II- Parcours en profondeur :

ParcoursProfondeur(G,x)
pour i← 1 à N faire
Marque[i] ← 0
P[i] ← NULL
Marque[x] ← 1
Tremaux(x)

Tremaux(x)
pour tout successeur z de y faire
si (marque[z]=0) alors
Marque[z] ← 1
P[z] ← y
Tremaux(z)

Exemple :
Adj
1 2 5
1 2 2 1 5 4 3

3 3 2 4

4 2 3 5
5 4
5 1 2 4

Résultats du parcours en profondeur à partir de x1 :

1 2 3 4 5 1 2 3 4 5
Marque 1 1 1 1 1 p NULL 1 4 5 2

arbre recouvrant :
1 2

5 4

L’arbre obtenu par cet algorithme dépend de l’ordre des successeurs dans les listes. Reprenons le
même graphe implémenté avec les mêmes listes mais avec un ordre différent pour les successeurs.

54
 Adj
1 5 2
1 2
2 3 4 5 1
3
3 4 2

5 4 4 5 3 2

5 4 2 1

Résultats du parcours en profondeur à partir de x1 :

1 2 3 4 5 1 2 3 4 5
Marque 1 1 1 1 1 p NULL 3 4 5 1

arbre recouvrant :
1 2

5 4

Exercice : Construire les arbres recouvrant du parcours en profondeur en utilisant un autre sommet
comme départ du parcours

Exemple de graphe orienté :

Adj
1 2 4
2 3
2 3 4

1 6
3 5 6

4 5 4 5

5 6

Résultats du parcours en profondeur à partir de x1 :

1 2 3 4 5 6 1 2 3 4 5 6
Marque 1 1 1 1 1 1 p NULL 1 2 2 3 5

55
arbre recouvrant :
2 3

1 6

4 5

III- Fermeture transitive d’un graphe :

On se donne un graphe G(S, A, org, ext) et on définit une relation :

Définition :
Un graphe est dit transitif si RG est transitive. i.e. pour tout chemin f, il existe un arc ayant la même
origine et la même extrémité que f.

Exemples :

1) graphe transitif :

2
3
1

4 5

2) graphe non transitif :

2 3

1 6

4 5

56
Fermeture transitive :
(i) C’est le plus petit graphe (S,A’) tel que et (S,A’) est transitif.
(ii) C’est le graphe obtenu à partir de (S,A) en ajoutant des arcs entre les sommets reliés par un chemin.

2 3

1 6

4 5

Algorithme :
Pour tout sommet x faire
Tremaux(x)
ajouter un arc entre x et tous les sommets marqués

IV- Algorithme de forte connexité :

1) Forte connexité d’un graphe :

G(S, A, org, ext) est fortement connexe si :

Exemple :

Graphe fortement connexe. 2 3

Propriété : 4 5

Si G est fortement connexe et pour donné :

2) Algorithme :
Choisir quelconque.
Tremaux( dans G.
S’il existe un sommet non marqué alors
G est non fortement connexe et arrêt.
Construire G’ à partir de G en inversant le sens des arcs.
Tremaux( dans G’.
Si tous les sommets sont marqués alors
G est fortement connexe
sinon
G est non fortement connexe.

57
Exemple :
2 3 2 3
G fortement
connexe 6 6

4 5 4 5

G non fortement
connexe
2 3 2 3

4 5 4 5
1 1

6 6

3) Sommet d’articulation dans un graphe symétrique :

x est un sommet d’articulation dans un graphe symétrique s’il existe y et z deux sommets tels que tous
les chemins reliant y et z passent par x.

2 3 2 3

x x
4 5 4 5
1 1

6 6

x est un sommet d’articulation x n’est pas un sommet d’articulation

x est un sommet d’articulation si et seulement si, en appliquant l’algorithme de Tremaux à partir de x,

on se retrouve avec la pile ne contenant que le marqueur de fond de pile avant la fin de l’algorithme.

58
#include "entete_graphe.h"
#include "file.h"
#include "pile.h"
#include "listes.h"
#define N 6
#define M 6

void largeur(cellule **g, int s,int n){

file f; creerf(&f);
int *marque= (int *) malloc((n+1)*sizeof(int));
int i,y;
cellule *z;
for (i=0;i<=n;i++) marque[i]=0;
ajouterf(s,&f);
marque[s]=1;
printf("descente en largeur:\n");
while(!videf(f)) {
y=valeurf(f);
supprimerf(&f);
z=g[y];
while (z!=NULL) {
if (marque[(*z).val] ==0) {
printf("%d ----> %d\n",y,(*z).val);
ajouterf((*z).val,&f);
marque[(*z).val] =1;
}

z=z->lien;
}
}
}

void tremaux(cellule **g,int s, int n,int p[],int m[]){

cellule *z=g[s];
while (z!=NULL){
if (m[(*z).val]==0) {
m[(*z).val]=1;
p[(*z).val]=s;
printf("%d --> %d\n",s,(*z).val);
tremaux(g,(*z).val,n,p,m);
}
z=z->lien;
}
}

void profondeur(cellule **g,int s, int n,int p[],int marque[]){

int i;
for (i=0;i<=n;i++) {marque[i]=0;p[i]=-1;}
marque[s]=1;
printf("parcours en profondeur recursif:\n");
tremaux(g,s,n,p,marque);
}

59
void profondeur_iteratif(cellule **g,int s, int n,int pere[],int marque[]){
int i,art=0;
for (i=0;i<=n;i++) {marque[i]=0;pere[i]=-1;}
marque[s]=1;
pile p; creerp(&p);
ajouterp(-1,&p);
cellule *z;
int y=s;
z=g[y];
printf("parcours en profondeur iteratif:\n");
while (!videp(p)){
if (z!=NULL){
if (marque[(*z).val] == 0){
printf("%d --> %d\n",y,(*z).val);
if ((valeurp(p)==-1) && (art==1))
printf("%d = point d'articulation\n",s);
ajouterp(y,&p);art=1;
marque[(*z).val]=1;
pere[(*z).val]=y ;
y=(*z).val;
z=g[y];
}
else z=z->lien;
}
else{
y=valeurp(p);
supprimerp(&p);
z=g[y];
}
}
}

main(){
int i,j;
int m_adj[N+1][M+1]={{0,0,0,0,0,0,0},{0,0,1,0,1,0,0}, {0,0,0,0,0,1,0},
{0,0,0,0,0,1,1},{0,0,1,0,0,0,0},{0,0,0,0,1,0,0},{0,0,0,0,0,0,1}};
cellule **g=(cellule **)malloc((N+1)*sizeof(cellule *));
for (i=1;i<=N;i++) g[i]=(cellule *)NULL;

for (i=1;i<=N;i++)
for (j=1; j<=M;j++)
if (m_adj[i][j]!=0)
g[i]=inserer_fin(g[i],creer(j));

for (i=1;i<=N;i++){
printf("sommet %d -->",i);
aff_liste(g[i]);}

largeur(g, 3,N);

int *marque= (int *) malloc((N+1)*sizeof(int));

int *pere= (int *) malloc((N+1)*sizeof(int));
profondeur(g,3,N,pere,marque);
profondeur_it(g,3,N,pere,marque);

for (i=1;i<=N;i++) printf("%2d",i);printf("\n");

for (i=1;i<=N;i++) printf("%2d",marque[i]);printf("\n");
for (i=1;i<=N;i++) printf("%2d",pere[i]);printf("\n");
}

60