[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]

ragazzi vi prego aiutatemi!!!!!!!

[mame83]

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

[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]

Originariamente inviato da 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));

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ì:

Originariamente inviato da Floris

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]

Originariamente inviato da mame83

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]

Originariamente inviato da 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);
}

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);
}