146
Structures de données listes, piles, files, arbres binaires Jacques Le Maitre Université du Sud Toulon-Var Ce cours est mis à disposition selon les termes de la licence Creative Commons Paternité-Pas d'Utilisation Commerciale-Pas de Modification 2.0 France

Structures Donnees

Embed Size (px)

Citation preview

Page 2: Structures Donnees

Bibliographie

Robert Sedgewick, Algorithmes en langage C, InterEditions.

Ouvrage collectif (coordination Luc Albert), Cours et exercices d'informatique, Vuibert.

Donald E. Knuth, The Art of Computer Programming, Volume 1, 2 et 3, Addison-Wesley.

Jacques Le Maitre I41 : Types de données 2

Page 3: Structures Donnees

Définition et implantation d’un type de données

1. Définir formellement les données de ce type.

2. Définir l’interface du type de données : un jeu d’opérations pour manipuler ces données en commençant

par les opérations primitives : celles à partir desquelles les autres peuvent être définies.

3. Choisir une représentation de ces données.

4. Définir les opérations relativement à cette représentation.

5. Choisir un langage de programmation.

6. Définir, en termes de ce langage, la représentation des données et les opérations.

7. Regrouper ces définitions dans un module constituant l’implantation du type de données.

Jacques Le Maitre I41 : Types de données 3

Page 4: Structures Donnees

Structures de données étudiées

Les listes linéaires et deux spécialisations importantes de ces listes : les piles

les files

Les arbres binaires.

Jacques Le Maitre I41 : Types de données 4

Page 5: Structures Donnees

Implantation des structures de données

Deux modes d’implantation seront étudiés : structures « modifiables en place », pour les listes linéaires,

structures non modifiables évoluant par reconstruction, pour les arbres binaires.

Le premier mode implique une programmation par effets de bord c.-à-d. où les changements d’état de la mémoire sont explicites.

Le second mode est parfaitement adapté à la programmation fonctionnelle.

Le premier mode est plus efficace en temps et en mémoire.

Le second mode privilégie une programmation déclarative.

Le langage de programmation choisi est le langage C.

Jacques Le Maitre I41 : Types de données 5

Page 6: Structures Donnees

LISTES LINÉAIRES

Page 7: Structures Donnees

Définition formelle

Soit T un type de données.

Une liste linéaire de valeurs de type T est une suite de n (n ≥ 0) valeurs v1, ..., vn rangées de façon à ce que : si n > 0, v1 est la première valeur dans ce rangement et vn est la

dernière,

si 1 < k <n, vk est précédée par la valeur vk-1 et suivie par la valeur vk+1.

(Donald E. Knuth, The Art of Computer Programming, Volume 1, Fundamental Algorithms, Third Edition, p. 238)

Notation : [] liste linéaire vide

[v1, ..., vn] liste linéaire non vide

Jacques Le Maitre I41 : Types de données 7

Page 8: Structures Donnees

Opérations primitives sur les listes linéaires (1)

On note : Vide le type dont l’unique valeur est la valeur rien notée ()

T : un type de données,

Liste(T) le type des listes linéaires de valeurs de type T,

Position le type des positions d’une valeur dans une liste linéaire,

Booléen le type d’extension {vrai, faux},

positions(l) l’ensemble des positions des valeurs de la liste linéaire l,

pos(v) la position de la valeur v dans la liste considérée,

↝ la modification en place d’une liste.

Jacques Le Maitre I41 : Types de données 8

Page 9: Structures Donnees

Opérations primitives sur les listes linéaires (2)

Création d’une liste vide créer-liste : Vide → Liste(T)

créer-liste : () ↦ []

Test de liste vide liste-vide : Liste(T) → Booléen

liste-vide : [] ↦ vrai

liste-vide : [...v...] ↦ faux

Jacques Le Maitre I41 : Types de données 9

Page 10: Structures Donnees

Opérations primitives sur les listes linéaires (3)

Insertion d’une valeur en début de liste insérer_au_début : Liste(T) T → Vide

insérer_au_début : ([...], v) ↦ ()

effet de bord : [...] ↝ [v...]

Insertion d’une valeur après une position donnée insérer_après : Liste(T) Position T → Liste(T)

insérer_après : (l, p, v) ↦ erreur ! (si p positions(l))

insérer_après : ([...w...] , p, v) où p = pos(w) ↦ ()

effet de bord : [...w...] ↝ [...w, v...]

Jacques Le Maitre I41 : Types de données 10

Page 11: Structures Donnees

Opérations primitives sur les listes linéaires (4)

Suppression d’une valeur dont la position est donnée supprimer : Liste(T) Position → Vide

supprimer : (l, p) ↦ erreur ! (si p positions(l))

supprimer : ([...v...], p) où pos(v) = p ↦ ()

effet de bord : [...v...] ↝ [...]

Jacques Le Maitre I41 : Types de données 11

Page 12: Structures Donnees

Opérations primitives sur les listes linéaires (5)

Sélection de la valeur dont la position est donnée valeur : Liste(T) Position → T

valeur : (l, p) ↦ erreur ! (si p positions(l))

valeur : ([...v...], p) où pos(v) = p ↦ v

Remplacement de la valeur dont la position est donnée remplacer : Liste(T) Position T → Liste(T)

remplacer : (l, p, w) ↦ erreur ! (si p positions(l))

remplacer : ([...v...], p, w) où pos(v) = p ↦ ()

effet de bord : [...v...] ↝ [...w...]

Jacques Le Maitre I41 : Types de données 12

Page 13: Structures Donnees

Types paramétrés et polymorphisme

Le type Liste(T) est un type paramétré. Il englobe tous les types de listes obtenus en remplaçant le paramètre de type T par un type effectif : Liste(Entier), Liste(Flottant), Liste (Point), etc.

Les opérations sur le type Liste(T) sont dites polymorphes car elles s’appliquent à toutes les listes quelque soit T.

Par exemple, la fonction :

liste_vide : Liste(T) → Booléen

s’applique aussi bien aux listes de types : Liste(Entier), Liste(Flottant), Liste(Point), etc.

Il n’est pas nécessaire d’écrire une définition pour chacun de ces types : une seule définition, dite générique, est suffisante quelque soit T.

Jacques Le Maitre I41 : Types de données 13

Page 14: Structures Donnees

Représentations d’une liste linéaire

Plusieurs représentations des listes linéaires ont été proposées.

La plupart consistent à enregistrer chaque valeur dans une cellule de la mémoire et à chaîner ces cellules entre elles.

Elles se différencient principalement par : le mode de mémorisation des cellules : dans un tableau ou bien

dans une zone mémoire allouée dynamiquement,

le mode de de marquage du début ou de la fin de la liste,

le mode de chaînage des cellules : unidirectionnel ou bidirectionnel.

Jacques Le Maitre I41 : Types de données 14

Page 15: Structures Donnees

Notre représentation d’une liste linéaire

Une liste linéaire est représentée comme une chaîne de maillons composée : d’un maillon de début,

d’une suite éventuellement vide de maillons internes,

d’un maillon de fin.

Chaque maillon a un identifiant.

Le maillon de début contient l’identifiant du 1er maillon interne.

Le ie maillon interne contient la ie valeur de la liste linéaire et l’identifiant du maillon contenant la (i + 1)e valeur.

Le maillon de fin a un identifiant nul.

Le maillon suivant du maillon de début d’une liste linéaire vide est le maillon de fin.

Une liste est identifiée par l'identifiant de son maillon de début.

Jacques Le Maitre I41 : Types de données 15

Page 16: Structures Donnees

Notre représentation d’une liste linéaire

Jacques Le Maitre I41 : Types de données 16

liste vide

maillon de début

maillon interne

liste non vide

maillon de fin

u v w

valeur

Page 17: Structures Donnees

Propriétés de cette représentation

La position d’une valeur est l’identifiant du maillon qui la contient.

Le chaînage est unidirectionnel et dirigé de la première vers la dernière valeur : la 1ère valeur est atteinte à partir du maillon de début,

la ke valeur (k > 1) est atteinte à partir du maillon contenant la (k – 1)e valeur.

Une opération suivant est nécessaire pour passer d’un maillon à l’autre.

L’opération supprimer est remplacée par une opération supprimer-suivant.

L’opération insérer-au-début est redondante et donc non définie, car : insérer-au-début(l, v) insérer-après(l, v)

puisque l est l’identifiant du maillon de début.

Une opération fin-liste est nécessaire pour tester que le maillon de fin a été atteint.

Jacques Le Maitre I41 : Types de données 17

Page 18: Structures Donnees

créer-liste

Jacques Le Maitre I41 : Types de données 18

créer-liste()

Page 19: Structures Donnees

fin-liste

Jacques Le Maitre I41 : Types de données 19

fin-liste(m) faux

m

fin-liste(m) vrai

m

Page 20: Structures Donnees

liste-vide

Jacques Le Maitre I41 : Types de données 20

liste-vide(l) faux

liste-vide(l) vrai

l

l

Page 21: Structures Donnees

insérer-après

Jacques Le Maitre I41 : Types de données 21

insérer-après(m, v)

nouveau maillon

m

m

v

Page 22: Structures Donnees

supprimer-suivant

Jacques Le Maitre I41 : Types de données 22

supprimer-suivant(m)

m

m

Page 23: Structures Donnees

suivant

Jacques Le Maitre I41 : Types de données 23

suivant(m1) m2

m1 m2

nul

m

suivant(m)

Page 24: Structures Donnees

valeur

Jacques Le Maitre I41 : Types de données 24

valeur(m) v v

m

Page 25: Structures Donnees

Représentation chaînée par pointeurs

Jacques Le Maitre I41 : Types de données 25

mémoire

(v1, a2)

a1

(_, 0)

a4

(_, a1) (v2, a3)

a2 (v3, a4)

a3

v1 v2 v3 l

l

Page 26: Structures Donnees

Représentation d'une liste linéaire en C

Jacques Le Maitre I41 : Types de données 26

struct maillon

{

valeur

suivant

}

NULL

NULL

[]

v1 v2 v3

struct maillon

{

valeur

suivant

}

NULL

struct maillon

{

valeur

suivant

}

struct maillon

{

valeur

suivant

}

struct maillon

{

valeur

suivant

}

NULL

[v1, v2, v3]

typedef struct maillon Maillon;

typedef Maillon *Liste;

struct maillon

{

void *valeur;

Maillon *suivant;

}

Page 27: Structures Donnees

Interface du type Liste linéaire en C

Les déclarations des types Maillon et Liste ainsi que

les déclarations des fonctions de l’interface sont enregistrées dans le fichier TD-liste-lineaire.h.

Les définitions des fonctions de l’interface sont enregistrées dans le fichier TD-liste-lineaire.c.

Jacques Le Maitre I41 : Types de données 27

Page 28: Structures Donnees

Polymorphisme

Les fonctions de cet interface sont polymorphes, c.-à-d. qu'elles s'appliquent à toute liste de valeurs quelque soit le type T de ces valeurs.

Cela est possible parce que : ce ne sont pas directement les valeurs qui sont contenues dans les

maillons, mais les adresses des variables contenant ces valeurs,

le champ valeur d'un maillon est de type void *, on peut donc

lui affecter n'importe quel type d'adresse par définition du type void * en C, et donc l'adresse d'une variable de type T.

Pour accéder à la valeur de la variable dont l'adresse est contenue dans un maillon, il faudra au préalable convertir cette adresse en une adresse de variable de type T.

Jacques Le Maitre I41 : Types de données 28

Page 29: Structures Donnees

Exemple

Supposons que l’on veuille créer et manipuler une liste de personnes décrites par leur nom et leur âge.

Supposons que la description d'une personne soit une instance du type Personne défini par : typedef struct

{

char *nom,

int age;

} Personne

La description d'une personne à insérer dans une liste devra être affectée à une variable de type Personne (allouée par un appel à malloc, par exemple) : C'est l'adresse de cette variable qui sera affectée dans le maillon correspondant

à la place de cette personne dans cette liste.

Pour obtenir la description de la personne dont l'adresse est contenue dans un maillon il faudra au préalable convertir cette adresse en une adresse de type Personne *.

Jacques Le Maitre I41 : Types de données 29

Page 30: Structures Donnees

Fichier TD-liste-lineaire.h (1)

#ifndef TD_LISTE_LINEAIRE

#define TD_LISTE_LINEAIRE

#include <stdlib.h>

#include <stddef.h>

#include "erreur.h"

typedef struct maillon Maillon;

typedef Maillon *Liste;

struct maillon

{

void *valeur;

Maillon *suivant;

};

Jacques Le Maitre I41 : Types de données 30

Page 31: Structures Donnees

Fichier TD-liste-lineaire.h (2)

Liste creer_liste(void);

int fin_liste(Maillon *m);

int liste_vide(Liste l);

Maillon *inserer_apres(Maillon *m, void *v);

void supprimer_suivant(Maillon *m);

Maillon *suivant(Maillon *m);

void *valeur(Maillon *m);

#endif

Jacques Le Maitre I41 : Types de données 31

Primitives

Page 32: Structures Donnees

Créer une liste linéaire

Liste creer_liste(void)

{

Maillon *d, *f;

d = (Maillon *) malloc(sizeof(Maillon));

if (d == NULL)

erreur("creer_liste");

d->suivant = NULL;

return d;

}

Jacques Le Maitre I41 : Types de données 32

Page 33: Structures Donnees

Le maillon m est-il le maillon de fin de liste ?

int fin_liste(Maillon *m)

{

return m == NULL;

}

Jacques Le Maitre I41 : Types de données 33

Page 34: Structures Donnees

La liste l est-elle vide ?

int liste_vide(Liste l)

{

return l->suivant == NULL;

}

Jacques Le Maitre I41 : Types de données 34

Page 35: Structures Donnees

Insérer un maillon contenant la valeur v après le maillon m

Maillon *inserer_apres(Maillon *m, void *v)

{

Maillon *s;

if (fin_liste(m))

erreur("inserer_apres");

s = (Maillon *) malloc(sizeof(Maillon));

if (s == NULL)

erreur("inserer_apres");

s->valeur = v;

s->suivant = m->suivant;

m->suivant = s;

return s;

}

Jacques Le Maitre I41 : Types de données 35

On retourne l'adresse du maillon inséré.

Page 36: Structures Donnees

Supprimer le maillon suivant le maillon m

void supprimer_suivant(Maillon *m)

{

if (fin_liste(m))

erreur("supprimer_suivant");

if (!fin_liste(m->suivant))

m->suivant = m->suivant->suivant;

}

Jacques Le Maitre I41 : Types de données 36

Si le maillon suivant de m est la fin de la

liste, on ne fait rien.

Page 37: Structures Donnees

Maillon suivant le maillon m

Maillon *suivant(Maillon *m)

{

if (fin_liste(m))

erreur("suivant");

return m->suivant;

}

Jacques Le Maitre I41 : Types de données 37

Page 38: Structures Donnees

Valeur contenue dans le maillon m

void *valeur(Maillon *m)

{

if (fin_liste(m))

erreur("valeur");

return m->valeur;

}

Jacques Le Maitre I41 : Types de données 38

Page 39: Structures Donnees

Autres opérations

Longueur d’une liste

ne valeur d’une liste

Copie d’une liste

Fusion de 2 listes d’entiers triées par ordre croissant

Jacques Le Maitre I41 : Types de données 39

Page 40: Structures Donnees

nième maillon de la liste l

Maillon *nieme(Liste l, int n)

{

Maillon *m = l;

int i = 0;

while (!fin_liste(m) && i < n)

{

i++;

m = suivant(m);

}

if (i != n)

erreur("nieme");

return m;

}

Jacques Le Maitre I41 : Types de données 40

Si i est différent de n, c’est que n est inférieur à 0 ou supérieur à la longueur de la liste : erreur, c’est au programme appelant de vérifier que le rang demandé est valide !

Page 41: Structures Donnees

Longueur de la liste l

int longueur_liste(Liste l)

{

Maillon *m;

int i = 0;

m = suivant(l);

while (!fin_liste(m))

{

i++;

m = suivant(m);

}

return i;

}

Jacques Le Maitre I41 : Types de données 41

Page 42: Structures Donnees

Copier la liste l1

Maillon *copier_liste(Liste l1)

{

Liste l2;

Maillon *m1, *m2;

l2 = creer_liste();

m1 = suivant(l1);

m2 = l2;

while (!fin_liste(m1))

{

m2 = inserer_apres(m2, valeur(m1));

m1 = suivant(m1);

}

return l2;

}

Jacques Le Maitre I41 : Types de données 42

Page 43: Structures Donnees

Fusion de 2 listes d’entiers l1 et l2 ordonnées (1)

int entier(void *v)

{

return *((int *) v);

}

Maillon *fusion_listes(Liste l1, Liste l2)

{

Liste l3;

Maillon *m1, *m2, *m3;

l3 = creer_liste();

m1 = suivant(l1);

m2 = suivant(l2);

m3 = l3;

...

Jacques Le Maitre I41 : Types de données 43

entier pointé par v

Page 44: Structures Donnees

Fusion de 2 listes d’entiers l1 et l2 ordonnées (2)

...

while (!fin_liste(m1) && !fin_liste(m2))

{

if (entier(valeur(m1)) < entier(valeur(m2)))

{

m3 = inserer_apres(m3, valeur(m1));

m1 = suivant(m1);

}

else

{

m3 = inserer_apres(m3, valeur(m2));

m2 = suivant(m2);

}

}

...

Jacques Le Maitre I41 : Types de données 44

Page 45: Structures Donnees

Fusion de 2 listes d’entiers l1 et l2 ordonnées (3)

...

while (!fin_liste(m1))

{

m3 = inserer_apres(m3, valeur(m1));

m1 = suivant(m1);

}

while (!fin_liste(m2))

{

m3 = inserer_apres(m3, valeur(m2));

m2 = suivant(m2);

}

return l3;

}

Jacques Le Maitre I41 : Types de données 45

Page 46: Structures Donnees

Allocation et libération de maillons (1)

Jacques Le Maitre I41 : Types de données 46

0 (_, adresse case 4)

1 (_, adresse nulle)

l 2 (_, adresse case 3)

3 (v1, adresse case 6)

4 (_, adresse case 9)

5 (_, adresse case 1)

6 (v2, adresse case 7)

7 (v3, adresse nulle)

libre 8 (_, adresse case 0)

9 (_, adresse case 5)

maillons

v1 v2 l v3

Page 47: Structures Donnees

Allocation et libération de maillons(2) #include "TD-liste-lineaire.h"

#define TAILLE 1000

static Maillon maillons[TAILLE];

static int configurer_liste_maillons = 1;

static Maillon *libre;

static Maillon *allouer_maillon(void)

static void liberer_maillon(Maillon *m)

Liste creer_liste(void)

int fin_liste(Maillon *m)

int liste_vide(Liste l)

Maillon *inserer_apres(Maillon *m, void *v)

void supprimer_suivant(Maillon *m)

Maillon *suivant(Maillon *m)

void *valeur(Maillon *m)

Jacques Le Maitre I41 : Types de données 47

Gestion de la mémoire

Dans les fonctions creer_liste,

inserer_apres et supprimer_suivant

les fonctions allouer_maillon et liberer_maillon

seront utilisées au lieu de malloc et free.

Page 48: Structures Donnees

Allocation et libération de maillons (3) static Maillon *allouer_maillon(void)

{

int i;

Maillon *m;

if (configurer_liste_maillons)

{

for (i = 0; i < TAILLE - 1; i++)

maillons[i].suivant = maillons + i + 1;

maillons[i].suivant = NULL;

libre = maillons;

configurer_liste_maillons = 0;

}

if (libre == NULL)

return NULL;

m = libre;

libre = m->suivant;

return m;

}

Jacques Le Maitre I41 : Types de données 48

Page 49: Structures Donnees

Allocation et libération de maillons(4)

static void liberer_maillon(Maillon *m)

{

m->suivant = libre;

libre = m;

}

Jacques Le Maitre I41 : Types de données 49

Page 50: Structures Donnees

PILES

Page 51: Structures Donnees

Définition formelle

Une pile est une liste linéaire l pour laquelle les insertions et les suppressions sont effectuées au début de l : la première valeur de l est le

sommet de la pile,

empiler une valeur c’est l’insérer au début de l,

dépiler une valeur, si l est non vide, c’est sélectionner la première valeur de l et la supprimer de l.

Jacques Le Maitre I41 : Types de données 51

v3

v2

v1

sommet

pile vide

v2

v1

v2

v1

pile non vide

empiler v3 v3 = dépiler

v2

v1

[v2, v1] []

Page 52: Structures Donnees

Opérations primitives sur les piles (1)

On note : Pile(T) : le type des piles de valeurs de type T

Création d’une pile créer-pile : Vide → Pile(T)

créer-pile : () ↦ []

Test de pile vide pile-vide : Pile(T) → Booléen

pile-vide : [] ↦ vrai

pile-vide : [v...] ↦ faux

Jacques Le Maitre I41 : Types de données 52

Page 53: Structures Donnees

Opérations primitives sur les piles (2)

Empiler une valeur empiler : Pile(T) T → Vide

empiler : ([...], v) ↦ ()

effet de bord : [...] ↝ [v...]

Dépiler une valeur dépiler : Pile(T) → T

dépiler : [] ↦ erreur !

depiler : [v...] ↦ v

effet de bord : [v...] ↝ [...]

Sélectionner la valeur située au sommet sommet : Pile(T) → T

sommet : [] ↦ erreur !

sommet : [v, ...] ↦ v

Jacques Le Maitre I41 : Types de données 53

Page 54: Structures Donnees

Représentation d’une pile

Jacques Le Maitre I41 : Types de données 54

v3

v2

v1

v3 v2 v1

sommet

Page 55: Structures Donnees

créer-pile

Jacques Le Maitre I41 : Types de données 55

créer_pile()

Page 56: Structures Donnees

pile-vide

Jacques Le Maitre I41 : Types de données 56

pile-vide(p) faux

p

pile-vide(p) vrai

p

sommet

Page 57: Structures Donnees

empiler

Jacques Le Maitre I41 : Types de données 57

empiler(p, v)

p

p

v

sommet

sommet

Page 58: Structures Donnees

dépiler

Jacques Le Maitre I41 : Types de données 58

dépiler(p)

p

v

p

v /

sommet

sommet

Page 59: Structures Donnees

sommet

Jacques Le Maitre I41 : Types de données 59

sommet(p)

p

v

v

sommet

Page 60: Structures Donnees

Représentation d'une pile en C

Jacques Le Maitre I41 : Types de données 60

struct maillon

{

valeur

suivant

}

NULL

NULL

[]

v3 v2 v1

struct maillon

{

valeur

suivant

}

NULL

struct maillon

{

valeur

suivant

}

struct maillon

{

valeur

suivant

}

struct maillon

{

valeur

suivant

}

NULL

[v3, v2, v1]

typedef Liste Pile;

Page 61: Structures Donnees

Interface

La déclaration du type Pile ainsi que les déclarations des

fonctions de l’interface sont enregistrés dans le fichier TD-pile.h.

Les définitions des fonctions de l’interface sont enregistrées dans le fichier TD-pile.c.

Jacques Le Maitre I41 : Types de données 61

Page 62: Structures Donnees

Fichier TD-pile.h

#ifndef TD_PILE

#define TD_PILE

#include "TD-liste-lineaire.h"

#include "erreur.h"

typedef Liste Pile;

Pile creer_pile(void);

int pile_vide(Pile p);

void empiler(Pile p, void *v);

void *depiler(Pile p);

void *sommet(Pile p);

#endif

Jacques Le Maitre I41 : Types de données 62

Primitives

Page 63: Structures Donnees

Créer une pile

Pile creer_pile(void)

{

return creer_liste();

}

Jacques Le Maitre I41 : Types de données 63

Page 64: Structures Donnees

La pile p est-elle vide ?

int pile_vide(Pile p)

{

return liste_vide(p);

}

Jacques Le Maitre I41 : Types de données 64

Page 65: Structures Donnees

Empiler une valeur v au sommet d’une pile p

void empiler(Pile p, void *v)

{

inserer_apres(p, v);

}

Jacques Le Maitre I41 : Types de données 65

Page 66: Structures Donnees

Dépiler la valeur au sommet de la pile p

void *depiler(Pile p)

{

void *v;

if (pile_vide(p))

erreur("depiler");

v = valeur(suivant(p));

supprimer_suivant(p);

return v;

}

Jacques Le Maitre I41 : Types de données 66

Page 67: Structures Donnees

Valeur au sommet de la pile p

void *sommet(Pile p)

{

if (pile_vide(p))

erreur("sommet");

return valeur(suivant(p));

}

Jacques Le Maitre I41 : Types de données 67

Page 68: Structures Donnees

FILES

Page 69: Structures Donnees

Définition formelle

Une file est une liste linéaire l pour laquelle les insertions sont réalisées à la fin de l et les suppressions sont effectuées au début de l : la première valeur de l est la tête de la file et la dernière est la queue

de la file,

entrer une valeur c’est l’ajouter à la fin de de l,

sortir une valeur, si l est non vide, c’est sélectionner la première valeur de l et la supprimer de l.

Jacques Le Maitre I41 : Types de données 69

v3 v2 v1

[] [v1, v2, v3]

v2 v1 v3 v2 v1 v3 v2

entrer v3 v1 = sortir

queue tête

file vide file non vide

Page 70: Structures Donnees

Opérations primitives sur les files (1)

On note : File(T) : le type des files de valeurs de type T

Création d’une file vide créer-file : Vide → File(T)

créer-file : () ↦ []

Test de file vide file-vide : File(T) → Booléen

file-vide : [] ↦ vrai

file-vide : [v...] ↦ faux

Jacques Le Maitre I41 : Types de données 70

Page 71: Structures Donnees

Opérations primitives sur les files (2)

Entrer une valeur dans une file entrer : File(T) T → Vide

entrer : ([...], v) ↦ ()

effet de bord : [...] ↝ [...v]

Sortir une valeur d’une file sortir : File(T) → T

sortir : [] ↦ erreur !

sortir : [v...] ↦ v

effet de bord : [v...] ↝ [...]

Jacques Le Maitre I41 : Types de données 71

Page 72: Structures Donnees

Opérations primitives sur les files (3)

Sélectionner la valeur en tête d’une file tête : File(T) → T

tête : [v...] ↦ v

tête : [] ↦ erreur !

Sélectionner la valeur en queue d’une file queue : File(T) → T

queue : [...v] ↦ v

queue : [] ↦ erreur !

Jacques Le Maitre I41 : Types de données 72

Page 73: Structures Donnees

Représentation d’une file

Jacques Le Maitre I41 : Types de données 73

v3 v2 v1

file vide

v2 v3 v1

tête queue

Page 74: Structures Donnees

créer-file

Jacques Le Maitre I41 : Types de données 74

créer_file()

Page 75: Structures Donnees

file-vide

Jacques Le Maitre I41 : Types de données 75

file_vide(f) faux

f

file_vide(f) vrai

f

Page 76: Structures Donnees

entrer

Jacques Le Maitre I41 : Types de données 76

entrer(f, v3)

f

v1 v2

f

v1 v2 v3

queue

queue

Page 77: Structures Donnees

sortir

Jacques Le Maitre I41 : Types de données 77

sortir(f)

f

v1 v2 v3

v1 /

f

v2 v3

tête

tête

Page 78: Structures Donnees

tête

Jacques Le Maitre I41 : Types de données 78

tête(f)

v

f

v

tête

Page 79: Structures Donnees

queue

Jacques Le Maitre I41 : Types de données 79

queue(f)

v

f

v

queue

Page 80: Structures Donnees

Représentation d'une file en C

Jacques Le Maitre I41 : Types de données 80

typedef struct file *File;

struct file

{

Liste liste;

Maillon *queue;

};

[v1, v2 ]

v1 v2

struct file

{

liste

queue

}

struct maillon

{

valeur

suivant

}

NULL

struct maillon

{

valeur

suivant

}

struct maillon

{

valeur

suivant

}

NULL

[]

struct maillon

{

valeur

suivant

}

NULL

NULL

struct file

{

liste

queue

}

NULL

Page 81: Structures Donnees

Interface

La déclaration du type File ainsi que les déclarations des

fonctions de l’interface sont enregistrés dans le fichier TD-file.h.

Les définitions des fonctions de l’interface sont enregistrées dans le fichier TD-file.c.

Jacques Le Maitre I41 : Types de données 81

Page 82: Structures Donnees

Fichier TD-file.h (1)

#ifndef TD_FILE

#define TD_FILE

#include <stdlib.h>

#include <stddef.h>

#include "TD-liste-lineaire.h"

#include "erreur.h"

typedef struct file *File;

struct file

{

Liste liste;

Maillon *queue;

};

Jacques Le Maitre I41 : Types de données 82

Page 83: Structures Donnees

Fichier TD-file.h (2)

File creer_file(void);

int file_vide(File f);

void entrer(File f, void *v);

void *sortir(File f);

void *tete(File f);

void *queue(File f);

#endif

Jacques Le Maitre I41 : Types de données 83

Primitives

Page 84: Structures Donnees

Créer une file

File creer_file(void)

{

File f;

Liste l;

f = (File) malloc(sizeof(struct file));

if (f == NULL)

erreur("creer_file");

l = creer_liste();

f->queue = l;

f->liste = l;

return f;

}

Jacques Le Maitre I41 : Types de données 84

Page 85: Structures Donnees

La file f est-elle vide ?

int file_vide(File f)

{

return liste_vide(f->liste);

}

Jacques Le Maitre I41 : Types de données 85

Page 86: Structures Donnees

Entrer une valeur v dans une file f

void entrer(File f, void *v)

{

f->queue = inserer_apres(f->queue, v);

}

Jacques Le Maitre I41 : Types de données 86

Page 87: Structures Donnees

Sortir une valeur d’une file f

void *sortir(File f)

{

void *v;

if (file_vide(f))

erreur("sortir");

v = valeur(suivant(f->liste));

supprimer_suivant(f->liste);

if (file_vide(f))

f->queue = f->liste;

return v;

}

Jacques Le Maitre I41 : Types de données 87

Page 88: Structures Donnees

Valeur en tête d’une file f

void *tete(File f)

{

if (file_vide(f))

erreur("tete");

return valeur(suivant(f->liste));

}

Jacques Le Maitre I41 : Types de données 88

Page 89: Structures Donnees

Valeur en queue d’une file f

void *queue(File f)

{

if (file_vide(f))

erreur("queue");

return valeur(f->queue);

}

Jacques Le Maitre I41 : Types de données 89

Page 90: Structures Donnees

ARBRES BINAIRES

Page 91: Structures Donnees

Définition formelle

Un arbre binaire est un ensemble fini de valeurs qui est : soit vide,

soit constitué d’une racine et des valeurs de deux arbres binaires disjoints appelés sous-arbre gauche et sous-arbre droit de la racine.

(Donald E. Knuth, The Art of Computer Programming, Volume 1, Fundamental Algorithms, 3rd Edition, p. 312)

Jacques Le Maitre I41 : Types de données 91

AB vide

AB vide

AB vide

AB vide

AB vide

AB

AB

AB

v1

v2

v3 v4

arbre(v1, arbre(), arbre(v2, arbre(v3, arbre(), arbre()), arbre(v4, arbre(), arbre()))

AB

Page 92: Structures Donnees

Opérations primitives sur les arbres binaires (1)

On note : Arbre(T) : le type des arbres binaires de valeurs de type T

Jacques Le Maitre I41 : Types de données 92

Page 93: Structures Donnees

Opérations primitives sur les arbres binaires (2)

Création d’un arbre binaire vide cons-arbre-vide : Vide → Arbre(T)

cons-arbre-vide : ↦ ()

Création d’un arbre binaire non vide cons-arbre : T Arbre(T) Arbre(T) → Arbre(T)

cons-arbre : (v, a1, a2) ↦ arbre (v, a1, a2)

Test d’arbre vide arbre-vide : Arbre(T) → Booléen

arbre-vide : arbre() ↦ vrai

arbre-vide : arbre(v, a1, a2) ↦ faux

Jacques Le Maitre I41 : Types de données 93

Page 94: Structures Donnees

Opérations primitives sur les arbres binaires (3)

Racine d’un arbre racine : Arbre(T) → T

racine : () ↦ erreur !

racine : arbre(v, a1, a2) ↦ v

Sous-arbre gauche de la racine d’un arbre gauche : Arbre(T) → Arbre(T)

gauche : () ↦ erreur !

gauche : arbre(v, a1, a2) ↦ a1

Sous-arbre droit de la racine d’un arbre droit : Arbre(T) → Arbre(T)

droit : () ↦ erreur !

droit : arbre(v, a1, a2) ↦ a2

Jacques Le Maitre I41 : Types de données 94

Page 95: Structures Donnees

Autres opérations

Nous en étudierons 4 : test de feuille (racine d’un arbre binaire dont les deux sous-arbres

sont vides),

hauteur d’un arbre binaire,

construction d’un arbre binaire de recherche par insertion, dans un arbre binaire de recherche, d’une valeur relativement à une relation d’ordre donnée,

recherche d’une valeur dans un arbre binaire de recherche.

Jacques Le Maitre I41 : Types de données 95

Page 96: Structures Donnees

Notre représentation d’un arbre binaire

Un arbre binaire non vide de racine v est représenté par un nœud qui contient : la valeur v,

l’identifiant du sous-arbre gauche,

l’identifiant du sous-arbre droit.

Un nœud a un identifiant.

Un arbre binaire a un identifiant qui est : l’identifiant du nœud qui contient sa racine, si cet arbre n’est pas

vide,

l’identifiant nul, si cet arbre est vide (on peut voir l’identifiant nul comme celui d’un nœud factice de contenu vide).

Jacques Le Maitre I41 : Types de données 96

Page 97: Structures Donnees

Représentation d’un arbre binaire

Jacques Le Maitre I41 : Types de données 97

v1

v2

v3 v4

valeur

arbre vide

nœud

feuille

Page 98: Structures Donnees

cons-arbre-vide

Jacques Le Maitre I41 : Types de données 98

cons_arbre_vide()

nul

Page 99: Structures Donnees

cons-arbre

Jacques Le Maitre I41 : Types de données 99

cons_arbre(v, a1, a2)

a1 a2

v

Page 100: Structures Donnees

arbre-vide

Jacques Le Maitre I41 : Types de données 100

arbre_vide(a) faux

arbre_vide(a) vrai

v a

a

Page 101: Structures Donnees

racine

Jacques Le Maitre I41 : Types de données 101

v racine(a)

v a

Page 102: Structures Donnees

gauche

Jacques Le Maitre I41 : Types de données 102

g gauche(a) g

a

Page 103: Structures Donnees

droit

Jacques Le Maitre I41 : Types de données 103

d droit(a) d

a

Page 104: Structures Donnees

feuille

Jacques Le Maitre I41 : Types de données 104

Une feuille est la racine d’un arbre binaire dont le sous-arbre gauche et le sous-arbre droit sont vides.

feuille(a1)

feuille(a2)

faux

vrai

a1

a2

Page 105: Structures Donnees

hauteur-arbre

Jacques Le Maitre I41 : Types de données 105

La hauteur d’un arbre binaire est égale à 0 s’il est vide ou au nombre de nœuds − 1 de sa plus longue branche sinon. On a : • hauteur(a) = 0, si a est

vide ou si la racine de a est une feuille,

• hauteur(a) = 1 + max(hauteur(g), hauteur(d)), si a est un arbre non vide de sous-arbre gauche g et de sous-arbre droit d.

hauteur_arbre(a) 1

hauteur_arbre(a) 0

hauteur_arbre(a) 0

a

a

a

Page 106: Structures Donnees

Parcours préfixe d’un arbre binaire

Jacques Le Maitre I41 : Types de données 106

2

1

3

4 5

Parcours préfixe racine

sous-arbre gauche sous-arbre droit

parcours-préfixe(a) = •si ¬arbre-vide(a) alors • traiter racine(a) • parcours-préfixe(gauche(a)) • parcours-préfixe(droit(a))

Page 107: Structures Donnees

Parcours infixe d’un arbre binaire

Jacques Le Maitre I41 : Types de données 107

1

2

4

3 5

Parcours infixe sous-arbre gauche

racine sous-arbre droit

parcours-infixe(a) = •si ¬arbre-vide(a) alors • parcours-infixe(gauche(a)) • traiter racine(a) • parcours-infixe(droit(a))

Page 108: Structures Donnees

Parcours postfixe d’un arbre binaire

Jacques Le Maitre I41 : Types de données 108

1

5

4

2 3

Parcours postfixe sous-arbre gauche

sous-arbre droit racine

parcours-postfixe(a) = •si ¬arbre-vide(a) alors • parcours-postfixe(gauche(a)) • parcours-postfixe(droit(a)) • traiter racine(a)

Page 109: Structures Donnees

Parcours en largeur d’un arbre binaire

Jacques Le Maitre I41 : Types de données 109

Parcours en largeur niveau par niveau

1

2 3

6 7 4 5

parcours-en-largeur(a) = •si ¬arbre-vide(a) alors •f = file-vide •entrer(f, a) •faire

• a = sortir(f) • traiter racine(a) • g = gauche(a) • d = droit(a) • si ¬arbre-vide(g) alors • entrer(f, g) • si ¬arbre-vide(d) alors • entrer(f, d) jusqu’à file-vide(f)

Page 110: Structures Donnees

Modification d’un arbre binaire

On notera qu’il n’y a pas de primitives d’insertion ou de suppression de sous-arbres, ou bien de remplacement de la valeur de la racine, comme c’est le cas pour les maillons d’une liste linéaire : Il n’est donc pas possible de modifier une arbre « en place » .

La solution est de construire, à partir de l’arbre à modifier, un nouvel arbre comportant qui peut partager des sous-arbres avec l'arbre initial.

Jacques Le Maitre I41 : Types de données 110

Page 111: Structures Donnees

Modification par reconstruction

Jacques Le Maitre I41 : Types de données 111

cons_arbre(racine(a), gauche(a), cons_arbre(racine(droit(a)), droit(droit(a)), arbre_vide()));

v4 v5

v1 a

v3 v2 a’ v3

v1 nouvel arbre

partage de sous-arbre

partage de sous-arbre

Page 112: Structures Donnees

Arbres binaires de recherche

Un arbre binaire de recherche est un arbre binaire dans lequel les valeurs sont placées relativement à une relation d’ordre ≼ , de la façon suivante.

Pour tout sous-arbre de racine r : les valeurs contenues dans le sous-arbre

gauche, sont les valeurs v telles que v ≼ r,

les valeurs contenues dans le sous-arbre droit sont les valeurs v telles que v ≻ r.

La recherche d’une valeur ne nécessite que le parcours de la branche à laquelle appartient cette valeur.

Jacques Le Maitre I41 : Types de données 112

22

56

29 75

≼ est la relation ≤ sur les entiers

Page 113: Structures Donnees

Insertion et recherche d’une valeur dans un arbre binaire de recherche L’insertion et la recherche d’une valeur dans un arbre binaire de

recherche sont réalisées par les fonctions cons-arbre-recherche et chercher. Dans le cas général, les valeurs de l’arbre sont structurées et sont

ordonnées par rapport à la valeur de l’une de leurs composantes que nous appellerons la clé. Par exemple, le nom ou l’âge d’une personne.

Lorsque les valeurs de l’arbre sont atomiques, des nombres par exemple, la clé est égale à la valeur elle-même.

Soit T le type des valeurs de l’arbre binaire de recherche et K celui de leurs clés.

En insertion, il faudra fournir une fonction de comparaison de deux valeurs, définie de la façon suivante : compvv : T T → {−1, 0, 1} compvv : (v1, v2) ↦ −1 si clé(v1) ≺ clé(v2), 0 si clé(v1) = clé(v2), 1 si clé(v1) ≻ clé(v2)

En recherche, il faudra fournir une fonction de comparaison d’une clé et d’une valeur, définie de la façon suivante : compkv : K T → {−1, 0, 1} compkv : (k, v) ↦ −1 si k ≺ clé(v), 0 si k = clé(v), 1 si k ≻ clé(v)

Jacques Le Maitre I41 : Types de données 113

Page 114: Structures Donnees

cons-arbre-recherche (1)

cons-arbre-recherche : Arbre(T) T (T T → {−1, 0, 1}) → Arbre(T)

cons-arbre-recherche (a, v, compvv) =

si arbre-vide(a) alors

cons-arbre(v, cons-arbre-vide(), cons-arbre-vide())

sinon

soit a = (r, g, d) dans

si compvv(v, r) ≤ 0 alors

cons-arbre(r, cons-arbre-recherche(g, compvv, v), d)

sinon

cons_arbre(r, g, cons-arbre-recherche(d, compvv, v))

Jacques Le Maitre I41 : Types de données 114

Page 115: Structures Donnees

cons-arbre-recherche (2)

Jacques Le Maitre I41 : Types de données 115

Relation d’ordre : ≤ sur les entiers

cons-arbre-recherche (a, 22, compvv)

22

a

Page 116: Structures Donnees

cons-arbre-recherche (3)

Jacques Le Maitre I41 : Types de données 116

Relation d’ordre : ≤ sur les entiers

22

56

cons-arbre-recherche (a, 56, compvv)

22 a

Page 117: Structures Donnees

cons-arbre-recherche (4)

Jacques Le Maitre I41 : Types de données 117

Relation d’ordre : ≤ sur les entiers

56

22

56

29

cons-arbre-recherche (a, 29, compvv)

22 a

Page 118: Structures Donnees

cons-arbre-recherche (5)

Jacques Le Maitre I41 : Types de données 118

Relation d’ordre : ≤ sur les entiers

a 22

56

29 75

56

29

cons-arbre-recherche (a, 75, compvv)

22

Page 119: Structures Donnees

Parcours ordonné des valeurs d’un arbre binaire de recherche

Pour accéder aux valeurs d’un arbre binaire de recherche dans l’ordre selon lequel cet arbre a été construit, il suffit de parcourir l’arbre en ordre « infixe ».

Jacques Le Maitre I41 : Types de données 119

t

y p

e s

e p t s y

1

2

3

5

4

(ordre alphabétique)

Page 120: Structures Donnees

chercher (1)

chercher : Arbre(T) K (K T → {−1, 0, 1}) → Arbre(T)

chercher(a, k, compkv) =

si arbre_vide(a ) alors

a

sinon

soit a = (r, g, d) dans

si compkv (k, r) < 0 alors

chercher(g, k, compkv)

sinon

si compkv(k, r) = 0 alors

a

sinon

chercher(d, k, compkv)

Jacques Le Maitre I41 : Types de données 120

Page 121: Structures Donnees

chercher (2)

Si la recherche a réussi, la fonction chercher retourne le sous-arbre dont la racine a pour clé la clé recherchée.

Si cette clé n’est pas unique, il faudra relancer la recherche dans le sous-arbre gauche de ce sous-arbre

Si la recherche a échoué, la fonction chercher retourne un arbre vide.

Jacques Le Maitre I41 : Types de données 121

Page 122: Structures Donnees

chercher (3)

Jacques Le Maitre I41 : Types de données 122

Relation d’ordre : ≤ sur les entiers Relation d’ordre : ≤ sur les entiers

56

29 75

chercher(a, 29)

22 a

chercher(a’, 29) a’

Page 123: Structures Donnees

chercher (4)

Jacques Le Maitre I41 : Types de données 123

Relation d’ordre : ≤ sur les entiers

56

29 75

22

a

a’

chercher(a, 29) chercher(a’, 29)

Page 124: Structures Donnees

chercher (5)

Jacques Le Maitre I41 : Types de données 124

Relation d’ordre : ≤ sur les entiers

56

29 75

22

a

chercher(a, 29) a chercher(a, 29) chercher(a’, 29)

Page 125: Structures Donnees

chercher (6)

Jacques Le Maitre I41 : Types de données 125

Relation d’ordre : ≤ sur les entiers

56

29 75

22 a

chercher(a, 12) chercher(a’, 12)

a’

Page 126: Structures Donnees

chercher (7)

Jacques Le Maitre I41 : Types de données 126

Relation d’ordre : ≤ sur les entiers

56

29 75

22

a

chercher(a, 12) a (échec)

Page 127: Structures Donnees

Coût d’une recherche

Le coût d’une recherche peut-être mesuré en nombre de nœuds parcourus.

La recherche d’une valeur se fait le long d’une seule branche.

Le coût maximum est donc égal à h + 1, si h est la hauteur de l’arbre.

Si un arbre contient n nœuds : sa hauteur maximum est égale n − 1 lorsque l’arbre n’a qu’une seule

branche.

sa hauteur minimum est égale à log2(n + 1) −1 lorsque l’arbre est équilibré (toutes les branches ont la même longueur).

Le coût de recherche est donc compris entre n et log2(n + 1). En moyenne, il est logarithmique (𝒪(log n)).

Jacques Le Maitre I41 : Types de données 127

Page 128: Structures Donnees

Représentation d'un arbre binaire en C

Jacques Le Maitre I41 : Types de données 128

(v1, arbre(v2, arbre(), arbre(v4, arbre(), arbre)), arbre(v3, arbre(), arbre()))

typedef struct noeud *Arbre;

struct noeud

{

void *valeur;

Arbre gauche;

Arbre droit;

};

struct noeud

{

valeur

gauche

droit

}

v1

NULL

NULL

struct noeud

{

valeur

gauche

droit

}

NULL

struct noeud

{

valeur

gauche

droit

}

NULL

NULL

v2 v3

v4

struct noeud

{

valeur

gauche

droit

}

arbre()

NULL

Page 129: Structures Donnees

Interface

La déclaration du type Arbre ainsi que les déclarations

des fonctions de l’interface sont enregistrés dans le fichier TD-arbre-binaire.h.

Les définitions des fonctions de l’interface sont enregistrées dans le fichier TD-arbre-binaire.c.

Jacques Le Maitre I41 : Types de données 129

Page 130: Structures Donnees

Fichier TD-arbre-binaire.h (1)

#ifndef TD_ARBRE_BINAIRE

#define TD_ARBRE_BINAIRE

#include <stdlib.h>

#include <stddef.h>

#include "erreur.h"

typedef struct noeud *Arbre;

struct noeud

{

void *valeur;

Arbre gauche;

Arbre droit;

};

Jacques Le Maitre I41 : Types de données 130

Page 131: Structures Donnees

Fichier TD-arbre-binaire.h (2)

Arbre cons_arbre_vide(void);

Arbre cons_arbre(void *v, Arbre g, Arbre d);

void *racine(Arbre a);

Arbre gauche(Arbre a);

Arbre droit(Arbre a);

int arbre_vide(Arbre a);

int feuille(Arbre a);

int hauteur_arbre(Arbre a);

Arbre cons_arbre_recherche(Arbre a, void *v, int (*comp)(const

void *, const void *));

Arbre chercher(Arbre a, void *cle, int (*comp)(const void *,

const void *));

#endif

Jacques Le Maitre I41 : Types de données 131

Primitives

Page 132: Structures Donnees

Construire un arbre binaire vide

Arbre cons_arbre_vide(void)

{

return NULL;

}

Jacques Le Maitre I41 : Types de données 132

Page 133: Structures Donnees

Construire un arbre binaire de racine r, de sous-arbre gauche g et de sous-arbre droit d

Arbre cons_arbre(void *v, Arbre g, Arbre d)

{

Arbre a;

a = (Arbre) malloc(sizeof(struct noeud));

if (a == NULL)

erreur("cons_arbre");

a->valeur = v;

a->gauche = g;

a->droit = d;

return a;

}

Jacques Le Maitre I41 : Types de données 133

Page 134: Structures Donnees

L’arbre binaire a est-il vide ?

int arbre_vide(Arbre a)

{

return a == NULL;

}

Jacques Le Maitre I41 : Types de données 134

Page 135: Structures Donnees

Racine d’un arbre binaire a

void *racine(Arbre a)

{

if (arbre_vide(a))

erreur("racine");

return a->valeur;

}

Jacques Le Maitre I41 : Types de données 135

Page 136: Structures Donnees

Sous-arbre gauche de la racine d’un arbre binaire a

Arbre gauche(Arbre a)

{

if (arbre_vide(a))

erreur("gauche");

return a->gauche;

}

Jacques Le Maitre I41 : Types de données 136

Page 137: Structures Donnees

Sous-arbre droit de la racine d’un arbre binaire a

Arbre droit(Arbre a)

{

if (arbre_vide(a))

erreur("droit");

return a->droit;

}

Jacques Le Maitre I41 : Types de données 137

Page 138: Structures Donnees

La racine de l’arbre binaire a est-elle une feuille ?

int feuille(Arbre a)

{

if (arbre_vide(a))

erreur("feuille");

return arbre_vide(gauche(a)) && arbre_vide(droit(a));

}

Jacques Le Maitre I41 : Types de données 138

Page 139: Structures Donnees

Hauteur de l’arbre binaire a

int hauteur_arbre(Arbre a)

{

int hg, hd;

if (arbre_vide(a) || feuille(a))

return 0;

hg = hauteur_arbre(gauche(a));

hd = hauteur_arbre(droit(a));

if (hg > hd)

return 1 + hg;

else

return 1 + hd;

}

Jacques Le Maitre I41 : Types de données 139

Page 140: Structures Donnees

Arbre cons_arbre_recherche(Arbre a, void *v,

int (*comp)(const void *, const void *))

{

void *r;

Arbre g, d;

if (arbre_vide(a))

return cons_arbre(v, NULL, NULL);

r = racine(a);

g = gauche(a);

d = droit(a);

if (comp(v, r) <= 0)

return cons_arbre(r, cons_arbre_recherche(g, v, comp), d);

else

return cons_arbre(r, g, cons_arbre_recherche(d, v, comp));

}

Construire un arbre binaire de recherche par insertion d’une valeur v dans un arbre binaire de recherche a en utilisant la fonction comp de comparaison de deux valeurs

Jacques Le Maitre I41 : Types de données 140

Page 141: Structures Donnees

Chercher une valeur de clé cle dans un arbre binaire de recherche a en utilisant la fonction comp de comparaison d’une clé et d’une valeur

Arbre chercher(Arbre a, void *cle,

int (*compvv)(const void *, const void *))

{

void *v;

int c;

if (arbre_vide(a))

return a;

c = comp(cle, racine(a));

if (c < 0)

return chercher(gauche(a), cle, comp);

if (c == 0)

return a;

return chercher(droit(a), cle, comp);

}

Jacques Le Maitre I41 : Types de données 141

Page 142: Structures Donnees

Autres opérations

Parcours d'un arbre binaire préfixe

infixe

suffixe

en largeur

Jacques Le Maitre I41 : Types de données 142

Page 143: Structures Donnees

Parcours préfixe d'un arbre binaire a

(racine – gauche – droit)

void parcours_prefixe(Arbre a)

{

if (!arbre_vide(a))

{

Traiter la valeur contenue dans la racine de l'arbre a

parcours_prefixe(gauche(a));

parcours_prefixe(droit(a));

}

}

Jacques Le Maitre I41 : Types de données 143

Page 144: Structures Donnees

Parcours infixe d'un arbre binaire a

(gauche – racine – droit)

void parcours_infixe(Arbre a)

{

if (!arbre_vide(a))

{

parcours_infixe(gauche(a));

Traiter la valeur contenue dans la racine de l'arbre a

parcours_infixe(droit(a));

}

}

Jacques Le Maitre I41 : Types de données 144

Page 145: Structures Donnees

Parcours suffixe d'un arbre binaire a

(gauche – droit - racine)

void parcours_suffixe(Arbre a)

{

if (!arbre_vide(a))

{

parcours_suffixe(gauche(a));

parcours_suffixe(droit(a));

Traiter la valeur contenue dans la racine de l'arbre a

}

}

Jacques Le Maitre I41 : Types de données 145

Page 146: Structures Donnees

Parcours en largeur d'un arbre binaire a

void parcours_en_largeur(Arbre a)

{

File f;

Arbre g, d;

if (!arbre_vide(a))

{

f = creer_file();

entrer(f, a);

do

{

a = arbre(sortir(f));

Traiter la valeur contenue dans la racine de l'arbre a g = gauche(a);

d = droit(a);

if (!arbre_vide(g))

entrer(f, g);

if (!arbre_vide(d))

entrer(f, d);

}

while (!file_vide(f));

}

}

Jacques Le Maitre I41 : Types de données 146