[C]trovare il minimo in un albero binario semplice

[mame83]

Ciao a tutti. Ho il seguente problema : devo cercare in un albero binario semplice(cioè non di ricerca)l elemento piu piccolo utilizzando una funzione ricorsiva.


int minimo(nod *radice, int conf)
{
int min1,min2;
if (radice!=NULL)
{
if(radice->info<conf)
conf=radice->info;
min1=minimo(radice->sinistro,conf);
min2=minimo(radice->destro,conf);
if (min1>min2)
return min1;
else
return min2;
}
}


Dove conf inizializzo ad un valore piu grande che non potrei mai inserire nell albero.
MIN1 e MIN2 sono due variabili che dovrebbero memorizzare il minimo di sinistro e il minimo di destra. Li confronto e il valore piu piccolo sarà il minimo dell albero.
INVECE la funzione mi restitutisce un valore sballato.
Spero che qualcuno mi aiuti grazie

[mame83]

:mc: non so piu che fare. vi prego aiutatemi!!!!!

[sottovento]

if (min1>min2)
return min1;
else
return min2;





Qui ritorni il massimo. Ad ogni modo ti consiglio di rivedere l'algoritmo

[mame83]

Qui ritorni il massimo. Ad ogni modo ti consiglio di rivedere l'algoritmo

si va be ho sbagliato a mettere segno. ma non va lo stesso....grazie per la tuo aiuto geniale..........ripeto GENIALE...... ma va va

[clockover]

L'algoritmo che hai fatto è fatto molto male.
Dai una condizione if, ma non ritorni nulla nel caso non si verifichi la condizione.

così al volo potresti fare una cosa del tipo
int minimo(node *nd){
int min = nd.val;
se nd è foglia
return min
int tmp = 0;
//qui meglio distinguere alcuni casi
if ha entrambi i figli
int left = minimo(nd->left);
int right = minimo(nd->right);
tmp = valore più piccolo tra left e right
else se ha solo figlio sinistro
tmp = minimo(nd->left)
else
tmp = minimo(nd->right)
return valore più piccolo tra tmp e min

dato ch manca un passo base all'inizio della funzione ricorsiva ti consiglio di fare una cosa del genere
int mini(node *nd){
if(nd == NULL)vedi te che vuoi ritornare
else return minimo(nd);
}
sembra non bello a vedersi ma in questo modo controlli subito la radice dell'albero senza aver bisogno di un passo base all'inizio della funzione minimo. Infatti non hai mai problemi nella funzione minimo di richiamare un nodo NULL dato che effettui sempre dei controlli prima di fare una chiamata...

Il codice non l'ho provato ma dovrebbe funzionare

ps
tratta bene chi ti risponde anche se le risposte possono essere un po scontate... anche perchè è stato l'unico che ti ha risposto ed è stato anche quello che ti ha detto di riguardare il codice dato che comunque era sbagliato

[sottovento]

si va be ho sbagliato a mettere segno. ma non va lo stesso....grazie per la tuo aiuto geniale..........ripeto GENIALE...... ma va va

Sempre un piacere avere a che fare con gente gentile..... ripeto GENTILE .... cerca almeno di capire cosa manca:


int minimo (node *nd)
{
int l,r,m;
return (nd==NULL)?maxint:(((m=(((l=minimo(nd->left))<(r=minimo(nd->right)))?l:r)) < nd->radice) ? m : nd->radice);
}

[mame83]

questo messaggio è per tutti. Il codice l ho visto è rivisto tantissime volte senza riuscire a risolvere nulla. Quindi ho deciso di chiedere aiuto, se quindi ricevo come risposta di rivedere il codice è ovvio che una persona si arrabbia (senza offendere nessuno).

[sottovento]

questo messaggio è per tutti. Il codice l ho visto è rivisto tantissime volte senza riuscire a risolvere nulla. Quindi ho deciso di chiedere aiuto, se quindi ricevo come risposta di rivedere il codice è ovvio che una persona si arrabbia (senza offendere nessuno).

Ok, dai... abbiamo sbagliato entrambi :D

Mio suggerimento:

1 - caso base: nd == NULL. Evita altri casi, altrimenti il codice diventa troppo lungo. Nel caso base ritorni il massimo intero disponibile

2 - se non e' il caso base:
2.1 - chiama ricorsivamente il minimo sul nodo sinistro (non hai bisogno di controllare che sia NULL) e memorizza il risultato nella variabile intera left;
2.2 - chiama ricorsivamente il minimo sul nodo destro e memorizza in right;
2.3 - ritorna il minimo fra left, right ed il contenuto della radice.

le variabili locali ti servono perche' si tratta di un minimo fra tre variabili, che effettuerai a due a due (confronti i primi due elementi, ed il risultato con il terzo).

[clockover]

1 - caso base: nd == NULL. Evita altri casi, altrimenti il codice diventa troppo lungo. Nel caso base ritorni il massimo intero disponibile


il fatto è proprio questo... che valori ritorneresti se si verifica il caso base?
se entri nella funzione
int minimo(nodo *p){
if(p == NULL)return cosa?
......resto.....
}

infatti nella mia versione dell'algoritmo ho eliminato il caso base proprio per questo motivo

[sottovento]

il fatto è proprio questo... che valori ritorneresti se si verifica il caso base?
se entri nella funzione
int minimo(nodo *p){
if(p == NULL)return cosa?
......resto.....
}

infatti nella mia versione dell'algoritmo ho eliminato il caso base proprio per questo motivo

Ho proposto di ritornare il massimo intero disponibile. La costante opportuna dovrebbe trovarsi in limit.h

Nel caso non ti piaccia come soluzione (si, lo so, non ti piace :D ) si puo' pensare come condizione iniziale che l'utente NON ti dia un albero vuoto (ci deve essere almeno un nodo) e questo deve essere testato prima di chiamare la funzione ricorsiva.

Dopo di che:
1 - caso base: il nodo e' una foglia (i.e. entrambi i sottoalberi sono NULL).
in tal caso, il minimo e' l'informazione contenuta nella radice.

2 - se il nodo sx non e' NULL,
2.1 - chiama ricorsivamente il minimo() e memorizza il risultato in left;
2.2 - calcola il minimo fra left ed la radice e memorizzalo in res_sx;
Se il nodo sx e' NULL allora res_sx = radice;

3 - se il nodo dx non e' NULL,
3.1 - chiama ricorsivamente minimo() e memorizza il risultato in right;
3.2 - calcola il minimo fra right e la radice e memorizzalo in res_dx;
Se il nodo dx e' NULL allora res_dx = radice;

4 - ritorna il minimo fra res_dx e res_sx;

Mi piace di piu' ritornare il massimo intero ;)

[clockover]

Nel caso non ti piaccia come soluzione (si, lo so, non ti piace :D ) Già :D :D :D

Comunque il risultato è identico! Più che altro io ho puntato al fatto che fare delle chiamate ricorsive costa più che qualche if - else

[mame83]

ho provato a farlo cosi mi sembra che funzioni

int min(int a, int b, int c)
{
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

int tree_min(nod *radice)
{
/* arrivati alla fine */
if (radice == NULL)
return max;

/* nodo foglia */
if (radice->sinistro==NULL && radice->destro==NULL)
return radice->info;

return min(tree_min(radice->sinistro),tree_min(radice->destro),radice->info);
}


dove max è una costante preinizializzata.
calcolo il minimo dal basso verso l alto tra sinistro destro e radice.
Che ne pensate???

[sottovento]

ho provato a farlo cosi mi sembra che funzioni

int min(int a, int b, int c)
{
return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

int tree_min(nod *radice)
{
/* arrivati alla fine */
if (radice == NULL)
return max;

/* nodo foglia */
if (radice->sinistro==NULL && radice->destro==NULL)
return radice->info;

return min(tree_min(radice->sinistro),tree_min(radice->destro),radice->info);
}


dove max è una costante preinizializzata.
calcolo il minimo dal basso verso l alto tra sinistro destro e radice.
Che ne pensate???

Ne penso bene ;)
Volendo puoi anche eliminare il controllo del nodo foglia, e' gia' fatto nella ricorsione