[C] verificare se un albero binario è un abr

[mame83]

Ciao a tutti ho il seguente problema: devo verificare se un albero binario è un albero binario di ricerca. Spero che mi aiutate grazie

void verifica(nod *radice, int abr)/*ritorna zero se e un abr 1 se non è*/
{
 
 if (radice!=NULL)
   {
    printf("radice uguale a %d \n",radice->info);
    if (((radice->sinistro==NULL)&&(radice->destro->info<radice->info))||
       ((radice->destro==NULL)&&(radice->sinistro->info>radice->info))||
       ((radice->destro->info<radice->info)&&(radice->sinistro->info<radice->info)))
        {
         
         abr=1;
         
        } 
    else
      { 
       verifica(radice->sinistro,0);
       verifica(radice->destro,0);
      }
   }   
  
}

[wingman87]

Faccio due considerazioni che dovrebbero condurti sulla buona strada:
- questa funzione deve restituire un valore, quindi perché è void?
- se sia il ramo sx che il dx sono NULL cosa succede?

[mame83]

ciao avevo pensato di usare una vodi visto che devo ricordarmi il valore di abr precedente. Poi per quanto riguarda se entrambi i figli sono uguali a null deve fermarsi e questo che non riesco a fare. Se saresti piu esplicito forse capisco meglio. grazie

[clockover]

Originariamente inviato da mame83

Ciao a tutti ho il seguente problema: devo verificare se un albero binario è un albero binario di ricerca. Spero che mi aiutate grazie

void verifica(nod *radice, int abr)/*ritorna zero se e un abr 1 se non è*/

si ma non ritorna nulla con il void, sostituiscilo con int...

per quanto riguarda il fatto se un nodo non ha figlio destro e sinistro il risultato è true (cioè 1)....

io farei una cosa del tipo.... (molto al volo)

se nodo == null
    return 1;
se nodo.left == null && nodo.right == null
    return 1;
qui effettui i controlli su entrambi i figli
se uno solo dei due non soddisfa la condizione puoi ritornare direttamente 0

ora qui fai una chiamata ricorsiva su entrambi i figli della funzione
ricorda che deve essere vero per entrambi

e la tua funzione falla così

int isBst(nod * radice) //o comunque chiamala come vuoi

dato che ti serve solo la radice leva quell'altro parametro che non ti serve..

[mame83]

ho fatto come mi dicevi.

int verifica(nod *radice)/*ritorna zero se e un abr 1 se non è*/
{
 
 if ((radice==NULL)||((radice->sinistro==NULL)&&(radice->destro==NULL)))
   {
     
     return 0; 
   }
 else
   if (((radice->sinistro==NULL)&&(radice->destro->info<radice->info))||
       ((radice->destro==NULL)&&(radice->sinistro->info>radice->info))||
       ((radice->destro->info<radice->info)&&(radice->sinistro->info<radice->info)))
        {
         
         return 1;
        } 
   else
     {
      ;
       return (verifica(radice->sinistro));
       return (verifica(radice->destro));
     }          
}

però ho due problemi:
1 mi restituisce sempre 0, se non metto return 0 mi restituisce sempre 1.
2 non richiamo il figlio destro
SPero mi aiuti perche non so piu cha fare.

[clockover]

Originariamente inviato da mame83

return (verifica(radice->sinistro));
return (verifica(radice->destro));
però ho due problemi:
1 mi restituisce sempre 0, se non metto return 0 mi restituisce sempre 1.
2 non richiamo il figlio destro
SPero mi aiuti perche non so piu cha fare.

mamma mia e che ci hai messo qua

due return non si possono proprio vedere.....

semplifica la cosa levando un po di roba che almeno ti semplifica la vita...
intanto il passo base della ricorsione è fatto bene se non fosse che devi ritornare 1. Si perchè un albero binario è banalmente binario se non ha figli (cioè è una foglia) e il controllo se il nodo stesso è null diciamo che neanche servirebbe in questo caso ma ce lo mettiamo lo stesso
quindi

se nodo == null || (nodo.left == null && nodo.right == null)return 1;

e qui ci siamo

controlli i figli

se (nodo.left != null) && (nodo.left.info > nodo.info)return 0
se (nodo.right != null) && (nodo.right.info <= nodo.info) return 0

qui ho fatto una cosa semplice: non controllo se il sinistro è minore o uguale e il destro maggiore, ma il contrario! In questo modo posso ritornare 0 (cioè è violata la condizione) e bloccare subito il controllo!

adesso però devi vedere che tutti gli altri nodi non ritornino 0

return isBst(nodo.left) && isBst(nodo.right)

questo vuol dire che se un solo nodo ritorna 0 il controllo si interrompe e restituisce 0, propagandolo fino alla radice! Quando è che ritorna 1? Quando sei arrivato ad una foglia e ritorni 1 (passo base della ricorsione)

spero di non aver sbagliato nulla


edit
gli else non servono a nulla in questo caso, omettili adesso almeno rendono un po più leggibile il codice

[mame83]

Originariamente inviato da clockover

mamma mia e che ci hai messo qua

due return non si possono proprio vedere.....

semplifica la cosa levando un po di roba che almeno ti semplifica la vita...
intanto il passo base della ricorsione è fatto bene se non fosse che devi ritornare 1. Si perchè un albero binario è banalmente binario se non ha figli (cioè è una foglia) e il controllo se il nodo stesso è null diciamo che neanche servirebbe in questo caso ma ce lo mettiamo lo stesso
quindi

se nodo == null || (nodo.left == null && nodo.right == null)return 1;

e qui ci siamo

controlli i figli

se (nodo.left != null) && (nodo.left.info > nodo.info)return 0
se (nodo.right != null) && (nodo.right.info <= nodo.info) return 0

qui ho fatto una cosa semplice: non controllo se il sinistro è minore o uguale e il destro maggiore, ma il contrario! In questo modo posso ritornare 0 (cioè è violata la condizione) e bloccare subito il controllo!

adesso però devi vedere che tutti gli altri nodi non ritornino 0

return isBst(nodo.left) && isBst(nodo.right)

questo vuol dire che se un solo nodo ritorna 0 il controllo si interrompe e restituisce 0, propagandolo fino alla radice! Quando è che ritorna 1? Quando sei arrivato ad una foglia e ritorni 1 (passo base della ricorsione)

spero di non aver sbagliato nulla


edit
gli else non servono a nulla in questo caso, omettili adesso almeno rendono un po più leggibile il codice

ho capito che due return uno dietro l altro non funzionano perche ne farà sempre solo il primo. ma la funzione deve restituire 0 se è un abr 1 se non lo è

[clockover]

Non ci avevo fatto caso che doveva essere il contrario...vabbè comunque basta davvero poco per modificarlo...

[mame83]

scusa ma il caso base e che il nodo non ha figli o e lui stesso NULL e restituisce 0 come avevo fatto......

[clockover]

Guarda stai impazzendo per nulla... se hai capito quello che ti ho scritto prima ti basta modificare poche cose...più di questo dovrei darti la soluzione...e non mi pare il caso

comunque posta il tuo codice.

[mame83]

continua a non funzionarmi come in questo caso:
5
\
7
/
3
va in loop. 5 radice 7 figlio destro di 5 e 3 figlio sinistro di 7.

int verifica(nod *radice)/*ritorna zero se e un abr 1 se non è*/
{
 
 if ((radice==NULL)||((radice->sinistro==NULL)&&(radice->destro==NULL)))
   {
     printf("fine \n");
     return 0; 
   }
 else
   if (((radice->sinistro==NULL)&&(radice->destro->info<radice->info))||
       ((radice->destro==NULL)&&(radice->sinistro->info>radice->info))||
       ((radice->destro->info<radice->info)&&(radice->sinistro->info<radice->info)))
        {
         printf("l albero non e' un abr \n");
         return 1;
        } 
   else
     {
       printf("andiamo avanti con la funzione \n");
       return (verifica(radice->sinistro)||verifica(radice->destro));
       
       
     }          
}

non riesco a capire perche va in loop

[sottovento]

Prova a semplificarlo ancora un po:

- caso base: Se il nodo e' NULL allora ritorna 1 (si, e' un albero di ricerca);
- caso base: se uno dei due nodi, sinistro/destro e' NULL, allora ritorna 1 in accordo all'ordine che hai scelto (cioe', se sx!=NULL, allora confronta sx con root e se sx < root ritorni 1);

- caso base :Se sia sx sia dx sono != NULL (quindi hai fatto i controlli di cui sopra) allora puoi confrontare sx->root->dx. Se non rispettano l'ordine, ritorni 0. Siccome hai trovato un caso, tutto l'albero non e' di ricerca e le tue ricorsioni verranno interrotte perche' sai gia' il risultato.

Infine (caso ricorsivo) ti rimane che sx e dx sono != NULL e sono nell'ordine giusto. Allora puoi fare l'AND fra le chiamate ricorsive a sx e dx e ritornare il risultato.

Fai le prove partendo da alberi semplici (i.e. verifica i casi base prima di tutto)

Spero ti sia d'aiuto

[clockover]

Originariamente inviato da mame83

continua a non funzionarmi come in questo caso:
5
\
7
/
3
va in loop. 5 radice 7 figlio destro di 5 e 3 figlio sinistro di 7.

int verifica(nod *radice)/*ritorna zero se e un abr 1 se non è*/
{
 
 if ((radice==NULL)||((radice->sinistro==NULL)&&(radice->destro==NULL)))
   {
     printf("fine \n");
     return 0; 
   }
else
   if (((radice->sinistro==NULL)&&(radice->destro->info<radice->info))||
       ((radice->destro==NULL)&&(radice->sinistro->info>radice->info))||
       ((radice->destro->info<radice->info)&&(radice->sinistro->info<radice->info)))
        {
         printf("l albero non e' un abr \n");
         return 1;
        } 
   else
     {
       printf("andiamo avanti con la funzione \n");
       return (verifica(radice->sinistro)||verifica(radice->destro));
       
       
     }          
}

non riesco a capire perche va in loop

non riesco a capire perchè devi complicarti la vita in questo modo
mettendo tutta quella roba in un'unica espressione rischi di fare degli errori e non riuscire a capire dove

quella parte in rosso cancellala totalmente...
sostituisci con qualcosa del tipo

se nodo.left != null && nodo.left.value > nodo.value return 1
se nodo.right != null && nodo.right.value <= nodo.value return 1

Cancella anche tutti gli else che ci sono. Non sono un errore usarli, ma non servono ora e levandoli migliori la lettura del codice

Comunque fattelo dire ritornare 0 (false) se è un albero binario e 1 (true) se non lo è è una cosa molto anomala...

[mame83]

Originariamente inviato da clockover

non riesco a capire perchè devi complicarti la vita in questo modo
mettendo tutta quella roba in un'unica espressione rischi di fare degli errori e non riuscire a capire dove

quella parte in rosso cancellala totalmente...
sostituisci con qualcosa del tipo

se nodo.left != null && nodo.left.value > nodo.value return 1
se nodo.right != null && nodo.right.value <= nodo.value return 1

Cancella anche tutti gli else che ci sono. Non sono un errore usarli, ma non servono ora e levandoli migliori la lettura del codice

Comunque fattelo dire ritornare 0 (false) se è un albero binario e 1 (true) se non lo è è una cosa molto anomala...

ho fatto come dici tu le semplificazioni ma mi da sempre 1 cioe che non è un abr
anke in caso di albero semplice :
5
3 6

int verifica(nod *radice)/*ritorna zero se e un abr 1 se non è*/
{
 
 if ((radice==NULL)||((radice->sinistro==NULL)&&(radice->destro==NULL)))
   {
     printf("fine \n");
     return 0; 
   }
 else
   {
    printf("valore del nodo analizzato uguale a %d \n",radice->info);        
    if ((radice->sinistro!=NULL)&&(radice->sinistro->info>radice->info))
      return 1;
    if  ((radice->destro!=NULL)&&(radice->destro->info>radice->info))
      return 1;
    return (verifica(radice->sinistro)&&verifica(radice->destro));
   }
                
}

[clockover]

C'è un errore nel return finale che prima non avevi fatto

[mame83]

Originariamente inviato da clockover

C'è un errore nel return finale che prima non avevi fatto

ho sbagliato il secondo if per ritornare 1 deve essere destro<radice
per quanto riguardo il return finale devo mettere l else del secondo if?

[clockover]

Originariamente inviato da mame83

ho sbagliato il secondo if per ritornare 1 deve essere destro<radice
per quanto riguardo il return finale devo mettere l else del secondo if?

Si giusto... metti minore/uguale per il figlio destro... nel return finale sostituisci and con or

[mame83]

ho fatto come dicevi

int verifica(nod *radice)/*ritorna zero se e un abr 1 se non è*/
{
 
 
 if ((radice==NULL)||((radice->sinistro==NULL)&&(radice->destro==NULL)))
   {
     
     return 0; 
   }
 else
   {
            
    if ((radice->sinistro!=NULL)&&(radice->sinistro->info>radice->info))
                                                                      
       return 1;
       
    if  ((radice->destro!=NULL)&&(radice->destro->info<radice->info))
      
       return 1;
       
    else  
      return (verifica(radice->sinistro)||verifica(radice->destro));
   }
                
}

un caso che non avevo considerato e che forse dovrei cambiare quasi tt il codice è questo:
se io ho un albero in cui i figli rispettano la proprieta verso il padre ma non verso il nonno diciamo cosi quest algoritmo non va bene.
ESEMPIO
5
\
7
/
2
in questo caso mi restituisce che e un ABR perche controlla che 2 è minore di 7 e che 7 è maggiore di 5. ma non che 2 stando a destra di 5 dovrebbe essere maggiore di 5. non so se ho reso l idea

[clockover]

Effettivamente hai ragione.. non avevamo considerato questa cosa! Potresti provare allora con una visita in-order e verificare che ogni nodo sia minore del successivo... Questa cosa mi era proprio sfuggita

[mame83]

hai ragione proverò a farlo