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

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. :mc:

[clockover]

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. :mc:

mamma mia e che ci hai messo qua :doh:

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]

mamma mia e che ci hai messo qua :doh:

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......:muro:

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

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 :confused:
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]

non riesco a capire perchè devi complicarti la vita in questo modo :confused:
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]

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]

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

[mame83]

hai ragione proverò a farlo

[mame83]

allora ho provato a farlo seguendo la visita in ordine

int abr(nod *radice)
{
int app;
if (radice!=NULL)
{
app=radice->info;
return(abr(radice->sinistro));
if (radice->info<app)
{
return(abr(radice->destro));
}
else
return 1;
}
}

il problema e che mi restituisce sempre 1 qualcuno saprebbe aiutarmi???

[goldorak]

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



Una soluzione veloce puo' essere quella di visitare in ordine l'albero T e verificare che gli elementi visitati costituiscano una successione crescente. Per questo basta ricordarsi degli ultimi due elementi visitati.

[mame83]

Una soluzione veloce puo' essere quella di visitare in ordine l'albero T e verificare che gli elementi visitati costituiscano una successione crescente. Per questo basta ricordarsi degli ultimi due elementi visitati.
ed è questo che ho provato a fare nel programma. vedere il succssivo se è maggiore di quello attuale ma non mi riesce. hai qualche suggerimento sul programma che ho precedentemente postato? :mc: non so cosa modificare grazie

[goldorak]

ed è questo che ho provato a fare nel programma. vedere il succssivo se è maggiore di quello attuale ma non mi riesce. hai qualche suggerimento sul programma che ho precedentemente postato? :mc: non so cosa modificare grazie


Mantieni una variable globale x (inizializzata con un valore arbitrario piu' piccolo di qualsiasi valore presente nell'albero, chesso' 0 oppure -100000)

L'algoritmo di visita in ordine funziona cosi :


inordine (T)

visiti sottoalbero sinistro di T
(*) visiti radice di T
visiti sottoalbero destro di T


quando visiti la radice di T (*), confronti il valore della radice con x. Se la radice di T e' maggiore di x aggiorna x con il valore della radice, se invece il valore della radice e' minore di x esci dalla procedura/funzione perche' l'albero non puo' essere un albero binario di ricerca.

[clockover]

Dato che ora il tuo problema è anche un mio problema...sono arrivato alla coclusione che ci sono tre soluzioni (o almeno le mie)
1- ti crei un vettore della dimensione dell'albero, fai una visita, ci salvi gli elementi e poi controlli il vettore (brutta non mi piace però è semplice)
2- effettuo una visita (ovviamente inorder) e confronto le chiavi ricorsivamente...questa è tosta ma figa
3- una versione iterativa della seconda usa uno stack e ci salva i nodi confrontando le chiavi mano mano...pure questa mi piace....
domani mi metto all'opera

[mame83]

allora ho provato a fare con la variabile passata nella funzione per confrontarla con il valore precedente.

int abr(nod *radice,int conf)
{

if (radice!=NULL)
{

return (abr(radice->sinistro,radice->info));

if (radice->info<conf)
return(abr(radice->destro,radice->info));
else

return 1;
}
}

il problema è che inserendo delle printf prima della chiamata radice sinistro le fa dopo invece niente , quindi non richiama neanche radice destro.
non so cosa fare :mc:

[goldorak]

non so cosa fare :mc:

Magari parti dall'algoritmo di visita inordine scritto correttamente e poi lo modifichi leggermente.



int X *inizializzata con un valore opportuno*

visit (node* root) {

if (root != NULL) {

visit (root->left) ;

[ In questo blocco fai il confronto tra il root->info ed il valore della variable globale x.
Se non viene soddisfatta la proprieta' degli abr esci dall'algoritmo altrimenti aggiorna x e continua l'esecuzione dell'algoritmo.]

visit (root->right);
}
}

[mame83]

Magari parti dall'algoritmo di visita inordine scritto correttamente e poi lo modifichi leggermente.

devo usare una void? visto che con una funzione dopo il return non fa più niente. giusto?

[mame83]

e poi la variabile per il confronto devo passarla nella void???

[goldorak]

devo usare una void? visto che con una funzione dopo il return non fa più niente. giusto?

Si, se la funzione non ritorna alcun valore metti void.

e poi la variabile per il confronto devo passarla nella void???

Se usi una variable globale la puoi usare direttamente nel codice della funzione senza passarla esplicitamente. Se invece non vuoi usare una variable globale puoi modificare il prototipo della funzione in questo modo
visit (node *root, int* x).

[mame83]

io vorrei utilizzare una funzione che mi restituisca 1 se è un abr e 0 se non lo è. Il problema è che se utilizzo una funzione dopo il return(richiamo il sinistro)in questa stessa funzione non rientrerà più e quindi non posso fare i confronti, ne succesivamente chiamare il destro. è questo il problema grosso :mc: :mc: come posso fare?

[goldorak]

io vorrei utilizzare una funzione che mi restituisca 1 se è un abr e 0 se non lo è. Il problema è che se utilizzo una funzione dopo il return(richiamo il sinistro)in questa stessa funzione non rientrerà più e quindi non posso fare i confronti, ne succesivamente chiamare il destro. è questo il problema grosso :mc: :mc: come posso fare?

Beh la tua funzione e' fatta male, e' proprio sbagliata nel senso che non fail il controllo giusto quando richiami ricorsivamente la funzione sui sottoalberi destro e sinistro piu' qualche altro problema logico.

Prima di implementare tale funzione, devi fare un ragionamento per induzione strutturale sull'albero e capire come il criterio di abr entri in gioco quando hai una struttura del genere

a
/ \
S D

supponendo che i sottoalberi S e D siano degli alberi binari di ricerca, che condizione deve valere per il nodo a affinche il tutto (nodo a collegato con S e D) sia a sua volta un albero binario di ricerca ?

[mame83]

Beh la tua funzione e' fatta male, e' proprio sbagliata nel senso che non fail il controllo giusto quando richiami ricorsivamente la funzione sui sottoalberi destro e sinistro piu' qualche altro problema logico.

Prima di implementare tale funzione, devi fare un ragionamento per induzione strutturale sull'albero e capire come il criterio di abr entri in gioco quando hai una struttura del genere

a
/ \
S D

supponendo che i sottoalberi S e D siano degli alberi binari di ricerca, che condizione deve valere per il nodo a affinche il tutto (nodo a collegato con S e D) sia a sua volta un albero binario di ricerca ?

un albero binario è di ricerca se tutti gli elementi del sotto albero di sinistra sono minori de nodo radice e tutti gli elementi del sottoalbero destro sono maggiori o uguali.

Ora il problema (che ho da più di un mese) è che non posso usare una funzione simile alla void delle visita in ordine perchè dopo il return non entrèra mai più nella stessa funzione, ne richiamerà altre e una volta arrivato a radice==NULL chiuderà tt le funzioni precedentemente aperte.
Spero di essere stato chiaro.

Spero che mi aiutate IN MANIERA CHIARA perche questo problema mi sta mandando al manicomio!!!!!!!!!

[goldorak]

un albero binario è di ricerca se tutti gli elementi del sotto albero di sinistra sono minori de nodo radice e tutti gli elementi del sottoalbero destro sono maggiori o uguali.



Molto bene, quindi cosa devi fare ? Hai bisogno di due funzioni ausiliarie chiamiamole MAX (T) e MIN (T) che ti restituiscono il massimo ed il minimo
nell'albero T. Ora diventa semplice capire la condizione che deve soddisfare il nodo a quando fai la chiamata ricorsiva sull'albero T.

a >= MAX (T->sinistro) e a<= MIN (T->destro).

Questa condizione si puo' semplificare perche' in un albero binario di ricerca T il massimo e' sempre l'elemento piu' a destra mentre il minimo e' sempre l'elemento piu' a sinistra. Quindi invece di fare una ricerca esaustiva per il massimo ed il minimo basta scorrere l'albero o tutto a sinistra oppure tutto a destra.


Ora il problema (che ho da più di un mese) è che non posso usare una funzione simile alla void delle visita in ordine perchè dopo il return non entrèra mai più nella stessa funzione, ne richiamerà altre e una volta arrivato a radice==NULL chiuderà tt le funzioni precedentemente aperte.
Spero di essere stato chiaro.

Spero che mi aiutate IN MANIERA CHIARA perche questo problema mi sta mandando al manicomio!!!!!!!!!

Il tuo problema e' che cerchi di implementare una funzione alla meno peggio senza avere ben chiara la situazione.


Il pseudocodice che ti scrivo e' la traduzione diretta di quello che ti ho spiegato poco sopra. Ecco :


Sia T un albero (a, S, D) con a un nodo e S e D sottoalberi binari.

Sia F la funzione che restituisce 1 se T e' un abr e 0 altrimenti.


Se T=(a, NULL, NULL) F(T) restituisce 1 poiche' T e' un abr
Se T=(a, S, NULL) F(T) restituisce 1 se e solo se a>=MAX(S) e F(S) == 1
Se T=(a, NULL, D) F(T) restituisce 1 se e solo se a <= MIN(D) e F(D) == 1
Se T=(a, S, D) F(T) restituisce 1 se e solo se F(S) == 1, F(D) == 1, a>=MAX(S) e a<= MIN(D)


Adesso sta a te implmentare in C questa funzione.
Non avrai problemi se hai capito le proprieta' degli alberi binari di ricerca. ;)

[mame83]

ho capito il tuo discorso ma io vorrei risolvero in maniera piu semplice. vedendo la successione se è crescente non so se mi spiego