visita albero n-ario in C

[Brendon77]

... anche io penso che ti siano arrivati suggerimenti più che validi per il problema che hai posto...

[streuso83]

ci sbatto la testa da tre giorni e non riesco...le visite preordine postordine etc funzionano ma a me non serve questo. devo far stampare tutti i percorsi radice foglia...a partire dal primo 3 in alto a sx.
valerio

[Brendon77]

... dall'immagine che hai allegato manca la ROOT o mi sbaglio :master: ?

..dovrebbe esserci la radice principale che poi avrà i vari figli.

...a parte questo, l'esercizio (a mio parere) trova risoluzione sempre negli algoritmi delle visite.

Quando studiavo all'università, mi capitavano spesso di questi esercizi, quello che devi fare è capire bene la struttura e i relativi algoritmi....

io risolvevo problemi del genere modificando gli algoritmi di visita.....

.. usavo sia per gli alberi n-ari che binari gli algoritmi ricorsivi.... una volta che capisci la logica e fai qualche prova il gioco è fatto!!!

non so che altro dirti

[streuso83]

anch'io penso che si debba modificare gli algoritmi di visita...ma non riesco a capire come faccio a tener traccia dei nodi "genitori". considera che la root è il nodo in alto a sx.

[Brendon77]

scusa... ma se la root è il nodo in alto a sinistra... come mai ha dei fratelli ?

[Brendon77]

.. per tener traccia dei genitori puoi agigungere un campo Parent al nodo....

[sebaldar]

prova in questa maniera, purtroppo senza inserire nella struttura il nodo padre con questo sistema non è possibile stamparlo all'inizio della riga.

#include <stdio.h>

struct nodo {

	int inf;
	struct nodo *figlio;
	struct nodo *fratello;

};

struct nodo * addFratello ( struct nodo *n, int value )
{

	struct nodo *n1 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n1->inf=value;
	n1->figlio=NULL;
	n1->fratello=NULL;

	do  {
		if ( !n->fratello ) 
			return n->fratello=n1;
	} while ( n=n->fratello );

};


struct nodo * addFiglio ( struct nodo *n, int value )
{

	struct nodo *n1 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n1->inf=value;
	n1->figlio=NULL;
	n1->fratello=NULL;

	do  {
		if ( !n->figlio )
			return n->figlio=n1;
	} while ( n=n->figlio );

};


void printNodo ( const struct nodo * n )
{

	if ( n ) {

		printf ( "%d", n->inf );
		
		if ( n->figlio )
			printNodo ( n->figlio ) ;
		else
			printf ( "\n" );
		
		if ( n->fratello )
			printNodo ( n->fratello ) ;

	}
	
}

int main () 
{


	struct nodo *n00 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n00->inf = 3;

	struct nodo *n02 = addFratello(n00, 2); 
	struct nodo *n05 = addFratello(n00, 1); 

	struct nodo *n10 = addFiglio (n00, 3); 
	struct nodo *n11 = addFratello (n10, 1); 
	addFiglio (n11, 1); 
	addFiglio (n11, 1); 

	struct nodo *n12 = addFiglio (n02, 2); 
	struct nodo *n14 = addFratello(n12, 1); 
	addFiglio (n14, 1); 
	addFiglio (n14, 1); 
	addFiglio (n14, 1); 

	struct nodo *n22 = addFiglio (n02, 2); 
	struct nodo *n33 = addFratello(n22, 1); 
	addFiglio (n33, 1); 

	addFiglio (n05, 1); 
	addFiglio (n05, 1); 
	addFiglio (n05, 1); 
	addFiglio (n05, 1); 
	addFiglio (n05, 1); 

	printNodo(n00);
	return (0);
}

[streuso83]

buongiorno,
grazie dell'aiuto. mi rendo conto che forse più che un albero vero e proprio è una lista di liste..Ho provato con il listato precedente solo che non stampa tutti i cammini..nel senso che stampa 33 e poi dovrebbe stampare 3111 e invece stampa 111 etc . Vi posto un codice un po incasinato che ho scritto che mi stampa i risultati salvo poi bloccarsi non so perchè. In pratica visito un nodo con il primo figlio, cancello il figlio e se c'è gli assegno l'altro figlio. Ecco il codice:

void *visualizzaAlbero(struct nodo *radice){
struct nodo *radix=radice,*r1,*r2,*r3;
while (radice){
r1=radice;
while (r1->figlio!=NULL){
printf("%d ",r1->inf);
r1=r1->figlio;
}
printf("%d\n",r1->inf);
r3=radice;
while (r3->figlio!=NULL){
r1=r3;
while (r1->figlio!=NULL){
r2=r1;
r1=r1->figlio;
}
if (r1->fratello==NULL){
free(r1);
r2->figlio=NULL;
}else{
r2->figlio=r1->fratello;
free(r1);
visualizzaAlbero(radice);
}
}
r1=radice;
radice=radice->fratello;
free(r1);
}
}

[sebaldar]

bè, ma ti è stato detto. :master:
Per ottenere la stampa che vuoi tu devi aggiungere alla struttura il membro "genitore"

struct nodo {

	int inf;
	struct nodo *figlio;
	struct nodo *fratello;

	struct nodo *genitore;

};

modifiche le funzioni di inserimento in questo modo

struct nodo * addFratello ( struct nodo *n, int value )
{

	struct nodo *n1 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n1->inf=value;
	n1->figlio=NULL;
	n1->fratello=NULL;

	n1->genitore=n->genitore;

	do  {
		if ( !n->fratello ) 
			return n->fratello=n1;
	} while ( n=n->fratello );

};


struct nodo * addFiglio ( struct nodo *n, int value )
{

	struct nodo *n1 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n1->inf=value;
	n1->figlio=NULL;
	n1->fratello=NULL;

	n1->genitore=n;

	do  {
		if ( !n->figlio ) 
			return n->figlio=n1;
	} while ( n=n->figlio );

};

quando crei il nodo radice imposti il suo genitore a NULL
eventualmente aggiugi una funzione

struct nodo * creaRoot ( struct nodo *n, int value )
{

	struct nodo *n1 = ( struct nodo *) malloc ( sizeof(struct nodo) );
	n1->inf=value;
	n1->figlio=NULL;
	n1->fratello=NULL;

	n1->genitore=NULL;

	return ( n1 );


};

ed infine modifichi la stampa in questo modo

void printNodo ( const struct nodo * n )
{

	if ( n ) {

		printf ( "%d", n->inf );
		
		if ( n->figlio )
			printNodo ( n->figlio ) ;
		else {

			printf ( "\n" );

struct nodo * p = n->parent;
while ( p ) {
  printf ( "%d", p->inf );
  p=p->parent;
}

		};

		
		if ( n->fratello )
			printNodo ( n->fratello ) ;

	}
	
}