Dessiner un arbre n-aire - Page 1

Voila. J'ai une classe Noeud. Et j'aimerais faire une fonction d'affichage en mode console (avec uniqement printf sans cout) qui affiche l'arbre. Les noeud ont entre 0 et n fils.

sur le net j'ai trouvé ca, mais cest pas en mode console:
procedure arbre.dessine(en_cours: noeud; limg, old_x, old_y: integer); var x, y, nb: integer;   i: char; begin //nb:=compter_terminaux(courant); // effet joli   nb := compter_terminaux(en_cours);   x := limg + (50 * nb) div 2;   y := old_y + 80;   if en_cours <> tete then     with form1.image1.picture.bitmap.canvas do     begin       textout(x, y, en_cours.lettre);       en_cours.x := x; en_cours.y := y;       moveto(x, y - 5); lineto(old_x, old_y);     end;   for i := 'A' to 'Z' do     if en_cours.fils[i] <> nil then     begin       nb := compter_terminaux(en_cours.fils[i]);       dessine(en_cours.fils[i], limg, x, y + 20);       limg := limg + nb * 50;     end; end;

Il faut faire un parcours en largeur de l'arbre pour savoir les longueurs respectives des chaînes. C'est détaillé notamment dans "Algorithmes et structures de données génériques" de Michel Divay (il y a du code, C écrit plus ou moins de façon OO).

oui mais c'est un livre ca. Et ca coute 29€

t'as plusieurs facons de representer un arbre, tu peux le coucher hein genre:

racine
    fils1
        petitfils11
        petitfils12
    fils2
        petitfils21

Dans ce cas la, c'est tres simple a afficher


ps: tu trouveras plein d'algos de parcours en largeur d'arbre sur le net...

cest vrai que ca peut etre une solution de secours...
moi je pensais plutot à un affichage de ce genre:

                     +-<1 >
              +-<- >-|
              |      |      +-<0 >
              |      +-<* >-|
              |             +-<0 >
       +-<+ >-|
       |      +-<1 >
+-<& >-|
       +-<0 >

mais en n-aire. Donc eventuellement du genre:

                     +-<1 >
                     |       +-<1 >
              +-<- >-|       |
              |      |       +-<0 >
              |      +--<* >-|
              |              +-<0 >
       +-<+ >-|
       |      +-<1 >
+-<& >-|
       +-<0 >

Et les routines pour ca, ca court pas les rues d'internet

Ben, 'faut dire qu'en mode console, tu dois commencer par la branche qui est graphiquement la plus à droite.. (en considérant un arbre comme ça : )
[pre] /\ /\/[/pre] Tu risques de devoir passer par une structure intermédiaire, comme un classement des noeuds par abscisse...

idée :
tu fais un tableau de taille nb de feuille par hauteur de l'arbre. Avec le 2ème exemple ./5 : 6x5.
tu fais un parcours en profondeur :
- dès que tu rencontres une feuille tu le place dans le tableau.
- quand tu remontes sur un noeud et que tu as visité tous ces fils tu lemets à la bonne place en fonctions d'où tu as placé les fils.
ca donnerait ca :.

.	.	1	.
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.

.

.	.	1	.
.	.	.	.	1
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.

.

.	.	1	.
.	.	.	.	1
.	.	.	.	0
.	.	.	.	.
.	.	.	.	.
.	.	.	.	.

.

.	.	1	.
.	.	.	.	1
.	.	.	.	0
.	.	.	.	0
.	.	.	.	.
.	.	.	.	.

.

.	.	1	.
.	.	.	.	1
.	.	.	*	0
.	.	.	.	0
.	.	.	.	.
.	.	.	.	.

.

.	.	1	.
.	.	-	.	1
.	.	.	*	0
.	.	.	.	0
.	.	.	.	.
.	.	.	.	.

.

.	.	1	.
.	.	-	.	1
.	.	.	*	0
.	.	.	.	0
.	.	1	.	.
.	.	.	.	.

.

.	.	1	.
.	.	-	.	1
.	+	.	*	0
.	.	.	.	0
.	.	1	.	.
.	.	.	.	.

.

.	.	1	.
.	.	-	.	1
.	+	.	*	0
.	.	.	.	0
.	.	1	.	.
.	0	.	.	.

.

.	.	1	.
.	.	-	.	1
.	+	.	*	0
&	.	.	.	0
.	.	1	.	.
.	0	.	.	.

Ca a l'air de bien marcher ton truc (sans avoir testé), le tableau a l'allure de ce que je veux faire dessiner.

Mais là je vois pas ce qu'il faut appeler avec printf. Comment passer de ton tableau à la representation?
Je devrais peut etre faire des tableaux de char de maniere à appeler la fonction afficher d'un fils/noeud en lui donnant en parametre ce qu'il y a à gauche (par exemple "..." pour le "1" de la premiere ligne de ton exemple), ceci correspondant à une ligne de ton tableau.

Pour une case vide, ton printf sera un printf(" "), pour une case avec quelque chose, ce sera printf("+") par exemple.

effectivement, mais ca donnera ça :

            +<1>
        +<->    +<1>
    +<+>    +<*>+<0>
+<&>            +<0>
        +<1>
    +<0>   

Tu peux donc enrichir ton tableau en y ajoutant des "liens" : .

.	.	1	.
.	.	-	|	1
.	+	|	*	0
&	|	|	.	0
.	|	1	.	.
.	0	.	.	.

            +<1>
        +<->|   +<1>
    +<+>|   +<*>+<0>
+<&>|   |       +<0>
    |   +<1>
    +<0>   

Tu peux aussi commencer par la droite et remonter à gauche avec le printf.

Voilà une façon d'afficher un arbre que j'ai codé en 3 minutes, je n'ai pas testé
[source=]

je viens de regarder, ça doit sûrement marcher.
Moi j'ai fait la solution qui demande de la mémoire (le tableau), la solution de Thepro demande du temps de calcul (des calculs faits et refaits).

Nouvelle version que je n'ai toujours pas testé ////////////////////////// © Raoul PRÉVOST (Thepro). ////////////////////////// typedef struct {char *texte;int nbenfants,hauteur;void *parent,**enfants;} noeud; int dec=5; //Largeur maximale des textes des noeuds (utile seulement avec la ligne (1)). void printXY(int x,int y,char *texte) {      printf("\33[u;%dB;%dC%s",y,x,texte); } int InitHauteur(noeud *courant) {      int i,nb=0;      if (!courant->nbenfants) nb=2;      for (i=0;i<courant->nbenfants;i++)           nb+=InitHauteur(courant->enfants[i]);      nb+=courant->nbenfants-1;      courant->hauteur=nb;      return nb; } void DessineNoeud(noeud courant,short x,short y) {      int i,ycourant=y+(courant.hauteur-1)/2;      printXY(x-1,ycourant,(char*)"+");      printXY(x,ycourant,courant.texte);      if (!courant.nbenfants) return;             //////////////////// Ne garder que l'une de ces 2 lignes ! ////////////////////      x+=dec;// (1)      x+=strlen(courant.texte);// (2) /////////////////////////////////////////////////////////////////////////////// //////////////////////////// Affichage des lignes. ////////////////////////////      for (i=(((noeud*)courant.enfants[0])->hauteur-1)/2;i<courant.hauteur-((noeud*)courant.enfants[courant.nbenfants-1])->hauteur/2;i++)           printXY(x,y+i,(char*)"|");      printXY(x,ycourant,(char*)"+"); //////////////////////// Affichage des noeuds enfants. ////////////////////////      for (i=0;i<courant.nbenfants;i++)           DessineNoeud(*(noeud*)(courant.enfants[i]),x+1,y),           y+=((noeud*)(courant.enfants[i]))->hauteur+1; } void DessineArbre(noeud *racine) {      printf("\33[s");      InitHauteur(racine);      DessineNoeud(*racine,1,0); } void main(void) {      noeud racine;      (...)      DessineArbre(&racine);      (...) }

...et ça c'est la version intermédiaire, la meilleure à mon avis

Bon je test ca et je te le dis. Pour les performances, peu importe.

Thepro> pkoi void * et pas struct noeud * ?

Pourquoi pas ...

pour ne pas rajouter des casts inutiles peut-être ?

Bah, ça ne change que pour parent (que je n'utilise pas).

euuuh

for (i=(((noeud*)
courant.enfants[0])->hauteur-1)/2;i<courant.hauteur-((noeud*)courant.enfants[courant.nbenfants-1])->hauteur/2;i++)
printXY(x,y+i,(char*)"|");
printXY(x,ycourant,(char*)"+");

//////////////////////// Affichage des noeuds enfants. ////////////////////////
for (i=0;i<courant.nbenfants;i++)
DessineNoeud(*(noeud*)(courant.enfants[i]),x+1,y),
y+=((noeud*)(courant.enfants[i]))->hauteur+1;

Aucun de ces casts n'est utile (et en plus ça t'oblige à rajouter des parenthèses supplémentaires, puisque tu peux pas faire machin->hauteur mais seulement ((noeud *)machin)->hauteur)

Pareil pour tous les casts vers char*, d'ailleurs : la solution propre serait de déclarer l'argument de printXY comme un const char *...

Thepro est un pro du cast

Avec :

typedef struct {char *texte;int nbenfants,hauteur;struct noeud *parent, **enfants;} noeud;

Dans :

for (i=(courant.enfants[
0]->hauteur-1)/2;i<courant.hauteur-courant.enfants[courant.nbenfants-1]->hauteur/2;i++)

J'ai 2 erreurs : Dereferencing pointer to incomplete type.

Oui, parce que pour le compilateur "struct noeud" n'est pas défini : il faut faire "typedef struct noeud { ... } noeud;"...

("struct noeud" et le type "noeud" n'ont, pour le compilateur, a priori rien à voir... et pour une déclaration récursive tu es obligé de passer par "struct noeud")

Encore une nouvelle version (plus joli)
Merci pour vos conseils
[source=]

De toute facon ce qui compte, c'est l'algo. Pas les détails de ce genre.

cest ou deja les trucs qui permettent d'utiliser les features du printf ansi? du stye %dC etc..

%dtc () sinon je comprends pas trop ce que tu demandes, tu veux savoir les codes disponibles? man 3 printf

http://www.linux-france.org/article/man-fr/man3/printf-3.html

Tu peux trouver des infos là : http://forum.cppfrance.com/code.aspx?ID=

Peut-être que la ligne "printf("\33[u;%dB;%dC%s",y,x,texte);" doit être remplacée par "printf("\33[u\33[%dB\33[%dC%s",y,x,texte);"

je m'étais jamais rendu compte du niveau de moisissure des commentaires sur les *france.com

Bon sans les déplacements de curseur foireux... ca donne ca:

void CNoeud::Afficher(char *S,char *SD,char *SG){
	char str1[300];
	char str2[300];
	char str3[300];
	char Ind[300];
	unsigned int i,j;
	for (i=0;i<strlen(ImageNoeud());i++)
		Ind[i]=32;
	Ind[i]=0;
	
	sprintf(str1,"%s%s     ",SD,Ind);
	sprintf(str2,"%s%s      ",SD,Ind);
	sprintf(str3,"%s%s     |",SD,Ind);
	if (mFilsD)
		mFilsD->Afficher(str1,str2,str3);
	
	for(j=0;j<30 && !Successeur[j];j++);

	if (mFilsD==NULL && mFilsG==NULL && j==30)
		printf("%s+-<%s >\n",S,ImageNoeud());
	else if (j<30)
		printf("%s+-<%s >-,\n",S,ImageNoeud());
	else
		printf("%s+-<%s >-|\n",S,ImageNoeud());
	

	sprintf(str1,"%s%s     ",SG,Ind);
	sprintf(str2,"%s%s     |",SG,Ind);
	sprintf(str3,"%s%s      ",SG,Ind);	
	if (mFilsG)
		mFilsG->Afficher(str1,str2,str3);

	for(j=0;j<30;j++)
	{
		if (Successeur[j])
		{
			sprintf(str2,"%s%s     |",SG,Ind);
			sprintf(str3,"%s%s     |",SD,Ind);
			Successeur[j]->Afficher(str1,str2,str3);
		}
	}
}

avec un départ:

void CNoeud::Afficher(){
	Afficher(""," "," ");
}

ImageNoeud est une fonction membre de la classe qui renvoi un char * qui contient l'information du noeud this
Merci quand meme Thepro