[C] Massimo Elemento In Un Albero Binario

[xbubbax]

int Massimo(int x, tree T)
{
if(T!=NULL)
{
Massimo(x,T->SX);

if(T->DATO>x)
{
x=T->DATO;
}

Massimo(x,T->DX);
}
}

Come mai questo esercizio mi restituisce sempre il massimo degli elementi del sottoalbero destro e non di tutto l'albero?

Naturalmente la x all'inizio quando si entra nella funzione viene messa a 0

[xbubbax]

ho dimenticato di mettere "return x" ma non penso che cambi il risultato

[banryu79]

int Massimo(int x, tree T)
{
if(T!=NULL)
{
Massimo(x,T->SX);

if(T->DATO>x)
{
x=T->DATO;
}

Massimo(x,T->DX);
}
}


Credo che l'errore stia nel fatto che tu entri ricorsivamente nel sottoalbero di sinistra, e ad ogni nuova chiamata continui a passare tale sottoalbero finchè esso è != NULL.
Quando arrivi alla fine del ramo sinitro e non c'è più alcun sottoalbero non si verifica la condizone if(T!=NULL) e quindi la funzione ricorsiva ritorna alla chiamante precedente e così via fino a tornare nel contesto della prima invocazione (in grasetto nel codice).

A quel punto hai esaminato tutto il ramo di sinitra ma non hai ancora mai eseguito nessun controllo sul valore del dato rispetto a x; cominci a farlo solo subito dopo con

...
f(T->DATO>x)
{
x=T->DATO;
}
...

e quindi a questo punto memorizzi il primo valore "di sinistra" che trovi, per poi cominciare la serie di chiamate ricorsive ai sottoalberi di destra:

...
Massimo(x,T->DX);

dove, durante l'esecuzione di ogni chiamata viene finalmente eseguito il codice
che confronta il DATO contenuto con x e, se maggiore, lo memorizza in x.

[xbubbax]

è possibile correggerlo oppure è sbagliato proprio l'approccio a questo esercizio?

perchè una volta il prof lo fece in un modo molto piu complicato, ovvero facendo la #define, definendo una funzione che prendeva 3 interi e ne calcolava il maggiore..

[gugoXX]

è possibile correggerlo oppure è sbagliato proprio l'approccio a questo esercizio?

perchè una volta il prof lo fece in un modo molto piu complicato, ovvero facendo la #define, definendo una funzione che prendeva 3 interi e ne calcolava il maggiore..

Si puo' correggere, certo.
Io proverei cosi'.


int Massimo(int x, tree T)
{
int ret=-1; (-infinito se i valori possono essere negativi)
if(T!=NULL)
{
int sinistro = Massimo(x,T->SX);
int centro = t->DATO;
int destro = Massimo(x, t->DX);

ret=max(sinistro,centro);
ret=max(ret,destro);
}
return ret;
}


Ma appunto con la funzione che restituisce il massimo di 3 valori.

[khelidan1980]

int Massimo(int x, tree T)
{
if(T!=NULL)
{
Massimo(x,T->SX);

if(T->DATO>x)
{
x=T->DATO;
}

Massimo(x,T->DX);
}
}


Credo che l'errore stia nel fatto che tu entri ricorsivamente nel sottoalbero di sinistra, e ad ogni nuova chiamata continui a passare tale sottoalbero finchè esso è != NULL.
Quando arrivi alla fine del ramo sinitro e non c'è più alcun sottoalbero non si verifica la condizone if(T!=NULL) e quindi la funzione ricorsiva ritorna alla chiamante precedente e così via fino a tornare nel contesto della prima invocazione (in grasetto nel codice).



ma quanto l'ultima chiamata ricorsiva ritorna alla precedente perchè ha trovato un puntatore null,dovrebbe poi continuare valutando il dato della foglia,e poi passare sul sottoalbero destro della foglia,che trova null e così via come in una normale visita simmetrica,secondo me,volendo mantenere questa impostazione, risolverebbe usando x come variabile globale