Les composantes de l'arbre seront donc soit des operateurs (noeuds), soit des operandes (feuilles). Nous allons choisir les declarations suivantes :
typedef float type_feuille;
typedef struct s_noeud_2
{char op_c;
struct s_comp*fils1;
struct s_comp*fils2;
}type_noeud_2;
typedef struct s_noeud_1
{char op_c;
struct s_comp*fils;
}type_noeud_1;
typedef struct s_comp
{int arite;
union
{type_noeud_2 n2;
type_noeud_1 n1;
type_feuille f;
}val;
}composante;
typedef composante *lien;
Nous prevoyons donc deux types de noeuds : a arite 1 (avec
un fils) ou a arite 2 (deux fils). On aurait pu utiliser un seul
type (a arite 2) en mettant NULL dans le second fils en cas
d'arite 1. Une feuille par contre ne contient aucun lien. Une composante
de l'arbre contiendra donc un indicateur de son type (ici l'arite) et,
suivant ce type, soit une feuille, soit un noeud (d'arite 1 ou 2). Nous
allons ecrire une fonction creant un tel arbre (a partir
d'une chaine de caracteres prealablement saisie, contenant
l'expression en notation polonaise prefixee
par exemple) : {
lien x;
char c;
while(**deb==' '||**deb==',') (*deb)++;
if(**deb==0) /* on est arrive en fin de chaine */
{puts("erreur : il doit manquer des operandes");
return(NULL);}
x=(composante*)malloc(sizeof(composante));
if(isdigit(**deb))
{
x->arite=0;
sscanf(*deb,"%f",&(x->val.f));
while(isdigit(**deb)||**deb=='.') (*deb)++;
}
else
{
c=toupper(*((*deb)++));
if(c=='*'||c=='/'||c=='+'||c=='-')
{
x->arite=2;
x->val.n2.op_c=c;
x->val.n2.fils1=saisie_prefixe(deb);
x->val.n2.fils2=saisie_prefixe(deb);
}
else if(c=='C'||c=='S')
{
x->arite=1;
x->val.n1.op_c=c;
x->val.n1.fils=saisie_prefixe(deb);
}
else printf("erreur, '%c'n'est pas un operateur prevu\n",c);
}
return(x);
}
On peut remarquer que cette fonction est recursive.
La creation de l'arbre a partir d'une expression postfixee
est similaire (scruter la chaine dans l'autre sens par exemple), a
partir d'une expression infixee
c'est un peu plus dur, surtout si l'on ne veut pas imposer d'entrer toutes les
parentheses, par exemple 1+2+3 au lieu de (1+(2+3)).L'utilisation d'un tel arbre devient maintenant tres simple. On utilisera la recursivite. Pour evaluer l'expression, si c'est une feuille unique la valeur est celle de la feuille, si c'est un noeud, la valeur est obtenue en effectuant l'operation correspondante, apres evaluation (recurrente, donc soit directement la valeur si feuille soit nouveau calcul) de ses fils :
float eval(lien x)
{
float r1,r2;
if(x->arite==0) return(x->val.f);
else if (x->arite==1)
{
if (x->val.n1.op_c=='C')
return(cos(eval(x->val.n1.fils)));
else if (x->val.n1.op_c=='S')
return(sin(eval(x->val.n1.fils)));
}
else
{
r1=eval(x->val.n2.fils1);
r2=eval(x->val.n2.fils2);
switch (x->val.n2.op_c)
{
case '+':return(r1+r2);
case '-':return(r1-r2);
case '*':return(r1*r2);
case '/':return(r1/r2);
}
}
/* si aucun return n'a ete effectue jusqu'ici*/
puts("erreur (code operatoire inconnu par exemple)");
return(0);
}
Le parcours
des arbres (c'est a dire le passage par tous les noeuds et feuilles) se
fait d'habitude de maniere recursive. On doit evidement
parcourir l'arbre pour afficher son contenu. On peut utiliser dans le cas des
arbres binaires trois possibilites de parcours : afficher la valeur du
noeud puis recursivement de ses deux fils, afficher le premier fils, la
valeur du noeud, puis le second fils, ou afficher les deux fils avant la valeur
du noeud. On obtient dans notre cas directement les notations
prefixe, infixee et postfixee (avec un petit
travail supplementaire pour la gestion des parentheses en
notation infixee, qu'on aurait pu simplifier si l'on avait
accepte des parentheses surabondantes) :void affiche_prefixe(lien x)
{
switch(x->arite)
{
case 0:printf("%6.1f ",x->val.f);break;
case 1:printf(" %C ",x->val.n1.op_c);
affiche_prefixe(x->val.n1.fils);
break;
case 2:printf(" %c ",x->val.n2.op_c);
affiche_prefixe(x->val.n2.fils1);
affiche_prefixe(x->val.n2.fils2);
}
}
void affiche_postfixe(lien x)
{
switch(x->arite)
{
case 0:printf("%6.1f ",x->val.f);break;
case 1:affiche_postfixe(x->val.n1.fils);
printf(" %C ",x->val.n1.op_c);
break;
case 2:affiche_postfixe(x->val.n2.fils1);
affiche_postfixe(x->val.n2.fils2);
printf(" %c ",x->val.n2.op_c);
}
}
void affiche_infixe(lien x)
{
switch(x->arite)
{
case 0:printf("%6.1f ",x->val.f);break;
case 1:printf(" %C( ",x->val.n1.op_c);
affiche_infixe(x->val.n1.fils);
putch(')');
break;
case 2:if(x->val.n2.fils1->arite!=0)putch('(');
affiche_infixe(x->val.n2.fils1);
if(x->val.n2.fils1->arite!=0)putch(')');
printf(" %c ",x->val.n2.op_c);
if(x->val.n2.fils2->arite!=0)putch('(');
affiche_infixe(x->val.n2.fils2);
if(x->val.n2.fils2->arite!=0)putch(')');
}
}
Notre exemple est un peu plus complexe que dans veritable arbre
binaire, puisque nous acceptions egalement des noeuds a un seul
fils.
typedef struct s_noeud *lien;
typedef struct s_noeud
{char *nom;
lien fils1;
lien fils2;
}type_noeud;
Il vaut mieux ne pas prevoir de type specifique pour les
feuilles, l'arbre etant gere de maniere
evolutive (une feuille sera donc un noeud avec ses deux fils valant le
pointeur NULL). Le nom contenu dans chaque noeud aurait pu etre un
tableau statique de caracteres, mais pour optimiser le cout
memoire, nous utiliserons un tableau dynamique. Donc, pour allouer la
memoire d'un nouveau noeud, deux malloc
seront necessaires : un pour le noeud lui-meme, et un pour le nom
qui lui est associe. Ecrivons une fonction de creation d'un noeud
(on lui transmet le nom associe, elle retourne l'adresse allouee):lien cree_feuille(char *nouv_nom)
{
lien x;
int taille;
x=(lien)malloc(sizeof(type_noeud));
taille=strlen(nouv_nom)+1; /* compter le \0 */
x->nom=(char*)malloc(taille);
strcpy(x->nom,nouv_nom);
x->fils1=NULL;
x->fils2=NULL;
return(x);
}
Supposons entrer dans l'ordre : Jean, Bernard, Lucie, Anne, Jacques,
Laurent, Maud, Luc, Julie, Elsa. Si vous creez progressivement l'arbre,
vous pourrez voir que toute nouvelle valeur trouve toujours sa place, les
feuilles se transformant petit a petit en noeuds, au fur et a
mesure de l'augmentation de la taille de l'arbre.
La fonction effectuant la saisie et la creation de cet arbre devra donc, apres la saisie du nouveau nom a inserer, rechercher sa position definitive. Cette recherche sera recursive: sur un noeud donne, si le nouveau nom est plus petit, rechercher dans la descendance du fils1, sinon rechercher dans la descendance du fils2. La recherche s'arrete quand on arrive a un pointeur NULL (qui sera remplace par l'adresse du nouveau noeud). En cas d'egalite, si l'on desire une creation stable, un nouveau nom sera place derriere ceux deja existants. :
void insert_feuille(lien racine, lien x)
{
while(racine!=NULL) /* ou boucle infinie */
{
if(strcmp(x->nom,racine->nom)<0)
if(racine->fils1==NULL){racine->fils1=x;return;}
else racine=racine->fils1;
else
if(racine->fils2==NULL){racine->fils2=x;return;}
else racine=racine->fils2;
}
}
lien saisie(void)
{
lien racine=NULL;
char txt[100];
do
{
printf("entrez un nouveau nom, @@@ pour finir : ");
gets(txt);
if(strcmp(txt,"@@@"))
if(racine==NULL)racine=cree_feuille(txt);
else insert_feuille(racine,cree_feuille(txt));
}
while(strcmp(txt,"@@@"));
return(racine);
}
On remarque l'efficacite de cette methode : aucun
deplacement d'element, le tri se fait par insertion, mais
avec recherche optimisee (du type dichotomie : l'espace de recherche est
reduit a chaque test). Pour N insertions, on fait donc N
recherches donc N*P lectures de composantes (P profondeur de l'arbre).Une fois l'arbre cree, on peut afficher la liste triee par ordre alphabetique par un simple parcours infixe (arbr_nom):
void affiche(lien x)
{
if(x!=NULL)
{
affiche(x->fils1);
printf("%s, ",x->nom);
affiche(x->fils2);
}
}
L'utilisation d'un arbre binaire
pour une liste triee permet donc une programmation relativement
aisee, des algorithmes rapides, mais moyennant un peu de place
memoire supplementaire. L'arbre va posseder
simultanement tous les avantages des autres structures de donnees:
En fait, plutot que de creer cette liste hors des noeuds, le plus simple (et qui utilise autant de memoire) est d'associer a chaque noeud l'adresse de son fils aine, et de son frere cadet. Acceder a tous les fils revient donc a acceder au fils aine puis a tous ses freres:
On peut remarquer qu'un tel arbre est un arbre binaire: chaque noeud possede deux liens. On peut donc traiter tout arbre sous forme d'un arbre binaire.
Une autre amelioration possible d'un arbre est de permettre un acces toujours sequentiel mais bidirectionnel : pour un arbre binaire, chaque noeud possede en plus l'adresse de son pere, pour un arbre generalise ceci revient a ce que chaque frere connait son aine, l'aine connaissant leur pere commun. Cet acces bidirectionnel est couteux en memoire, mais complique egalement les modifications (plus de liens a gerer), pour par contre accelerer les parcours dans l'arbre. On ne prevoira cette amelioration que lorsque l'on utilise de frequentes remontees (l'utilisation d'algorithmes recursifs ne necessite en general pas ces liens, le fait de quitter une fonction appelee pour gerer un fils fait automatiquement retrouver le pere).