[C]funzione verificare se un albero binario è un abr

[mame83]

Ciao a tutti ho il seguente problema : dato un albero binario devo scrivere una funzione ricorsiva che restituisce 0 se l albero è un ABR , 1 se non lo è.
La soluzione che avevo pensato ma non riesco ad applicare è quella di utilizzare la visita in ordine e verificare se la successione è crescente. Quindi utilizzando una funzione dove gli passerò due parametri var1 e var2 e verifico di chiamata in chiamata se var1 è minore o uguale di var2 appena var1 è maggiore di var2 dovrei uscire e ritornare 1 se no vado avanti.

Spero di essere stato chiaro nell esposizione del problema e che qualcuno mi aiuti GRAZIE!!!!!!!!


int ABR(nod *radice, int *b)/*0 se è un abr, 1 se non lo è*/
{
int confronto;
if (radice!=NULL)
{
confronto=ABR(radice->sinistro,&(radice->info));
printf("valore di radice e' %d \n",radice->info);
printf("valore di b e' %d \n",*b);
if (radice->info>(*b))
return 1;/*dobbiamo uscire visto che il precedente è minore del successivo*/
else
confronto=0; /*vado avanti*/
confronto=ABR(radice->destro,&(radice->info));
}
return confronto;

}



B lo inizializzo nel main con un valore piu grande che non posso mai inserire nell albero.

[mame83]

:mc: ragazzi vi prego aiutatemi!!!!!!!

[mame83]

in output mi restituisce sempre 1 anke quando è un abr. qualcuno mi sa aiutare:mc:

[Floris]

class node{
public:
int info;
node* first;
node* second;
node(int i,node* f, node* s):info(i),first(f),second(s){}
};

bool testNode(node* n){
bool isOk = true;
if(n->first!=0)
isOk = n->first->info <= n->info;
if(n->second!=0)
isOk = isOk && n->info <= n->second->info;
return isOk;
}

bool testABR(node* root){
if(root == 0) return true;
return testNode(root) && testABR(root->first) && testABR(root->second);
}

Credo che nel tuo codice l'errore sia alla fine dove dovresti porre

confronto=confronto || ABR(radice->destro,&(radice->info));

[mame83]

class node{
public:
int info;
node* first;
node* second;
node(int i,node* f, node* s):info(i),first(f),second(s){}
};

bool testNode(node* n){
bool isOk = true;
if(n->first!=0)
isOk = n->first->info <= n->info;
if(n->second!=0)
isOk = isOk && n->info <= n->second->info;
return isOk;
}

bool testABR(node* root){
if(root == 0) return true;
return testNode(root) && testABR(root->first) && testABR(root->second);
}

Credo che nel tuo codice l'errore sia alla fine dove dovresti porre

confronto=confronto || ABR(radice->destro,&(radice->info));

Scusa la mia ignoranza in materia. ma il codice che hai scritto non l ho capito. non è C vero?

[EnergyVortex]

non basta fare una visita inorder e controllare che i valori siano sempre crescenti?

[mame83]

e questo che voglio. ma come posso fare??? dove sbaglio nella mia funzione?

[EnergyVortex]

io farei così:
void verifica(struct nodo *radice, int *max, int* abr) //se abr è 0 è un ABR
{
verifica(radice->sx,max,abr);
int appoggio;
if (radice!=NULL)
{
appoggio=radice->info;
if (appoggio<max)
*abr=1;
*max=appoggio;
}
verifica(radice->dx,max,abr);
}

[mame83]

scusa max lo inizializzo a 0 o ad un valore grande??

[Floris]

Quando quoti un listato lungo di codice senza apportarne modifiche, fai così:

class node{
public:
int info;
...

Per non rendere il thread dispersivo.

In ogni caso il codice è in C++. In C sarebbe una cosa del genere:

struct node{
int info;
node* first;
node* second;
};

bool testNode(node* n){
bool isOk = true;
if(n->first!=0)
isOk = n->first->info <= n->info;
if(n->second!=0)
isOk = isOk && n->info <= n->second->info;
return isOk;
}

bool testABR(node* root){
if(root == 0) return true;
return testNode(root) && testABR(root->first) && testABR(root->second);
}

Inoltre vengono usati i valori booleani. true equivale a 1 e false a 0. Il test n->first!=0 equivale a n->first!=NULL.
Quindi per avere i valori che vuoi tu basta che fai !testABR(radice), così ti ritorna 0 (false) se è ABR e 1 (true) se non lo è.
Per il resto è una normale visita ricorsiva infissa dell'albero. Facendo così eviti di dover utilizzare variabili ausiliarie.
Inoltre la cortocircuitazione dell'operatore && garantisce che appena viene trovato un valore che non rispetta la definizione
di ABR, la ricorsione si chiude. (nel caso non sapessi cosa significa che l'operatore binario && è cortocircuitato, significa che se si ha A && B,
all'atto della valutazione se A è true allora viene valutato anche B, mentre se A è false allora B non viene valutato poichè
A && B è in ogni caso false. Stessa cosa per l'operatore binario ||)

Se vuoi una visita prefissa, basta porre:

return testABR(root->first) && testNode(root) && testABR(root->second);

[EnergyVortex]

scusa max lo inizializzo a 0 o ad un valore grande??

a 0 se l'albero contiene solo valori positivi, altrimenti al massimo numero negativo rappresentabile con un int

[mame83]

io farei così:
void verifica(struct nodo *radice, int *max, int* abr) //se abr è 0 è un ABR
{
verifica(radice->sx,max,abr);
int appoggio;
if (radice!=NULL)
{
appoggio=radice->info;
if (appoggio<max)
*abr=1;
*max=appoggio;
}
verifica(radice->dx,max,abr);
}

L ho provato a fare come dici. ma va in loop.
ho inizializzato nel main max e abr a 0

void verifica(struct nodo *radice, int *max, int* abr) //se abr è 0 è un ABR
{
verifica(radice->sinistro,max,abr);
int appoggio;
if (radice!=NULL)
{
appoggio=radice->info;
if (appoggio<*max)
*abr=1;
*max=appoggio;

}

verifica(radice->destro,max,abr);
}