Afficher un arbre [Résolu]

théoriquement c'est compréhensible et logique mais je trouve des difficultés à implémenter ça!
si c'est possible pouvez-vous me fournir l'algorithme correspondant? merci d'avance

L'algo c'est ce que je t'ai expliqué, si c'est l'implémentation que tu veux il va falloir définir quel langage tu utilises. Mais également dire quelles genre de données tu manipules (ta structure d'arbre binaire, les données aux noeuds...) là j'ai expliqué le cas "simple" où chaque noeud est représenté par un unique caractère mais c'est rarement le cas en général et ça va tout décaler !

justement les noeuds de mon arbre sont soit des opérateurs soit des entiers introduits par l'utilisateur donc il peuvent être composés de plus qu'un seul chiffre

Les entiers aussi n'ont qu'un seul chiffre ?
Et quel est ta structure d'arbre (ton langage de programmation, ton type arbre...)

non il peuvent avoir plus qu'un chiffre
j'utilise le langage C
voici la définition des noeuds
typedef float feuille;

typedef struct s_noeud
{char op_c;
struct s_comp*filsg;
struct s_comp*filsd;
}noeud;

typedef struct s_comp
{int arite;
union {noeud n;
feuille f;
}val;
}composante;

à quoi te sers int arite ?

en fait ça signifie arité: si le noeud est un opérateur cette variable prend le nombre d'opérandes
(c'est pour l'évaluation du résultat)

mon programme consiste en fait à transformer une expression arithmétique en un arbre binaire ensuite afficher l'arbre et évaluer le résultat

Donc arite=0 pour une feuille, et 2 pour un noeud, est-ce que 1 est autorisé (l'affichage ne serait pas le même), et 3, 4...5 ?

oui 0 c'est pour une feuille, 1 et 2 seulement sont autorisés

il y a quelques erreurs que j'arrive pas à corriger!
ce code fonctionne chez vous??

Oui mais je l'ai compilé en C++ donc il peut y avoir quelques différences mais normalement ça devrait pas être grand chose... Quelles sont les erreurs affichées ?

ça fonctionne merci :)

Bonjour KX je sais que vous avez tors de mes questions mais quoi faire vous êtes le seul à pouvoir m'aider et je serai très reconnaissant si vous pourriez m'aider une dernière fois.
voici la déclaration de ma structure

--------------------------------------------------------------
typedef float feuille;

typedef struct s_noeud
{char op_c;
struct s_comp*filsg;
struct s_comp*filsd;
}noeud;

typedef struct s_comp
{int arite;
union {noeud n;
feuille f;
}val;
}composante;
typedef float feuille;

typedef struct s_noeud
{ char op_c;
struct s_comp*filsg;
struct s_comp*filsd;
}noeud;

typedef struct s_comp
{ int arite;
union{ noeud n;
feuille f;
}val;
}composante;

typedef composante *lien;
--------------------------------------------------------------
j'ai une variable x qui pointe vers le sommet de mon arbre que j'ai déjà construit. ( lien x )
j'ai pas arrivé à adapter le code que vous m'avez donné à ma structure et j'ai pas parvenu à afficher mon arbre
le temps me presse et je vous prie de m'aider. un grand merci de toute façon

Je n'adapterai pas mes blocs à ta structure de données ce soir, mais si tu comprends l'algo suivant (avec les exemples au dessus) tu devrais y arriver tout seul :

bloc affichageArbre(Arbre a)
{
	bloc b

	switch (a.arite)
	{
	case 0:	creer(b,a.operande)

	case 1:	bloc b1
		creer(b1,a.operateur)

		bloc b2 = affichageArbre(a.gauche)

		fusionner(b,b1,b2)

	case 2:	bloc b1
		creer(b1,a.operateur)

		bloc b2 = affichageArbre(a.gauche)
		bloc b3 = affichageArbre(a.droite)

		fusionner(b,b1,b2,b3)
	}

	return b;
}

Je n'ai pas tester ce code (il faudrait que je reconstruise tes méthodes de manipulation d'arbre !) mais ça correspond à l'algo juste au-dessus :

void afficherArbre(bloc &b, const arbre a)
{
	char ch[20];
	bloc b1,b2,b3;

	switch (a->arite)
	{
	case 0:
		sprintf(ch,"%f",a->val.f);
		creer(b,ch);
		return;

	case 1:
		sprintf(ch,"%c",a->val.n.op_c);
		creer(b1,ch);
		afficherArbre(b2,a->val.n.filsg);
		fusionner(b,b1,b2);
		return;

	case 2:
		sprintf(ch,"%c",a->val.n.op_c);
		creer(b1,ch);
		afficherArbre(b2,a->val.n.filsg);
		afficherArbre(b3,a->val.n.filsd);
		fusionner(b,b1,b2,b3);
		return;
	}
}

void afficherArbre(arbre a)
{
	bloc b;
	afficherArbre(b,a);
	afficher(b);
	liberer(b);
}

Super! vous êtes génie :) merci beaucouuuuuuup KX vous m'avez énormément aidé
voici la totalité du code si ça vous intéresse :) merci encore une fois
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define MAX 10
#define EMPTY -1


/*STRUCTURES DE DONNEES*/
struct pile
{
char info[MAX];
int top;
};

double eval_factor(char const* exp, char const** end);
double eval_term(char const* exp, char const** end);
double eval_exp(char const* exp, char const** end);

int error_occured;


typedef float feuille;

typedef struct s_noeud
{ char op_c;
struct s_comp*filsg;
struct s_comp*filsd;
}noeud;

typedef struct s_comp
{ int arite;
union{ noeud n;
feuille f;
}val;
}composante;

typedef composante *lien;


/*DU POSTFIXE AU PREFIXE INVERSE*/
void inverser(char *po,char *pr)
{
char *p1,*p2;
p2=pr;
for(p1=po;*p1;p1++)
{
*p2=' ';
p2++;
};
*p2='\0';
p1=po;

for(p2=pr;*p2;p2++);
p2--;
while(*p1)
{
while(*p1==' ')p1++;
if(*p1!= '\0')
{
while(*p1!=' '&& (*p1))p1++;
p1--;
while(*p1!=' ' && p1>=po)
{
*p2=*p1;
*p1=' ';
p1--;
p2--;
};
if (p2>=pr)
{
*p2=' ';
p2--;
};
p1++;
};
};
}


/*DU INFIXE AU POSTFIXE*/
int estvide(struct pile *s)
{
return (s->top == EMPTY) ? 1 : 0;
}

void pilevide(struct pile* s)
{
s->top=EMPTY;
}

void empiler(struct pile* s,char item)
{
if(s->top == (MAX-1))
{
printf("\npile pleine");
}
else
{
++s->top;
s->info[s->top]=item;
}
}

char depiler(struct pile* s)
{
char ret=' ';
if(!estvide(s))
{
ret= s->info[s->top];
--s->top;
}
return ret;
}

void affiche(struct pile s)
{
while(s.top != EMPTY)
{
printf("\n%d",s.info[s.top]);
s.top--;
}
}

int operateur(char e)
{
if(e == '+' || e == '-' || e == '*' || e == '/')
return 1;
else
return 0;
}

int priorite(char e)
{
int pri = 0;

if(e == '*' || e == '/')
pri = 2;
else
{
if(e == '+' || e == '-')
pri = 1;
}
return pri;
}

void convertir(char* i, char * postfix)
{
char *p;
struct pile X;
char n1;
pilevide(&X);
p = postfix;

while(*i)
{
while(*i == ' ' || *i == '\t')
i++;

if( isdigit(*i) )
{
while( isdigit(*i) || (*i)=='.')
{
*p = *i;
p++;
i++;
}
/*SPACE CODE*/

*p = ' ';
p++;

/*END SPACE CODE*/
}

if( *i == '(' )
{
empiler(&X,*i);
i++;
}

if( *i == ')')
{
n1 = depiler(&X);
while( n1 != '(' )
{
*p = n1;
p++;
/*SPACE CODE*/

*p = ' ';
p++;

/*END SPACE CODE*/
n1 = depiler(&X);
}
i++;
}

if( operateur(*i) )
{
if(estvide(&X))
empiler(&X,*i);
else
{
n1 = depiler(&X);
if (priorite(n1)== priorite(*i))
{
*p=n1;
p++;
/*SPACE CODE*/
*p=' ';
p++;
/*END SPACE CODE*/
empiler(&X,*i);
}
else
{
while(priorite(n1) > priorite(*i))
{
*p = n1;
p++;
/*SPACE CODE*/
*p = ' ';
p++;
/*END SPACE CODE*/
n1 = depiler(&X);
}
empiler(&X,n1);
empiler(&X,*i);
}
}
i++;
}
}
while(!estvide(&X))
{
n1 = depiler(&X);
*p = n1;
p++;
/*SPACE CODE*/

*p = ' ';
p++;

/*END SPACE CODE*/
}
*p = '\0';
}


/* ANALYSE DE L'EXPRESSION*/
int error(char const* msg, char const* remainder)
{
if (!error_occured) {
printf("%s at: %s\n", msg, remainder);
error_occured = 1;
}

return error_occured;
}

char const* skipws(char const* exp)
{
while (isspace((int)(unsigned char)*exp)) {
exp++;
}
return exp;

}



double eval_factor(char const* exp, char const** end)
{
double result;
exp = skipws(exp);
if (*exp == '(')
{
result = eval_exp(exp+1, end);
if (**end != ')') {
error("missing closing parenthesis", *end);
} else {
++*end;
}
}
else if (*exp == '+')
{
result = eval_factor(exp+1, end);
}
else if (*exp == '-')
{
result = -eval_factor(exp+1, end);
}
else
{
char* endptr;
result = strtod(exp, &endptr);
*end = endptr;
if (*end == exp) {
error("invalid expression", *end);
}
}
return result;

}

double eval_term(char const* exp, char const** end)
{
double result = eval_factor(exp, end);
*end = skipws(*end);
while (**end == '*' || **end == '/')
{
char const* op = *end;
double factor = eval_factor(*end+1, end);
if (*op == '*') {
result *= factor;
} else if (factor != 0.0) {
result /= factor;
} else {
error("divide by 0", op);
}
*end = skipws(*end);
}
return result;

}

double eval_exp(char const* exp, char const** end)
{
double result = eval_term(exp, end);
*end = skipws(*end);
while (**end == '+' || **end == '-') {
char const* op = *end;
double term = eval_term(*end+1, end);
if (*op == '+') {
result += term;
} else {
result -= term;
}
*end = skipws(*end);
}
return result;

}

double eval(char const* exp)
{
char const* end;
double result = eval_exp(exp, &end);
if (*end != '\0') {
error("FONCTION INCONNUE", end);
}
return result;

}


/*CONSTRUCTION DE L'ARBRE */
lien construire(char **deb)
{
lien x;
char c;

while(**deb==' ') (*deb)++;
if(**deb=='\0') return(NULL); /* on est arrivé en fin de chaîne */
x=(composante*)malloc(sizeof(composante));
if(isdigit(**deb))
{(*x).arite=0;
sscanf(*deb,"%f",&((*x).val.f));
while(isdigit(**deb)||**deb=='.') (*deb)++;
}
else
{c=**deb;
(*deb)++ ;
(*x).arite=2;
(*x).val.n.op_c=c;
(*x).val.n.filsd=construire(deb);
(*x).val.n.filsg=construire(deb);
}
return(x);
}


/*EVALUATION DE L'ARBRE*/
double evaluer(lien x)
{
double r1,r2;
if((*x).arite==0) return((*x).val.f);
else
{
r1=evaluer((*x).val.n.filsg);
r2=evaluer((*x).val.n.filsd);
switch ((*x).val.n.op_c)
{
case '+':return(r1+r2);
case '-':return(r1-r2);
case '*':return(r1*r2);
case '/':return(r1/r2);
}
}
puts("erreur (code opératoire inconnu par exemple)");
return(0);
}
typedef struct s_
{
size_t x,y;
char** tab; // tab[y][x]
} bloc;
void allouer(bloc &b,const size_t x,const size_t y)
{
b.x = x;
b.y = y;

b.tab = (char**) malloc(y*sizeof(char*));

size_t j;
for (j=0; j<b.y; j++)
b.tab[j]= (char*) malloc(x*sizeof(char));
}

void liberer(bloc &b)
{
size_t j;
for (j=0; j<b.y; j++)
free(b.tab[j]);

free(b.tab);
}

void creer(bloc &b, const char* str)
{
size_t i,n=strlen(str);
allouer(b,n,1);
for (i=0; i<n; i++)
b.tab[0][i]=str[i];
}

void afficher(const bloc& b)
{
size_t i,j;
for (j=0; j<b.y; j++)
{
for (i=0; i<b.x; i++)
printf("%c",b.tab[j][i]);
printf("\n");
}
printf("\n");
}
void fusionner(bloc &r, bloc &h, bloc &b, const char blanc=' ')
{
size_t
i,x1,x2,x3,x4,x5,
j,y1=h.y,y2=y1+b.y;

if (h.x<b.x)
{
x1=(b.x-h.x)/2;
x2=x1+h.x;
x3=0;
x4=b.x;
x5=x4;
}
else
{
x1=0;
x2=h.x;
x3=(h.x-b.x)/2;
x4=x3+b.x;
x5=x2;
}

allouer(r,x5,y2);

//----

for (j=0; j<y1; j++)
{
for (i=0; i<x1; i++)
r.tab[j][i]=blanc;
for (i=x1; i<x2; i++)
r.tab[j][i]=h.tab[j][i-x1];
for (i=x2; i<x5; i++)
r.tab[j][i]=blanc;
}

for (j=y1; j<y2; j++)
{
for (i=0; i<x3; i++)
r.tab[j][i]=blanc;
for (i=x3; i<x4; i++)
r.tab[j][i]=b.tab[j-y1][i-x3];
for (i=x4; i<x5; i++)
r.tab[j][i]=blanc;
}

//----

liberer(h);
liberer(b);
}

// Fusion des petits blocs en un gros bloc
// r : bloc resultat (alloué par la fonction)
// h : bloc en haut centré (désalloué par la fonction)
// g : bloc en bas à gauche (désalloué par la fonction)
// d : bloc en bas à droite (désalloué par la fonction)
void fusionner(bloc &r, bloc &h, bloc &g, bloc &d, const char blanc=' ')
{
size_t
x1 = g.x,
x2 = x1+h.x,
x3 = x2+d.x,
y1 = h.y,
y2 = (g.y>d.y) ? y1+g.y : y1+d.y;

allouer(r,x3,y2);

//------

size_t i, j;
for (j=0; j<y1; j++)
{
for (i=0; i<x1; i++)
r.tab[j][i]=blanc;
for (i=x1; i<x2; i++)
r.tab[j][i]=h.tab[j][i-x1];
for (i=x2; i<x3; i++)
r.tab[j][i]=blanc;
}

for (j=0; j<y2-y1; j++)
{
for (i=0; i<x1; i++)
r.tab[j+y1][i]=(g.y>j) ? g.tab[j][i] : blanc;
for (i=x1; i<x2; i++)
r.tab[j+y1][i]=blanc;
for (i=x2; i<x3; i++)
r.tab[j+y1][i]=(d.y>j) ? d.tab[j][i-x2] : blanc;
}

//------

liberer(g);
liberer(h);
liberer(d);
}

void afficherArbre(bloc &b, const lien a)
{
char ch[20];
bloc b1,b2,b3;

switch (a->arite)
{
case 0:
sprintf(ch,"%g",a->val.f);
creer(b,ch);
return;

case 1:
sprintf(ch,"%c",a->val.n.op_c);
creer(b1,ch);
afficherArbre(b2,a->val.n.filsg);
fusionner(b,b1,b2);
return;

case 2:
sprintf(ch,"%c",a->val.n.op_c);
creer(b1,ch);
afficherArbre(b2,a->val.n.filsg);
afficherArbre(b3,a->val.n.filsd);
fusionner(b,b1,b2,b3);
return;
}
}


void afficherArbre(lien a)
{
bloc b;
afficherArbre(b,a);
afficher(b);
liberer(b);
}
int main(int argc, char *argv[])
{
char ch[20];
char const *pt;
char *p;
char **pp;
lien A;
char postf[50],pref[50];
double R;

/*SESIE ET ANALYSE DE L'EXPRESSION*/
pt=ch;
do {
error_occured = 0;
printf("introduire votre expression ");
gets(ch);
R= eval(pt);
}
while(error_occured);
printf("\nLe resultat par analyse de l'expression est--------------->%g\n",R);

/*DU INFIXE AU POSTFIXE*/
convertir(ch,postf);
printf("L'expression postfixée correspondante est : %s\n",postf);

/*DU POSTFIXE AU PREFIXE INVERSE*/
inverser(postf,pref);
printf("L'expression prefixée correspondante est : %s\n",pref);

/*CONSTRUCTION DE L'ARBRE */
p=pref;
pp=&p;
A=construire(pp);

/*EVALUATION DE L'ARBRE*/
R=evaluer(A);
printf("\nLe resultat par evaluation de l'arbre est--------------->%g\n",R);


printf("\n\nMerci pour votre attention\n");
afficherArbre(A);


return 0;

}