int minimo(int min, Tree T)
{ if (T!=null)
{ min = minimo(min,T.leftchild);
if(min>T.element) min = T.element;
min = minimo(min,T.rightchild);
}
return min;
}
Questo algoritmo trova ricorsivamente il minimo in un albero binario?
Qualcuno mi saprebbe dare una soluzione (se esiste) a partire dalla signature
int minimo(Tree T) ?
P.s.: albero binario normale e tree è un nodo con due puntatori e l'elemento.
L'ho scritto di getto direttamente nel browser ma penso che la soluzione sia questacodice:int minimo(Tree T) { int min_left,min_right,min; if (T!=NULL) { min_left=minimo(T.leftchild); min_right=minimo(T.rightchild); min=T.info; if (min_left<min) min=min_left; if (min_right<min) min=min_right; return min; } else return INT_MAX; }
Si ok era come l'avevo immaginato good.Originariamente inviato da doraemon83
L'ho scritto di getto direttamente nel browser ma penso che la soluzione sia questacodice:int minimo(Tree T) { int min_left,min_right,min; if (T!=NULL) { min_left=minimo(T.leftchild); min_right=minimo(T.rightchild); min=T.info; if (min_left<min) min=min_left; if (min_right<min) min=min_right; return min; } else return INT_MAX; }
Quello che ho scritto io va bene cmq?
E un'altra curiosità...cos'è quell INT_MAX? Restituisce 32milaecc..??
da una prima occhiata sembrerebbe di si, ma nn posso darti certezza, non l'ho provato. Il modo migliore per verificare se una soluzione funziona è quello di testarlo in un tuo programma.
Per INT_MAX essa è una costante definita se non sbaglio in stdlib.h (non vorrei sbagliare) che rappresenta il massimo intero rappresentabile sulla tua macchina (di solito è 32768 o giu di li )
Io credo che non funzioni (anche se non l'ho provata) e ti spiego il perchè:
Il valore min dovresti portartelo dietro per riferimento, altrimenti, min non cambia valore definitivamente, e quando la ricorsione va a ritroso, min assume i valori che aveva nelle chiamate precedenti "perdendo il valore minimo"
P.S Ovviamente sto parlando del primo codice, quell'altro ad occhio, non mi piace tanto quell'assegnamento min = T.info, penso che in questo modo il min te lo perdi in ogni ciclo ricorsivo e ti restituisce sempre la radice, ma di questo non sono sicuro, potrei sbagliarmi!!!
si e vero il min te lo perdi, perche ogni volta gli assegni T.info (che puo contentere un valore qualunque), un consiglio: di solito le variabili si inizializzano fuori dalle funzioni ricorsive oppure come in questo caso " fuori dall'if, cioè dentro la else".
saluti
Qualcuno mi sa dare info a riguardo?Originariamente inviato da giudf
Il valore min dovresti portartelo dietro per riferimento, altrimenti, min non cambia valore definitivamente, e quando la ricorsione va a ritroso, min assume i valori che aveva nelle chiamate precedenti "perdendo il valore minimo"
P.s.: sinceramente non credevo fosse tanto complicato fare un algoritmo del genere... ma mai nessuno l'ha fatto? università,..per perdere tempo... niente?
Senza provarlo sembra che funzioni (cioè non si perdono valori)
se il min. non è stato trovato nel sotto albero sinistro o in quello destro la funzione ricorsiva ritorna come valore min quello che gli era stato passato come parametro altrimenti gli ritorna quello modificato
penso che sia importante solo inizializzare min alla prima chiamata della funzione minimo (..,..)con il valore della radice dell'albero
dunque il principio secondo cui ho scritto quel codice è il seguente :
suppongo che ogni sottoalbero restituisce il proprio minimo, per cui tramite le chiamate ricorsive ottengo min_left e min_right (che vengono restituiti tramite i return)
Supponendo quindi di avere i minimi dei sottoalberi, il minimo dell'albero è dato dal valore piu piccolo tra il valore della radice e i minimi dei sottoalberi, per cui mi basta fare i confronti. se fate caso al codice, ho scritto :
min=T.info //Per prima cosa suppongo che la radice abbia il minimo
if (min_left<min) //Controllo che il minimo del sottoalbero sinistro sia minore della radice
min=min_left; //se è vero allora min_left è il nuovo minimo
if (min_right<min) //Controllo che il minimo del sottoalbero destro sia minore del minimo di prima
min=min_right; //se è vero allora min_right è il nuovo minimo
//Sei due controlli danno false entrambi allora il minimo è nella radice, quindi è gia in min
return min; //Ritorno il valore minimo trovato, che alle chiamate precedenti sarà assegnato a min_left o a min_right
Nel caso T sia NULL (cioè sono in una foglia) ritorno INT_MAX, che verrà assegnato a min_right o a min_left, per cui i controlli daranno sicuro un true.
Anche se min è una variabile locale, essa viene ritornata alle chiamate precedenti tramite il return, quindi il suo valore non è perduto, ma assegnato a min_left e min_right. Quello che dite voi è il motivo per cui faccio prima le chiamate ricorsive e poi i controlli, in modo tale da avere i valori aggiornati quando si comincia a far backtracking.
Scusate se mi sono dilungato, ma spero di essere stato chiaro. ciao ciao
Scusate se mi intrometto...volevo sapere che tipo di albero è. Mi spiego, mi sembra
di ricordare dai miei lontani anni in Università che un albero viene implicitamente ordinato,
in quanto la posizione dove aggiungere il nuovo nodo la trovo con un confronto tra il
valore da inserire e il valore del nodo corrente: se è minore lo aggiungo a sx altrimenti a
dx.
Se è così allora il valore minimo non dovrebbe essere semplicemente il valore del child
più a sinistra dell'albero?
Non si potrebbe cioè usare il codice:
Magari si potrebbe anche evitare la ricorsione con:codice:int minimo(Tree *T) { if( !T ) return MAX_INT; if( T->leftchild ) return minimo(T->leftchild); else return T->info; }
Ho ovviamente supposto un albero definito così:codice:int minimo_nr(Tree *T) { if( !T ) return MAX_INT; while( T->leftchild ) T = T->leftchild; return T->info; }
Se così non fosse allora non ho capito nulla (e quindi i miei ricordi si sono sbiaditi col tempo) e quindi fate finta che non abbia scritto niente.codice:struct Tree { int info; Tree *leftchild; Tree *rightchild; };
Permessi di invio
Rispondi quotando