Structure de Données en C PDF

PLAN DU COURS  LISTES CHAÎNÉES  PILES ET FILES  ARBRES BINAIRES  GRAPHES 1  TYPES DE DONNEES EVOLUES RAPPEL STRUCTURES Une structure est un type défini par un identificateur et possédant, en son sein, un certain nombre de cha...

PLAN DU COURS  LISTES CHAÎNÉES  PILES ET FILES  ARBRES BINAIRES  GRAPHES 1  TYPES DE DONNEES EVOLUES RAPPEL STRUCTURES Une structure est un type défini par un identificateur et possédant, en son sein, un certain nombre de champs Le nom des champs répond aux critères des noms de variable Deux champs ne peuvent avoir le même nom Les données peuvent être de n'importe quel type hormis le type de la structure dans laquelle elles se trouvent struct Point_plan { typedef struct Point_plan { float x; float x; float y; float y; }; } Point; typedef struct Point_plan Point; 2  EXERCICE Ecrire le programme qui permet de : Saisir un tableau T d’entiers Transcrire T en un tableau Tab dont tous les éléments sont distincts et apparaissent dans l’ordre de leur première apparition au sein de T Afficher enfin le tableau généré Tab. T 9 1 9 9 9 1 1 2 2 Tab 9 4 1 3 2 2 ? ? ? ? ? ? 3  EXERCICE struct complexe A struct complexe{ Nombre complexe float a; float b; a b a+ib }; b=0 a=0 et b!=0 Nombres réels Nombres imaginaires purs Reste float float struct complexe{ float a; float B float C float b; }; 2 i*1 D struct complexe 0 2+i*3 1 2 3 Ecrire le programme qui permet de scinder le tableau A en B,C et D 4  RAPPEL RECHERCHE SÉQUENTIELLE Pour chercher une donnée ou éventuellement sa position dans un tableau non trié, la recherche doit se faire de manière séquentielle, c’est à dire en comparant la donnée avec les données successives de tout le tableau. i=0; while( isuiv=nouveau; } } P nouveau info Suiv Nouveau info Suiv x a=4 x NULL 1° 2° L p P 23  *nouveau.val nouveau—>val *nouveau.suiv nouveau—>suiv INSERTION Insertion au mileu void insermilieu(liste l,int a,int x) { liste nouveau,p=l; while(p!=NULL && p->val!=a) p=p->suiv; if (p!=NULL) {nouveau =(liste)malloc(sizeof(struct cellule)); nouveau->val=x; nouveau->suiv=p->suiv; p->suiv=nouveau; } } a=7 Nouveau info Suiv x NULL L p P 24  EXERCICES Création d’une liste Insertion à la fin 1 2 n struct cellule { int val ; struct listcell *suiv;} ; liste CREER_fin(int n){ typedef struct cellule *liste ; liste nouveau,l,dernier; l =(liste)malloc(sizeof(struct cellule)) ; int main(){ l ->val=1;l->suiv=NULL;dernier=l; Int n; for(i=2;ival=i; scanf(« %d »,&n); nouveau->suiv=NULL; //l=CREER_fin(n); dernier>suiv=nouveau; //affichageliste (l); } affichageliste (CREER_fin(n)); dernier=nouveau;} l return l ;} 1 2 NULL 3 4 nouveau 25 dernier  EXERCICES Création d’une liste struct cellule { int val ; struct listcell *suiv;} ; 1 2 n typedef struct cellule *liste ; Insertion en tête Insertion à la fin liste CREER_tete (int n) { liste CREER_fin(int n){ liste l=NULL, nouveau; liste nouveau,l,dernier; for(i=n;i>=1;i--) { l =(liste)malloc(sizeof(struct cellule)) ; nouveau = (liste)malloc(sizeof(struct cellule)) ; l ->val=1;l->suiv=NULL;dernier=l; nouveau->val=i; for(i=2;isuiv=l ; nouveau=malloc(sizeof(struct cellule)) ; l= nouveau; nouveau->val=i; } nouveau->suiv=NULL; return l;} dernier>suiv=nouveau; dernier=nouveau;} return l ;} l n-2 n-1 n NULL 26 nouveau  LES LISTES SUPPRESSION premier 27  LES LISTES SUPPRESSION Suppression en tête Suppression au milieu On supprime la cellule en tête On supprime la cellule après celle contenant a void supprimer_tete(liste *l){ void supprimer_milieu(liste l, int a){ liste p; liste p=l,q; if (*l!=NULL){ p=*l; while(p!=NULL && p->val!=a) p=p->suiv; *l=(*l)->suiv; if (p!=NULL && p->suiv!=NULL) { free(p);} q=p->suiv; } p->suiv=q->suiv; free(q);}} L q 1 a 3 2 NULL p 1 a NULL 28 L p  1 a NULL L q p L 1 a 3 2 NULL q p On supprime la cellule contenant a qui ne se trouve pas en tête de liste void supprimer_a(liste l, int a){ liste p=l,q; while(p!=NULL && p->val!=a) {q=p;p=p->suiv;} if (p!=NULL) {q->suiv = p->suiv; free(p);} 29  L a 1 3 2 NULL p q=NULL L 1 a 3 2 NULL q p On supprime la cellule contenant a 1 2 NULL p void supprimer_a(liste *l, int a){ L q liste p=*l,q=NULL; while(p!=NULL && p->val!=a) {q=p;p=p->suiv;} if (p!=NULL) {if(q!=NULL) q->suiv = p->suiv; else *l=(*l)->suiv; free(p); } } 30  EXERCICES Soit L une liste d’entiers simplement chainée  Ecrire la fonction qui permet de localiser la premiere occurrence d’un entier a  Ecrire la fonction qui permet de localiser la dernière occurrence d’un entier a  Ecrire la fonction qui permet de localiser la nième occurrence d’un entier a  Ecrire la fonction qui calcule le nombre de cellules dans une liste (version itérative et récursive)  Ecrire la fonction qui permet de transcrire les éléments d’un tableau, avec leurs nombres d’occurrence, dans une liste simplement chainée. 31  LES LISTES LISTE DOUBLEMENT CHAINEE l Le parcours d’une telle liste se fait dans les deux sens On peut déterminer instantanément les éléments précédant et suivant d’un élément struct cellule { struct cellule * preced; int info ; struct cellule * suiv; suiv }; info preced typedef struct cellule * liste ; liste l; Primitives : Localiser / Insérer / Supprimer  LES LISTES INSERTION Insertion en tête void insertete(liste *l, int a) { liste p; p = (liste)malloc(sizeof(struct cellule)); p->val=a; p->suiv=*l; p->preced=NULL; (*l)->preced = p; *l=p;} l 2  p P->suiv l preced 10 suiv void insermilieu(liste l,int a,int x) { nouveau liste p=l; while(p!=NULL && p->val!=a) p=p->suiv; If (p!=NULL) { nouveau = (liste)malloc(sizeof(struct cellule)); nouveau->val=x; nouveau->preced=p; if(p->suiv!=NULL) (p->suiv)->preced=nouveau; nouveau->suiv =p->suiv; p->suiv=nouveau;} p } NULL preced 20 suiv 3 nouveau  LES LISTES INSERTION Insertion au milieu void insermilieu(liste l,int a,int x) { liste p=l,nouveau; while(p!=NULL && p->val!=a) p=p->suiv; If (p!=NULL) { nouveau = (liste)malloc(sizeof(struct cellule)); nouveau->val=x; nouveau->preced=p; nouveau->suiv=p->suiv; if(p->suiv!=NULL) (p->suiv)->preced=nouveau; nouveau->suiv =p->suiv; p->suiv=nouveau;} } Insertion à la fin 4  LES LISTES SUPPRESSION Suppression en tête NULL 1 2 void supprimer_tete(liste *l){ liste p; if (*l!=NULL){ p=*l; *l=(*l)->suiv; (*l)->preced=NULL; free(p);} } 5  LES LISTES SUPPRESSION Suppression au milieu Suppression au milieu On supprime la cellule après celle contenant a void supprimer_milieu(liste l, int a){ a liste p1=l,p; while(p1!=NULL && p1->val!=a) p1=p1->suiv; p->suiv if (p1!=NULL && p1->suiv!=NULL) { p=p1->suiv; p1->suiv=p->suiv; if(p->suiv!=NULL) (p->suiv)->preced = p1; free(p); } } a P1 P Suppression à la fin 6  LES LISTES LISTE CIRCULAIRE OU ANNEAU Le dernier élément de la liste pointe sur le premier élément de celle-ci On peut atteindre tous les éléments de la chaîne depuis n’importe quel élément On peut la considérer comme n’ayant ni début ni fin L struct cellule { P int info ; struct cellule *suiv; }; typedef struct cellule *liste ; Primitives : Localiser / Insérer / Supprimer 7  LES LISTES p=l; Tant que(p!=NULL) LISTE CIRCULAIRE OU ANNEAU p=p->suiv void affichanneau(liste l) void affichageliste (liste l) {liste p=l; { if(p!=NULL) liste p=l; do {printf(« %d »,p->val); 12 while(p!=NULL) { p=p->suiv;}while(p!=l); 25 printf("%d \n", p->val); } 4 p=p->suiv; } 7 } 12 l 25. P. 12. 25 4 7 8  LES LISTES LISTE CIRCULAIRE OU ANNEAU void ajoutmilieu(liste l,int x,int a) void afficher(liste l) { liste nouveau, p=l; int ok=0; {liste p=l; if (l!=NULL) { if(p!=NULL) { nouveau = malloc(sizeof(struct cellule)); do(printf(« %d »,p->val); nouveau->val=x; p=p->suiv;}while(p!=l); do { if(p->val==a) { nouveau->suiv=p->suiv; } p->suiv=nouveau; } ok=1;} p=p->suiv; }while(p!=l && ok!=1); } } x l a 9  TP ETUDIANTS Enoncé Soit L une liste simplement chaînée d’étudiants. Chaque étudiant est connu par son CNE et les résultats de validation des semestre S1 et S2. A- Ecrire la structure de données correspondante B- Ecrire une fonction qui permet de calculer le nombre d’étudiants ayant validé les deux semestres S1 et S2 (version récursive et itérative) C- Ecrire une fonction qui permet de donner la liste des étudiants ayant validé uniquement le semestre S2. struct cellule { int CNE ; l int Sun ;// vaut 0 ou 1 int Sdeux ;// vaut 0 ou 1 struct cellule *suiv; CNE Sun Sdeux Suiv }; typedef struct cellule *liste ; liste l; 10  TP TRANSACTIONS BANCAIRES Enoncé On dispose d’une liste de transactions bancaires où chaque cellule contient l'émetteur, le destinataire et le montant de la transaction effectuée. A- Ecrire la fonction qui permet de créer la liste contenant chaque émetteur avec le montant global de toutes les transactions qu'il a effectuées. Exemple : si la liste de transactions est [1,2,30]->[2,6,30]->[1,5,10] alors la liste crée est [1,40]->[2,30] B- En déduire l’adresse d’une personne qui a émis le montant le plus important, toutes transactions confondues 11  TP TRANSACTIONS BANCAIRES Enoncé On dispose d’une liste de transactions bancaires où chaque cellule contient l'émetteur, le destinataire et le montant de la transaction effectuée. A- Ecrire la fonction qui permet de créer la liste contenant chaque émetteur avec le montant global de toutes les transactions qu'il a effectuées. Exemple : si la liste de transactions est [1,2,30]->[2,6,30]->[1,5,10] alors la liste crée est [1,40]->[2,30] B- En déduire l’adresse d’une personne qui a émis le montant le plus important, toutes transactions confondues 12  TP LIGNES DE TRANSPORT 1 100 15 NULL Enoncé BUS On dispose d’un ensemble de lignes de transport public avec les stations desservies par ces autobus. Une station peut être desservie par plusieurs autobus à la fois. Faire la déclaration de la structure de données correspondante Une nouvelle station est ouverte au public, elle est desservie par les lignes contenues dans la liste pointée par BUS. Ecrire la procédure correspondante Ecrire la fonction qui donne la liste des autobus desservant une station donnée « STAT » Suite à des travaux, une station est temporairement fermée au public. Ecrire la procédure correspondante Une station est fermée définitivement au public. Ecrire la procédure correspondante 13  TP FAMILLE Enoncé On considère une population composée de familles toutes distinctes. On suppose que chaque famille est composée de 0, 1 ou deux parents et de 0, un ou plusieurs enfants stockés par ordre décroissant sur l’âge Faire la déclaration relative à une telle structure Ecrire une procédure déclarant une naissance chez une famille donnée Ecrire une fonction récursive qui donne le nombre de familles dont les parents sont tous les deux en vie 14  LES PILES INTRODUCTION Une pile (stack en anglais) est une liste dans laquelle l’insertion ou la suppression se fait toujours à partir de la même extrémité appelée sommet de la pile. Une pile permet de modéliser un ensemble régi par la discipline ‘dernier arrivé premier sorti’  LIFO : Last In First Out 1  LES PILES CARACTERISTIQUES GENERALES Ensemble de données dans lequel on a la possibilité de demander : * ensemble vide ? * éventuellement ensemble plein ? On peut faire dans cet ensemble : * Ajouter un élément (empiler) * Retirer le 1er élément (dépiler) * Donner l’élément qui se trouve au sommet * Eventuellement, vider la pile 2  LES PILES UTILISATION Exemples: Seules actions possibles : Pile courante L’Ajout d’un élément au sommet Pile informatique Le Retrait d’un élément au sommet Opérations effectuées sur les piles : vider(p) : vide le contenu de la pile P Premier(P) : retourne (sans le dépiler) l’élément au sommet de P Dépiler(P) : supprime physiquement l’élément au sommet de P Empiler(x,P) : insère l’élément x au sommet de P Pile-vide(P) : fonction qui teste si P est vide Pile_pleine(P): teste si la pile P est pleine ou non 3  LES PILES IMPLEMENTATIONS Implémentation dynamique par une liste chaînée Une pile en dynamique n'a pas de taille limite, hormis celle de la mémoire centrale (RAM) disponible. Implémentation statique sous forme de tableau 4  pointp LES PILES max-1 Implémentation sous forme de tableau #define max …. struct pile{typelt tab[max] ; int pointp;}; // pointeur de pile indice du sommet de la pile Typedef struct pile * ppile; int vide(ppile p) pointp+1 {return(p->pointp == -1);} void empiler(typelt x,ppile p) { if(p->pointptab[p->pointp+1]=x; p->pointp= p->pointp+1;} } void depiler(ppile p) { if(!vide(p)) p->pointp= p->pointp-1;} typelt sommet(ppile p) { return (p->tab[p->point]) ;} 5  LES PILES Implémentation sous forme liste chaînée 1 2 3 NULL struct element { int val; p p struct element *suiv;} ; q typedef struct element *pile; int sommet(pile p) { return(p->val);} void empiler(int x,pile *p) {pile nouveau; int depiler(pile *p) nouveau=(pile)malloc(sizeof(struct element)); {int som; nouveau->val=x; pile q; nouveau->suiv=*p; q=*p; *p=nouveau; som = (*p)->val; } *p = (*p)->suiv; free(q); 1 2 3 return(som); int pilevide(pile p) } {return(p==NULL);} x 1 2 3 NULL nouveau p 6 p  LES FILES REPRESENTATION INTUITIVE Type particulier de liste où les éléments sont insérés en queue et supprimés en tête. Le nom vient des files d’attente à un guichet où « le premier arrivé » est « le premier parti » : ce qui justifie le terme anglo-saxon « FIFO List » 7  LES FILES OPERATIONS SUR LES FILES Exemples : Gestion d’accès à une ressource informatique : en système les files sont utilisées pour gérer tous les processus en attente de ressource système D'une façon générale, la notion de file intervient dans un modèle dès qu'il est question d'une file d'attente : systèmes de réservation, gestion de pistes d'aéroport ……etc. Opérations : Tete(F) : retourne l’élément en tête de F Queue(F) : retourne l’élément en fin de F Enfiler(x,F) : insère l’élément x à la fin de la file F Defiler(F) : supprime le premier élément de la file F 8  LES FILES MISE EN ŒUVRE DES FILES PAR POINTEURS Une file est une liste dont on conserve en permanence le premier élément qui représente la tête de la file et le dernier élément qui représente la queue de la file. Elle est définie par deux pointeurs : dernier : pointeur sur la queue pour enfiler les éléments premier : pointeur sur la tête pour défiler les éléments A part cette spécificité c'est un cas normal de liste chainée En dynamique une file n'a pas de taille limite, hormis celle de la mémoire centrale (RAM) disponible. 9  LES FILES MISE EN ŒUVRE DES FILES PAR POINTEURS struct elem{ typelt val ; int filevide(pfile f ) struct elem *suiv;}; void enfiler(pfile f , pelem x) Typedef struct elem * pelem; pelem liretete(pfile f) pelem lirequeue (pfile f) Val struct file{ pelem defiler(pfile f) pelem premier; // sortie pelem dernier; // entrée }; Typedef struct file * pfile; tete Queue premier Dernier int filevide(pfile f) {return f->dernier==NULL;} 1 10  LES FILES IMPLEMENTATION PAR POINTEURS Enfiler un nouvel élément consiste à effectuer les opérations suivantes : le suivant du dernier devient le nouveau le dernier devient le nouveau. Si la file est vide alors premier et dernier prennent la valeur du nouvel élément void enfiler(pfile f, pelem x) { 1 if (filevide(f)) {f->dernier=x; f->premier=x;} a else { f->dernier->suiv=x; f->dernier=x;} x } pelem creer(int a) { x =(pelem)malloc(sizeof(struct elem)) ; x ->val=a ; x->suiv=NULL; return x;} 11  LES FILES IMPLEMENTATION PAR POINTEURS pelem liretete(pfile f) { pelem lirequeue(pfile f) pelem q=NULL; { if (!filevide(f)) pelem q=NULL; q=f->premier; if (!filevide(f)) return q; q=f->dernier; } return q; } premier 1 dernier a 12  LES FILES IMPLEMENTATION PAR POINTEURS Défiler : consiste à retourner l'adresse de l’élément sortant et passer la tête au suivant. premier 1 Deux cas sont à envisager : dernier ▪file avec un seul élément : on retourne son adresse et on met premier et dernier à NULL. file avec plusieurs éléments : on retourne l'adresse du premier et le premier prend l'adresse du suivant premier 1 dernier a 13  LES FILES IMPLEMENTATION PAR POINTEURS Défiler : consiste à retourner l'adresse pelem defiler(pfile f) de l’élément sortant et passer la tête { pelem q=NULL; if(!filevide(f)){ au suivant. // si file non vide retirer en tête Deux cas sont à envisager : if (f->premier==f->dernier){ // si un seul élément ▪file avec un seul élément : on retourne q=f->premier; son adresse et on met premier et f->premier=NULL; f->dernier=NULL; dernier à NULL. } file avec plusieurs éléments : on else{ // si plusieurs q=f->premier; retourne l'adresse du premier et le f->premier=f->premier->suiv;} premier prend l'adresse du suivant } return q; } 14  LES FILES IMPLEMENTATION PAR UN TABLEAU premier : indice pour la tête de la file dernier : indice pour la queue de la file un tableau d’éléments de taille Nbmax Déclaration : #define Nbmax …. struct file { int premier,dernier; typelt Tab[Nbmax]; } typedef struct file *pfile; Les données se trouvent entre ‘premier’ et ‘dernier’ 15  LES FILES IMPLEMENTATION PAR UN TABLEAU (TABLEAU SIMPLE) Tete Queue ( (5) ( ( (6) (7) on ne peut plus ajouter des éléments dans la file alors qu’elle n’est pas pleine 16  LES FILES IMPLEMENTATION PAR TABLEAU (TABLEAU SIMPLE AVEC DECALAGE) 20 ( (5) ( ( (6) (7) On doit décaler les éléments de la file après chaque suppression d’où un décalage très coûteux si la file contient beaucoup d’éléments 17  LES FILES IMPLEMENTATION PAR UN TABLEAU (TABLEAU CIRCULAIRE) Gestion du tableau de manière cyclique les nouveaux éléments entrants peuvent être placés au début ou à la fin selon la place restante dans le tableau les indices de la tête et de la queue progressent maintenant modulo la taille du tableau. 18  LES FILES IMPLEMENTATION PAR UN TABLEAU la file est pleine lorsque la tête et la queue coïncident ce qui représente la même condition quand la file est vide : il est clair que cette situation n’est pas satisfaisante. une solution consiste à laisser au moins l’espace d’un élément entre la tête et la queue : si la taille de la file est de 100 par exemple, il faudra réserver un tableau à 101 éléments. Le champ dernier (par exemple) correspond à la position libre suivante pour le prochain arrivant la file est pleine si le dernier élément retrouve le premier dans le tableau circulaire après un tour complet en partant de n'importe quelle position 19  LES FILES IMPLEMENTATION PAR UN TABLEAU int file_vide(pfile f) typelt defiler(pfile f) int file_pleine(pfile f) void enfiler(pfile f , typelt e) int file_vide(pfile f) { return f->dernier==f->premier; } int file_pleine(pfile f) { return ((f->dernier+1)%Nbmax == f->premier) ; } 20  LES FILES IMPLEMENTATION PAR UN TABLEAU void enfiler(pfile f,typelt x) { if (!file_pleine(f)){ f->tab[f->dernier]=x; f->dernier =(f->dernier+1)%Nbmax; } } typelt defiler(pfile f) { typelt x; x=f->tab[f->premier]; f->premier=(f->premier+1)%Nbmax; return x; } 21  LES ARBRES GENERALITES Les listes sont des structures dynamiques unidimensionnelles. Les arbres sont leur généralisation multidimensionnelle. Comme pour le premier d’une liste, l’adresse de la racine est nécessaire et suffisante pour accéder à l’intégralité d’un arbre. 22  N LES ARBRES N1 Nk A1 Ak DEFINITION Un arbre peut se définir de manière récursive : un sommet unique, par lui même, est un arbre. Dans ce cas, il est aussi la racine de l’arbre si n est un sommet et A1, A2, … , Ak sont des arbres de racines respectives n1, n2, … , nk ; on peut construire un nouvel arbre en associant comme parent unique aux sommets n1, n2, … , nk le sommet n. Dans cet arbre, n est la racine et A1, A2, … , Ak sont les ss-arbres. Les sommets n1, n2, … , nk sont appelés les fils de n. 23  LES ARBRES TERMINOLOGIE On utilise un vocabulaire inspiré des arbres généalogiques. Chaque composante d’un arbre contient une valeur, et des liens vers ses fils. Chaque élément d’un arbre se nomme un nœud. Le nœud racine est le seul qui n’est le fils d’aucun nœud. Un nœud qui n’a pas de fils est un noeud externe ou feuille Un nœud qui n’est pas une feuille est dit interne. 24  LES ARBRES TERMINOLOGIE Chemin: suite unique de sommets Longueur d’un chemin : nombre d’arcs intervenant dans ce chemin La hauteur d’un noeud s : la longueur du plus long chemin issu de s La profondeur d’un noeud s : longueur du chemin racine  s. La hauteur de l’arbre : la profondeur maximale de ses nœuds. Etant donné un sommet u, tous les sommets, autres que lui même, situés sur le chemin de la racine à u sont appelés des ancêtres, le dernier étant son père. Deux sommets qui ont le même père sont des frères 25  LES ARBRES TERMINOLOGIE 4-aire Taille=10 Arité d’un arbre Un arbre dont les nœuds ne comportent qu’au maximum n fils est un arbre d’arité n. On parle alors d’un arbre n-aire. Un arbre d’arité 2 est un arbre binaire. On parle alors de fils gauche et de fils droit. Taille d’un arbre : La taille d’un arbre est le nombre de nœuds qui le composent 26  ARBRES BINAIRES DEFINITION ET IMPLEMENTATION Un arbre binaire est soit un arbre vide, soit un arbre où chaque sommet a un fils gauche, un fils droit ou les deux fils à la fois. struct nœud { typelt info ; struct nœud *fg ; struct nœud *fd ;} ; typedef struct nœud *arbre ; 27  LES ARBRES BINAIRES PARCOURS Parcours en largeur On parcourt tous les sommets de l’arbre binaire par niveau de profondeur. On commence par la racine, puis tous les sommets (de gauche à droite) de profondeur 1 , puis tous les sommets de profondeur 2 , etc. Parcours en profondeur racine On parcourt récursivement le sous-arbre gauche puis le sous-arbre droit. La visite de la racine se fait : Avant les appels récursifs pour un parcours préfixé. Entre les deux appels récursifs pour un parcours infixé. Après les appels récursifs pour un parcours postfixé. 28  ARBRES BINAIRES PARCOURS Soit un arbre binaire de racine n et de ss-arbres A1 et A2 Parcours préfixé : on commence par la racine n puis on entreprend le parcours préfixé des sommets de A1, puis de A2 void prefixe(arbre r) { if(r!=NULL){ traiter( r ) ; prefixe(r->fg); prefixe(r->fd); } } 29  ARBRES BINAIRES PARCOURS Parcours préfixé : void prefixe(arbre r) R { prefixe(A) A if(r!=NULL){ prefixe(B) B traiter( r ) ; prefixe(NULL) prefixe(NULL) prefixe(r->fg); prefixe(C) C prefixe(r->fd); prefixe(NULL) } prefixe(D) D prefixe(NULL) } prefixe(NULL) prefixe(E) E prefixe(NULL) prefixe(NULL) Parcours préfixé : R-A-B-C-D-E 30  ARBRES BINAIRES PARCOURS Parcours infixé : on commence par le parcours infixé des sommets de A1, on passe par la racine n, puis on termine par le parcours infixé des nœuds de A2 void infixe(arbre r) { if(r!=NULL){ infixe(r->fg); traiter(r->info); infixe(r->fd); } } 31  ARBRES BINAIRES PARCOURS Parcours infixé : BACRDE void infixe(arbre r) { infixe(B) infixe(NULL) if(r!=NULL){ infixe(A) B infixe(NULL) infixe(r->fg); A traiter(r->info); infixe(C) infixe(NULL) C infixe(r->fd); R infixe(NULL) } infixe(D) infixe(NULL) D } infixe(E) infixe(NULL) E infixe(NULL) Parcours infixé : B-A-C-R-D-E 32  ARBRES BINAIRES PARCOURS Parcours postfixé : on effectue le parcours postfixé des nœuds de A1, de A2, et l’on termine par la racine void postfixe(arbre r) { if(r!=NULL){ postfixe(r->fg); postfixe(r->fd); traiter(r->info); } } 5 8 6 18 15 12 33  ARBRES BINAIRES PARCOURS Parcours postfixé : BCAEDR void postfixe(arbre r) postfixe(A) postfixe(B) postfixe(NULL) postfixe(NULL) { B postfixe(C) postfixe(NULL) if(r!=NULL){ postfixe(NULL) C postfixe(r->fg); A postfixe(r->fd); postfixe(D) postfixe(NULL) postfixe(E) traiter(r->info); postfixe(NULL) postfixe(NULL) } E D R } Parcours postfixé : B-C-A-E-D-R 34 EXERCICES DE PARCOURS Largeur : 1 2 3 4 5 6 7 8 9 Préfixé : 1 2 4 5 7 8 3 6 9 Postfixé : 4 7 8 5 2 9 6 3 1 Infixé : 4 2 7 5 8 1 3 9 6 Infixe : 9 18 25 26 28 29 30 41 48 52 60 Postfixe : 9 18 28 26 29 25 48 60 52 41 30 Prefixe : 30 25 18 9 29 26 28 41 52 48 60 Largeur : 30 25 41 18 29 52 9 26 48 60 28 35 EXERCICES DE PARCOURS  ARBRES BINAIRES Nombre d’arbres binaires à n noeuds 37  ARBRES BINAIRES Nombre d’arbres binaires à n noeuds Soit Cn , dit nième nombre de Catalan, le nombre d’arbres binaires à n nœuds. On a C0 =1. Soit n>0.Un noeud est la racine. Il reste à placer les n-1 nœuds restants dans le ss-arbre gauche et dans le ss-arbre droit, de toutes les façons possibles. *Soit on ne place aucun noeud à gauche : ce qui fait C0=1 façon, et n-1 noeuds dans le ss-arbre droit, avec Cn-1 possibilités. C0 Cn-1 cas *Soit on place un noeud à gauche, et n-2 noeuds à droite C1 Cn-2 cas. Plus généralement , on place k noeuds à gauche Ck sous-arbres gauches et n-1-k noeuds à droite, d’où Cn-1-k sous-arbres droits Ck Cn-1-k cas 38  ARBRE BINAIRE Nombre d’arbres binaires à n noeuds Finalement le nombre Cn vérifie la récurrence : C0=1 et Cn = C0 C n-1 + C 1 C n-2 + … + C k C n-1-k + … + C n-1 C 0 Donc : Cn 39  ARBRES BINAIRES QUELQUES ARBRES BINAIRES PARTICULIERS Un arbre dégénéré est un arbre dont les noeuds ne possèdent qu'un et un seul fils. Cet arbre est donc tout simplement une liste chaînée. Ce type d'arbre est à éviter puisqu'il n'apportera aucun avantage par rapport à une liste chaînée simple. Arbre binaire localement complet est un arbre binaire où chaque noeud possède soit 0 soit 2 fils. Arbre binaire complet est un arbre localement complet et dont toutes les feuilles ont la même profondeur. 40  Arbre binaire complet Arbre binaire localement complet Arbre binaire localement complet est un arbre binaire où chaque noeud possède soit 0 soit 2 fils. Arbre binaire complet est un arbre localement complet et dont toutes les feuilles ont la même profondeur.  ARBRES BINAIRES ARBRE BINAIRE COMPLET Rappel : La profondeur d’un noeud s : longueur du chemin r s. La hauteur de l’arbre : la profondeur maximale de ses nœuds Propriété : Soit G un arbre binaire complet d’ordre n , de hauteur h et soit f son nombre de feuilles. On a : n=2h+1−1 f=2h Remarque : Dans un arbre binaire complet, le nombre de noeuds internes est : n-f = 2h+1−1- 2h = 2* 2h − 1- 2h = 2h −1 racine Le nombre total de noeuds n= 23 -1= 8-1=7 Le nombre de noeuds internes : 22 −1=3 Le nombre de feuilles : 22 = 4 42  ARBRES BINAIRES ARBRE BINAIRE COMPLET  ARBRE BINAIRE 10 Hauteur d’un arbre binaire à n noeuds 20 Soit un arbre binaire non vide à n noeuds de hauteur h. On a : 30 h+1 ≤ n ≤ 2h+1−1 40 La borne supérieure est atteinte pour un arbre complet la borne inférieure est atteinte pour un arbre dégénéré ou filiforme log2(n+1) -1 ≤ h ≤ n − 1  ARBRE BINAIRE Hauteur d’un arbre binaire à n noeuds Soit un arbre binaire non vide à n noeuds de hauteur h. On a : h+1 ≤ n ≤ 2h+1−1 n ≤ 2h+1−1 n +1 ≤ 2h+1 log2(n+1) ≤ log2(2h+1) log2(n+1) ≤ h+1 log2(n+1) -1 ≤ h h+1 ≤ n h ≤ n -1 log2(n+1) -1 ≤ h ≤ n − 1  ARBRE BINAIRE DE RECHERCHE DÉFINITION Un arbre binaire de recherche est un arbre étiqueté tel que pour tout sommet x de l’arbre : les éléments de tous les sommets du ss-arbre gauche de x sont inférieurs ou égaux à l’élément contenu dans x les éléments de tous les sommets du ss-arbre droit de x sont supérieurs à l’élément contenu dans x 46  ARBRE BINAIRE DE RECHERCHE EXEMPLE 20 10 30 10 20 10 30 10 20 30 20 N.B: Le parcours infixé d’un arbre binaire de recherche produit la suite 30 des éléments triée par ordre croissant 47  ARBRE BINAIRE DE RECHERCHE INSERTION L’adjonction du nœud est effectuée de telle manière à ce que l’arbre reste binaire de recherche + 17 17 48  ARBRE BINAIRE DE RECHERCHE SUPPRESSION On désire supprimer le nœud s d’étiquette x Trois cas sont à considérer selon le nombre de fils du nœud x: 1er cas : le noeud s est une feuille 2ème cas : le nœud s possède un seul fils Fg Fd 2ème cas : le nœud s possède deux fils fg Fd 49  ARBRE BINAIRE DE RECHERCHE SUPPRESSION On désire supprimer le nœud s d’étiquette x Trois cas sont à considérer selon le nombre de fils du nœud x: 1er cas : si le noeud s est une feuille, alors on l’élimine 50  ARBRES BINAIRES DE RECHERCHE SUPPRESSION 2ème cas : si le nœud s possède un seul fils, on élimine s et on« remonte » ce fils. 51 ARBRES BINAIRES DE RECHERCHE SUPPRESSION 52  ARBRE BINAIRE DE RECHERCHE SUPPRESSION 3ème cas : si le nœud s possède deux fils, Pour conserver l’ordre sur les clés, il n’y a que deux choix : la clé du prédécesseur dans l’ordre infixé, ou la clé du successeur. 53 ARBRE BINAIRE DE RECHERCHE prédécesseur Successeur  ARBRE BINAIRE DE RECHERCHE TRI AVEC UN ABR  ARBRE BINAIRE DE RECHERCHE EXEMPLE DE TRI 20 15 10 35 19 13 5 3 12 7 16 40 25 38 3 5 7 10 12 13 15 16 19 20 25 35 38 40 ARBRE BINAIRE int nbresommets(arbre A) { if(A==NULL) return 0; else if (A->fg==NULL && A->fd ==NULL) return 1; else return(1+nbresommets(A->fg)+nbresommets(A->fd)); } int nbfeuilles (arbre racine) { vide if(racine==NULL) return 0; else if(racine->fg==NULL && racine->fd==NULL) return 1; else return(nbfeuilles(racine->fg)+nbfeuilles(racine->fd)); }  vide int max (int a,int b) { return (a>b ? a: b); } int hauteur (arbre racine) { if (racine == NULL) return 0; if (racine->fg == NULL && racine->fd==NULL) return 0; else return(1+ max(hauteur(racine->fg),hauteur(racine->fd))); } int rechercher(arbre racine,int n) { if (racine==NULL) {//printf("\nvaleur inexistante"); return 0; } if (racine->val == n){ //printf("\nla valeur existe"); return 1; } if (racine->val < n) return(rechercher(racine->fd,n)); if (racine->val > n) return(rechercher(racine->fg,n)); } void inserer_val(arbre *r,int n) { arbre N; if(*r==NULL){ N =(arbre)malloc(sizeof(struct sommet)); N->fg=NULL; N->val=n; N->fd=NULL; *r=N; } else if(n>(*r)->val) inserer_val(&(*r)->fd,n); else inserer_val(&(*r)->fg,n); }  racine =NULL; void infixe (arbre racine) do{ printf("saisir une valeur : "); { if (racine!=NULL) { scanf("%d",&x); infixe (racine->fg); inserer_val(&racine,x); printf("Noeud = %d\n",racine->val); }while (x!=0); infixe(racine->fd); } } infixe(racine); int maximum(arbre racine) 10 { int valmax; if (racine->fd==NULL) { 5 valmax=racine->val; return(valmax); 3 7 } else return(maximum(racine->fd)); } 1 4 6 9 int minimum(arbre racine) { int valmin; if (racine->fg==NULL) { valmin=racine->val; return(valmin); } else return(minimum(racine->fg)); }  SUPPRESSION DANS UN ABR arbre NoeudMax(arbre *r) { arbre p=NULL; if(*r!=NULL) { if((*r)->fd==NULL) { //plus grand trouvé void enlever(arbre *r,int x) p=*r; { *r=(*r)->fg; arbre res; } if (*r!=NULL) { else p = NoeudMax(&(*r)->fd); if(xval) enlever(&(*r)->fg,x); } else if(x>(*r)->val) enlever(&(*r)->fd,x); return p; else { //Noeud trouvé } if((*r)->fg==NULL) *r=(*r)->fd; else if ((*r)->fd==NULL) *r=(*r)->fg; else { //si un fg et un fd alors suppression //du plus GRAND à GAUCHE res=NoeudMax(&(*r)->fg); (*r)->val = res->val; } } } } 64 void enlever(arbre *r,int x) arbre NoeudMax(arbre *r) { { arbre res; arbre p=NULL; if (*r!=NULL) { if(*r!=NULL) { if(xval) enlever(&(*r)->fg,x); if((*r)->fd==NULL) { else if(x>(*r)->val) enlever(&(*r)->fd,x); //plus grand trouvé else { //Noeud trouvé p=*r; if((*r)->fg==NULL) *r=(*r)->fd; *r=(*r)->fg; else if ((*r)->fd==NULL) *r=(*r)->fg; } else { else p = NoeudMax(&(*r)->fd); //si un fg et un fd alors suppression } //du plus GRAND à GAUCHE return p; res=NoeudMax(&(*r)->fg); } (*r)->val = res->val; } } } } p