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;

2
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).
avatarMembre de la TI-Chess Team.
Co-mainteneur de GCC4TI (documentation en ligne de GCC4TI), TIEmu et TILP.
Co-admin de TI-Planet.
3
oui mais c'est un livre ca. Et ca coute 29€ fou
4
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 grin


ps: tu trouveras plein d'algos de parcours en largeur d'arbre sur le net...
5
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 smile
6
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...
avatarMaintenant j'ai la flemme de garder une signature à jour sur ce site. Je n'ai même plus ma chaîne Exec sous la main.
7
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...

8
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.
9
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.
avatar
Voilà une façon d'afficher un arbre que j'ai codé en 3 minutes, je n'ai pas testé wink
[source=]
avatar
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 wink que je n'ai toujours pas testé grin ////////////////////////// © 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);      (...) }
avatar
...et ça c'est la version intermédiaire, la meilleure à mon avis smile
Bon je test ca et je te le dis. Pour les performances, peu importe.
Thepro> pkoi void * et pas struct noeud * ? confus
Pourquoi pas ...
avatar
pour ne pas rajouter des casts inutiles peut-être ? cheeky
Bah, ça ne change que pour parent (que je n'utilise pas).
avatar
euuuh hum
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 *...
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.
avatar
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) grin
Merci pour vos conseils wink
[source=]
avatar
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 (grin) 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);"
avatar
je m'étais jamais rendu compte du niveau de moisissure des commentaires sur les *france.com sick
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 wink