Filières : 1-ISI

A.U : 2020/2021
Enseignant : Dr. Omar NAIFAR

TD 4
Algorithmique et structure des données
(Les arbres binaire)

Exercice
On représente une expression arithmétique par un arbre dont les nœuds sont des opérateurs ou des
nombres et dont les feuilles sont des nombres.

1. Écrire les structures de données permettant de représenter une expression arithmétique

sous forme d’arbre.
2. Écrire une fonction d’évaluation d’une expression arithmétique sous forme d’arbre.
3. Écrire une fonction qui génère une chaîne de caractères contenant l’expression préfixée
correspondant à un arbre.
4. Écrire une fonction de création d’un arbre représentant une expression arithmétique donnée
au format préfixé.
5. Écrire une fonction d’écriture d’une expression arithmétique sous forme parenthésée à partir
d’un arbre.
6. Écrire une fonction de création d’un arbre représentant une expression arithmétique donnée
au format parenthésé.

1
 Correction
1.
typedef struct Noeud
{
char contenue[30];
struct Noeud *fg, *fd;
} Noeud;
/*Fonction et déclarations nécessaires pour le traitement
des différentes parties de l’exercice*/
typedef struct Pile
{
char contenue[30];
struct Pile *suivant;
} Pile;
Pile initialiser()
{
return NULL;
}
char EstVide(Pile *P)
{
return (P == NULL) ? 1 : 0;
}
void push(Pile ** P, char * c)
{
Pile *q;
q = (Pile*) malloc(sizeof(Pile));
strcpy(q->contenue, c);
q->suivant = *P;
*P = q;
}

2
void pop(Pile ** P, char* c)
{
Pile *q;
if (EstVide(*P))
return ;
strcpy(c, (*P)->contenue);
q = *P;
*P = (*P)->suivant;
free(q);
}
void Afficherpile(Pile *P)
{
Pile *q;
q=P;
while (q != NULL)
{
printf("%s\t", q->contenue);
q = q->suivant;
}
puts("");
}
void Detruire(Pile ** P)
{
Pile *q;
while (*P != NULL)
{
q = *P;
*P = (*P)->suivant;
free(q);
}
*P = NULL;
}

3
void Vider(Pile ** P)
{
Detruire(&P);
*P = NULL;
}
void DetruireArbre(Noeud ** BT)
{
Noeud *qfg, *qfd;
if (*BT != NULL)
{
qfg = (*BT)->fg;
qfd = (*BT)->fd;
free(*BT);
DetruireArbre(&qfg);
DetruireArbre(&qfd);
}
}
void Traiter(Noeud * BT)
{
printf("%s, ", BT->contenue);
}
void ParcoursPrefixe(Noeud * BT)
{
if (BT != NULL)
{
Traiter(BT);
ParcoursPrefixe(BT->fg);
ParcoursPrefixe(BT->fd);
}
}
--------------------------------------------------------------------

4
2.
void Evaluation(Noeud * BT, Pile * P)
{
char a[30], b[30], c[30];
if (BT != NULL)
{
Evaluation(BT->fd, P);
Evaluation(BT->fg, P);
if (strcmp(BT->contenue, "+") == 0)
{
pop(&P, a);
pop(&P, b);
sprintf(c, "%d", atoi(a) + atoi(b));
push(P, c);
}
else if (strcmp(BT->contenue, "*") == 0)
{
pop(&P, a);
pop(&P, b);
sprintf(c, "%d", atoi(a) * atoi(b));
push(&P, c);
}
else if (strcmp(BT->contenue, "-") == 0)
{
pop(&P, a);
pop(&P, b);
sprintf(c, "%d", atoi(a) - atoi(b));
push(P, c);
}
else if (strcmp(BT->contenue, "/") == 0)
{
pop(&P, a);

5
 pop(&P, b);
sprintf(c, "%d", atoi(a) / atoi(b));
push(&P, c);
}
else
push(&P, BT->contenue);
}
}

3.
void GenereExpPrefixee(Noeud * BT, Pile * P)
{
if (BT != NULL)
{
GenereExpPrefixee(BT->fd, P);
GenereExpPrefixee(BT->fg, P);
push(&P, BT->contenue);
}
}

4.
void CreationArbreDePrefixe(Noeud * BT, Pile * P)
{
char *c;
if (P != NULL)
{
pop(&P, c);
strcpy(BT->contenue, c);
if (strcmp(P->contenue, "+") == 0 ||
strcmp(P->contenue, "-") == 0 || strcmp(P ->contenue, "*")
== 0 ||
strcmp(P ->contenue, "/") == 0)

6
 {
BT->fg = (Noeud *) malloc(sizeof(Noeud));
BT->fd = (Noeud *) malloc(sizeof(Noeud));
CreationArbreDePrefixe(BT->fg, P);
CreationArbreDePrefixe(BT->fd, P);
}
else
{
BT->fg = NULL;
BT->fd = NULL;
}
}
}

5.
void ExprParenthese(Noeud * BT, Pile * P)
{
Pile *q;
char a[30], b[30], c[30];
if (BT!= NULL)
{
ExprParenthese(BT->fd, P);
ExprParenthese(BT->fg, P);
if (strcmp(BT->contenue, "+") == 0
|| strcmp(BT->contenue, "-") == 0
|| strcmp(BT->contenue, "*") == 0
|| strcmp(BT->contenue, "/") == 0)
{
pop(&P, a);
pop(&P, b);
strcpy(c, "(");
strcat(c, a);

7
 strcat(c, BT->contenue);
strcat(c, b);
strcat(c, ")");
push(&P, c);
}
else
push(&P, BT->contenue);
}
}
6.
void ParentheseEnPrefixe(Pile *Original, Pile **Cumul, Pile
**final)
{
Pile *q;
char a[20];
q = Original;
if (q != NULL)
{
if (strcmp(q->contenue, "+") == 0 || strcmp(q->contenue, "-") == 0 ||
strcmp(q->contenue, "*") == 0 || strcmp(q->contenue, "/") == 0)
{
push(&(*Cumul), q->contenue);
}
else if (strcmp(q->contenue, ")") == 0)
{
}
else if (strcmp(q->contenue, "(") == 0)
{
pop(&(*Cumul), a);
push(&(*final), a);
}
else
{

8
push(&(*final), q->contenue);
}
q = q->suivant;
return ParentheseEnPrefixe(q, &Cumul, &final);
}
}
/*Dans cette fonction, l’exp parenthésée est
écrite sous format préfixée et puis l’arbre est construit*/
void CreationArbredeParenthese(Noeud * BT, Pile *exprparenthese)
{
Pile *Cumul, *final;
Cumul = initialiser();
final = initialiser();
ParentheseEnPrefixe(exprparenthese, &Cumul, &final);
CreationArbreDePrefixe(BT, & final);
Detruire(&Cumul);
Detruire(&final);
}

9
Le programme principal
int main()
{
Pile *P = NULL;
char car[20] = "\0";
P = initialiser();
Noeud *BT;
/* Saisir l’expression parenthésée entrée par l’utilisateur
l’exp est considérée complètement parenthésée ex ((10+2)/3) */
printf("Entrez les membres de l’expr. préfixée en
appuyant sur entrer à chaque fois qu’un élement est saisi et
tapez terminer pour finir\n");
scanf("%s", car);
while (strcmp(car, "terminer") != 0)
{
push(&P, car);
scanf("%s", car);
}
BT = (Noeud *) malloc(sizeof(Noeud));
/* (d) ou (f) (meme principe) */
/* Créer l’arbre à partir de l’expression parenthésée */
CreationArbredeParenthese(BT, &P);
puts("L’arbre créé est le suivant");
ParcoursPrefixe(BT);
puts("");
Vider(&P);
/* (c) Générer l’expression préfixée à partir de l’arbre,
le résultat se trouve dans la pile "P" */
GenereExpPrefixee(BT, P);
printf("L’expression préfixée à partir de l’arbre=\n");
Afficherpile(P);

10
 puts("");
Vider(&P);
/* (b) Évaluation de l’exp. arith., le résultat se trouve dans
la pile "P" contenant un seul élément à la sortie de la
fonction */
Evaluation(BT, P);
printf("Evaluation de l’exp arith. =%s\n", P->contenue);
Vider(&P);
/* (e) L’expression parenthésée est générée à partir de l’arbre
le résultat se trouve dans la pile "P" contenant un seul
élément
à la sortie de la fonction */
ExprParenthese(BT, P);
printf("Exp. parenthésée générer de l’arbre=%s\n", P->contenue);
Vider(&P);
DetruireArbre(&BT);
return 0;
}

11