Aiutino di C...

[marcus81]

Dunque devo implementare in C una procedura così definita:

void MinMaxPath(Tree *ptr, int *max, int *min)

questa funzione dato un albero binario deve calcolare la lunghezza minima e massima tra tutti i possibili percorsi radice-foglie e deve restituire i valori trovati...
Help me...thank you...

[marcus81]

nessuno??:confused:

[cionci]

Bella questa roba ricorsiva !!!!
Premetto che lo scriverò in C++, anche se probabilmente non dovrai fare nulla per adattarlo...

void MinMaxPath(Tree *t, int *min, int *max)
{
int minDx, minSx, maxDx, maxSx;
minDx = minSx = maxDx = maxSx = 0;
if(!t) {
*max = 0;
*min = 0;
return;
}
if(t->dx) MinMaxPath(t->dx, &minDx, &maxDx);
if(t->sx) MinMaxPath(t->sx, &minSx, &maxSx);
*min = (minDx < minSx) ? minDx : minSx;
*max = (maxDx > maxSx) ? maxDx : maxSx;
++(*min);
++(*max);
}

Non l'ho provato, ma dovrebbe andare bene...

[marcus81]

Non è che potresti mettere qualche commentino...soprattutto quella condizione (!t)...grazie

[cionci]

!t significa che ti hanno passato un albero vuoto (il puntatore vuoto è NULL cioè 0), quindi !t significa se l'albero è vuoto...

Stessa cosa per if(t->dx) e if(t->sx) esegue quella chiamato solo i puntatori ai figli di sinistra e di destra contengono un elemento...

Quegli if potrebero essere omessi, anzi nella forma canonica della ricorsione andrebbero omessi perchè la condizione d'arresto è if(!t) iniziale... Ce l'ho messi perchè, visto che in ogni chiamata si spreca heap, risparmiare un po' di risorse ed essere + veloci...

Infatti se omettevo i due if avrebbe pensato la condizione di arresto a ritornare valori comunque validi per la nostra ricorsione...

In questo modo la condizione di arresto non può comunque essere omessa perchè se ti passano un albero vuoto dobbiamo comunque ritornare 0 e 0...

Ti insegno il trucco per le ricorsione...non pensare a come deve funzionare il problema globalmente altirmenti non riuscirai mai a scrivere la ricorsione.

Inizia con la condizione di arresto che in tutti i casi deve essere presente (solitamente si controlla se il puntatore passato è vuoto)...

Dopo passa al nodo/elemento precedente a quello di aresto e scrivi come dovrebbe lavorare la funzione con quell'elemento che riceve i risultati dal/dagli elemento/i nulli...

A questo punto hai già finito...

Fai una prova con due elementi per le liste e con un albero assimmetrico con due elemnti per gli alberi binari (una radice con un solo figlio)...ed ecco finito tutto !!!

[marcus81]

Scusa ma ke vuol dire questo:
"Dopo passa al nodo/elemento precedente a quello di aresto e scrivi come dovrebbe lavorare la funzione con quell'elemento che riceve i risultati dal/dagli elemento/i nulli..."
Non capisco cosa vuol dir "...l'elemento che riceve i risultati dagli elementi nulli"...
Potresti spiegarti un pò meglio??Grazie mille.

[cionci]

Una volta scritta la condizione di arresto...passi a scrivere quello che deve fare la funzione nel caso più semplice...ovvero quello di un solo elemento...e richiamando la funzione sul successivo elemento (o sui successivi nel caso di una labero) anche se sai che è nullo... Questo ti può essere utile anche per stabilire i valori precisi che ti deve ritornaer la condizione di arresto...

Verifichi che il codice da te scritto si comporti nel modo giusto....e poi passi ad un caso più generale in cui non conosci i valori che ti ritornano le ricorsioni...e controlli che la funzione si comporti sempre nel modo giusto...

Comunque non pensare mai in modo GLOBALE...pensa solo ad un elemento nullo, un solo elemento...oppure ad un elemento generico...

Se epnsi in modo GLOBALE al problema è difficilissimo risucire a trovare il codice giusto...

[cionci]

Avevo fatto un errore di confusione sul secondo post...

!t significa se l'albero è vuoto (non "non è vuoto" come avevo scritto prima)...

[marcus81]

Cionci: la funziona l'ho provata in un programma completo...ha un problema: praticamente restituisce sia l'altezza minima ke quella massima maggiorate di uno...cosa dovrei aggiungere??Grazie.

[cionci]

Sì ? Mmmhh strano... Io non l'ho provata...magari ci faccio qualche prova...

[cionci]

Originariamente inviato da marcus81
[B]Cionci: la funziona l'ho provata in un programma completo...ha un problema: praticamente restituisce sia l'altezza minima ke quella massima maggiorate di uno...cosa dovrei aggiungere??Grazie.
Fammi un esempio...con un nodo solo...quanto mi deve ritornare la funzione ? 1 o 0 ?

[marcus81]

con un nodo solo, cioè con la sola radice deve restituire 0...

[marcus81]

Se vuoi ti allego il programma completo e gli dai un occhiata...

[cionci]

Nono....l'ho già fatto...

Io avevo capito che dovevo calcolare la profondità minima e massima dell'albero...comunque basta poco per modificarlo...

Prova così se ti torna...

void MinMaxPath(Tree *t, int *min, int *max)
{
int minDx, minSx, maxDx, maxSx;
minDx = minSx = maxDx = maxSx = 0;
if(!t||(!t->dx && !t->sx)) { //ho modificato qui
*max = 0;
*min = 0;
return;
}
if(t->dx) MinMaxPath(t->dx, &minDx, &maxDx);
if(t->sx) MinMaxPath(t->sx, &minSx, &maxSx);
*min = (minDx < minSx) ? minDx : minSx;
*max = (maxDx > maxSx) ? maxDx : maxSx;
++(*min);
++(*max);
}

[cionci]

In pratica ne conta uno in meno perchè non conta le foglie ;)

Questi esercizi erano la mia passione !!! Si vede ? :)

[marcus81]

ti ringrazio molto...adesso lo provo...ma tu che fai nella vita??

[cionci]

Studio (poco) ingegneria informatica...quindi sono ovviamente progammatore...

Poi sono anche webmaster e faccio siti web...

[marcus81]

Io faccio informatica e questo è il mio primo linguaggio di programmazione...

[cionci]

Che ti sembra ? Bello il C, vero ? E il C++ è anche più bello !!!

[cionci]

Ci vediamo...vado a pappare...

[marcus81]

soprattutto potente!