Posez votre question Signaler

Afficher un arbre [Résolu]

sangoku12 31Messages postés mercredi 10 août 2011Date d'inscription 9 mai 2013 Dernière intervention - Dernière réponse le 14 sept. 2011 à 16:47
Bonjour,
je voudrais savoir comment afficher un arbre binaire "sous la forme d'un arbre"
exemple:
******* + ******************
*** - ******* 9
* 5 ** 6 *********************
Lire la suite 
Réponse
+0
moins plus
Ç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)
KX 11725Messages postés samedi 31 mai 2008Date d'inscription ContributeurStatut 10 juillet 2015 Dernière intervention - 7 sept. 2011 à 18:56
à quoi te sers int arite ?
Répondre
sangoku12 31Messages postés mercredi 10 août 2011Date d'inscription 9 mai 2013 Dernière intervention - 7 sept. 2011 à 19:07
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)
Répondre
sangoku12 31Messages postés mercredi 10 août 2011Date d'inscription 9 mai 2013 Dernière intervention - 7 sept. 2011 à 19:09
mon programme consiste en fait à transformer une expression arithmétique en un arbre binaire ensuite afficher l'arbre et évaluer le résultat
Répondre
KX 11725Messages postés samedi 31 mai 2008Date d'inscription ContributeurStatut 10 juillet 2015 Dernière intervention - 7 sept. 2011 à 19:16
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 ?
Répondre
sangoku12 31Messages postés mercredi 10 août 2011Date d'inscription 9 mai 2013 Dernière intervention - 7 sept. 2011 à 19:25
oui 0 c'est pour une feuille, 1 et 2 seulement sont autorisés
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
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;
}
sangoku12 31Messages postés mercredi 10 août 2011Date d'inscription 9 mai 2013 Dernière intervention - 10 sept. 2011 à 21:13
ça fonctionne merci :)
Répondre
sangoku12 31Messages postés mercredi 10 août 2011Date d'inscription 9 mai 2013 Dernière intervention - 14 sept. 2011 à 00:26
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
Répondre
KX 11725Messages postés samedi 31 mai 2008Date d'inscription ContributeurStatut 10 juillet 2015 Dernière intervention - 14 sept. 2011 à 01:30
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;
}
Répondre
KX 11725Messages postés samedi 31 mai 2008Date d'inscription ContributeurStatut 10 juillet 2015 Dernière intervention - 14 sept. 2011 à 13:15
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);
}
Répondre
sangoku12 31Messages postés mercredi 10 août 2011Date d'inscription 9 mai 2013 Dernière intervention - 14 sept. 2011 à 16:47
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;

}
Répondre
Ajouter un commentaire
Ce document intitulé «  afficher un arbre  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes.

Le fait d'être membre vous permet d'avoir des options supplémentaires.