TP5 arbre.c

/* TP5 arbre.c 28/11/02 */
#include <stdio.h>
#include <stdlib.h>
#include "arbre.h"

AB Creer_AB(){
return NULL;
}

AB Ajouter_AB(AB a,Element e){
/* Attention, cette fonction n'est pas la meme que le prof puisque */
/* celle du prof ne fonctionne pas ! ! ! */
AB q;

if (Arbre_vide(a)==VRAI) { /* Vide */
q=(AB)malloc(sizeof(*q));
q->e=e;
q->d=NULL;
q->g=NULL;
a=q;
return a;
}

if (e<a->e) {
if (Arbre_vide(Fg(a))==FAUX)
return Ajouter_AB(Fg(a),e);
else {
q=(AB)malloc(sizeof(*q));
q->e=e;
q->d=NULL;
q->g=NULL;
a->g=q;
return a;
}
}
else {
if (Arbre_vide(Fd(a))==FAUX)
return Ajouter_AB(Fd(a),e);
else {
q=(AB)malloc(sizeof(*q));
q->e=e;
q->d=NULL;
q->g=NULL;
a->d=q;
return a;
}
}
}

AB Fg(AB a){
return a->g;
}

AB Fd(AB a){
return a->d;
}

Element Val(AB a){
return a->e;
}

int Taille(AB a){ /* Taille: compter le nombre de sommet */
if (Arbre_vide(a)==VRAI)
return 0;
else
return (1+Taille(Fg(a))+Taille(Fd(a)));
}

int _max(int a,int b){
if (a>b)
return a;
else
return b;
}

int Hauteur(AB a){
if (Arbre_vide(a)==VRAI)
return 0;
else
return 1+_max(Hauteur(Fg(a)),Hauteur(Fd(a)));
}

BOOL Arbre_vide(AB a){
if (a==NULL)
return VRAI;
else
return FAUX;
}

/* ©2002 All Rights Reserved to Didier STRAUS http://www.Software-DS.com*/
int Equilibre(AB a){
if (Arbre_vide(a)==VRAI)
return 1; /* VRAI */
else if (abs(Hauteur(Fg(a))-Hauteur(Fd(a)))>1)
return 0; /* FAUX */
else
return (Equilibre(Fg(a)) && Equilibre(Fd(a)));
}

BOOL Appartient(AB a,Element x){
if (Arbre_vide(a)==VRAI)
return FAUX;
else if(a->e==x)
return VRAI;
else if (x<a->e)
return Appartient(Fg(a),x);
else
return Appartient(Fd(a),x);
}

AB PlusDroite(AB p){
if (Arbre_vide(Fd(p))==VRAI)
return p;
else
return PlusDroite(Fd(p));
}

AB Supprimer(AB a,Element x,AB last){
/* On suppose que x appartient a l'arbre a */
/* Dans last on memorise le pere de a s'il en a un */
AB Q,P;
Element e;
if(Val(a)==x) {
/* 1° cas : les 2 fils sont vides */
if ((Arbre_vide(Fg(a))==VRAI) && (Arbre_vide(Fd(a))==VRAI)) {
if (Fg(last)->e==x)
last->g=NULL;
else
last->d=NULL;
free(a);
printf("cas 1");
return last;
}
/* 2° cas : un des 2 fils est vide */
if (Arbre_vide(Fg(a))==VRAI) {
if (Fg(last)->e==x)
last->g=Fd(a);
else
last->d=Fd(a);
free(a);
printf("cas 2-1");
return last;
}
if (Arbre_vide(Fd(a))==VRAI) {
if (Fg(last)->e==x)
last->g=Fg(a);
else
last->d=Fg(a);
free(a);
printf("cas 2-2");
return last;
}
/* 3° cas : aucun des 2 fils est vide (à finir) */
Q=PlusDroite(Fg(a));
e=Val(Q);
P=Supprimer(a,e,a);
last->e=e;
return last;
}
else if (x<a->e)
return Supprimer(Fg(a),x,a);
else
return Supprimer(Fd(a),x,a);
}

/* ©2002 All Rights Reserved to Didier STRAUS http://www.Software-DS.com*/
/* Applications aux ensembles */

AB UnionAjouter(AB dest,AB source){
AB c;

if (Arbre_vide(source)==VRAI)
return dest;
c=Ajouter_AB(dest,Val(source));
dest=UnionAjouter(dest,Fg(source));
dest=UnionAjouter(dest,Fd(source));
return dest;
}

AB Union(AB a,AB b){
AB res,c;

res=Creer_AB();
res=Ajouter_AB(res,0);
c=UnionAjouter(res,a);
c=UnionAjouter(res,b);
return res;
}

AB InterAjouter(AB dest,AB a,AB b){
AB c;

if (Arbre_vide(a)==VRAI)
return dest;
if (Appartient(b,Val(a))==VRAI)
c=Ajouter_AB(dest,Val(a));
c=InterAjouter(dest,Fg(a),b);
c=InterAjouter(dest,Fd(a),b);
return dest;
}

AB Intersection(AB a,AB b){
AB res,c;

res=Creer_AB();
res=Ajouter_AB(res,0);
c=InterAjouter(res,a,b);
return res;
}

/* ©2002 All Rights Reserved to Didier STRAUS http://www.Software-DS.com*/