Afficher un arbre [Résolu/Fermé]

Signaler
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013
-
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013
-
Bonjour,

je voudrais savoir comment afficher un arbre binaire "sous la forme d'un arbre"
exemple:
******* + ******************
*** - ******* 9
* 5 ** 6 *********************

2 réponses

Messages postés
16054
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 octobre 2020
2 696
Ça va fortement dépendre de ce que tu as afficher.
Cas simple : en console, chaque feuille/noeud est représenté par 1 caractère.

Il te faut tout d'abord calculer la hauteur de l'arbre : h
Du coup tu sais déjà quelle sera la ligne h, elle sera composée de 2^h caractères chacun séparés par 1 espace. De même la première ligne sera composée de 1 caractère "séparé" par 2^h espaces. Il suffit donc pour toutes les lignes k d'afficher les 2^k noeuds chacun espacés de 2^(h-k) espaces et ça devrait être à peu près bon (à quelques +/- 1 près)
Messages postés
16054
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 octobre 2020
2 696
à quoi te sers int arite ?
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013

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)
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013

mon programme consiste en fait à transformer une expression arithmétique en un arbre binaire ensuite afficher l'arbre et évaluer le résultat
Messages postés
16054
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 octobre 2020
2 696
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 ?
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013

oui 0 c'est pour une feuille, 1 et 2 seulement sont autorisés
Messages postés
16054
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 octobre 2020
2 696
Je n'ai pas tout fait, j'ai voulu faire quelque chose d'assez général de sorte que ça puisse être utilisé dans n'importe quel arbre binaire, j'ai donc fait "uniquement" de la manipulation de char*

Il te reste donc à utiliser mon code pour l'adapter à ta structure d'arbre, en faisant récursivement des créations de blocs pour les opérateurs et les opérandes ainsi que des fusions de blocs pour l'arbre et ses sous-arbres.

Regarde bien le main qui affiche ((1.23+4.5)*(-(6.7/8.9))) pour voir comment utiliser mes méthodes, je pense que tu verras tout de suite la récursivité ;-)

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

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");
}

// 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)
// b : bloc en bas  centré (désalloué par la fonction)
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);
}

int main()
{
	bloc b;
	{
		bloc b1;
		{
			creer(b1,"*");
		}
		
		bloc b2;
		{
			bloc b21;
			{
				creer(b21,"+");
			}
			
			bloc b22;
			{
				creer(b22,"1.23");
			}
			
			bloc b23;
			{
				creer(b23,"4.5");
			}
			
			fusionner(b2,b21,b22,b23);
		}
		
		bloc b3;
		{
			bloc b31;
			{
				creer(b31,"-");
			}
			
			bloc b32;
			{
				bloc b321;
				{
					creer(b321,"/");
				}
				
				bloc b322;
				{
					creer(b322,"6.7");
				}
				
				bloc b323;
				{
					creer(b323,"8.9");
				}
				
				fusionner(b32,b321,b322,b323);
			}
			
			fusionner(b3,b31,b32);
		}
		
		fusionner(b,b1,b2,b3);
	}
	
	afficher(b);
	
	liberer(b);
	
	system("PAUSE");
	return 0;
}
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013

ça fonctionne merci :)
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013

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
Messages postés
16054
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 octobre 2020
2 696
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;
}
Messages postés
16054
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
9 octobre 2020
2 696
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);
}
Messages postés
31
Date d'inscription
mercredi 10 août 2011
Statut
Membre
Dernière intervention
9 mai 2013

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;

}