[C++] ALBERO BINARIO BST SIMMETRICO

[Doraemond]

mentre giravo in rete ho trovato qlk esercizio in c++ che richiedeva ,dato un albero binario bst creato dando i dati in input di verificare tramite una funzione booleana se l'albero era simmetrico oppure no.sono riuscito a fare le prime cose ma mi sn bloccato qnd mi chiede d verificare se l'albero è simmetrico,ho provato a scrivere un codice ma nn riesco proprio a capire come confrontare la parte sinistra dell'albero con la simmetrica destra in un unica funzione..qlk potrebbe darmi una mano a capire come operare,magari in pseudo codice

P.S:non voglio che mi scriviate il codice,voglio soltanto capire il procedimento,il codice voglio svilupparlo da me!! :D :D

[DanieleC88]

Diciamo che hai un albero fatto così:

http://i49.tinypic.com/akiebq.jpg

Secondo me puoi fare una cosa di questo tipo.

caso base: l'albero è vuoto (non contiene alcun nodo). La funzione restituisce banalmente sì.
caso generale: ogni nodo all'interno dell'albero è la radice di un sottoalbero più piccolo. Ad ogni nodo che si trova nel lato sinistro dell'albero vuoi che corrisponda la stessa struttura, ribaltata specularmente, sul lato destro dell'albero. Quindi vuoi che (per esempio) quando il nodo b ha un figlio sinistro e non ha figlio destro, allora il nodo c abbia un figlio destro e non un figlio sinistro. Se imposti una funzione ausiliaria che riceve due parametri (due puntatori ai nodi opposti da esaminare, come b e c), allora puoi partire dalla radice ed invocare questa funzione ausiliaria sui sottoalberi radicati nel figlio sinistro e destro, e poi questa farà altrettanto finché non è terminato l'albero.


Dimmi se ti serve un esempio in pseudocodice, nel caso in cui io non sia stato molto chiaro. (Ed è un caso alquanto probabile. :D)

ciao ;)

[Doraemond]

diciamo che ho capito cosa vuoi dire tu ma il problema è che come faccio passare alla funzione ausiliaria i parametri che voglio far confrontare,e altro problema quanto + scendo di livello nell'albero i sottoalberi aumentano,a livello 1 ne ho 2 ,a livello 2 ne ho 4 e così via,come faccio a far passare i valori giusti??

P.S: se ti va postami anke lo pseudo codice,grazie

[DanieleC88]

In effetti mi rendo conto che era poco comprensibile descritto sommariamente come nel mio ultimo post. Però tu volevi il brivido del codice scritto da te... :D

Allora, abbozzo uno pseudocodice velocissimo:
algoritmo Albero-Simmetrico(albero T) → booleano {
se (T è vuoto) {
restituisci vero;
}
altrimenti {
restituisci Albero-StessaStruttura(T->sinistro, T->destro);
}
}

algoritmo Albero-StessaStruttura(nodo X, nodo Y) → booleano {
se (X è nullo AND Y è nullo) {
restituisci vero;
}
altrimenti se (X non è nullo AND Y non è nullo) {
restituisci (Albero-StessaStruttura(X->sinistro, Y->destro) AND Albero-StessaStruttura(X->destro, Y->sinistro));
}
altrimenti {
restituisci falso;
}
}

Non l'ho provato e dimostrato, ma a rigor di logica dovrebbe essere giusto... Buon lavoro. :)

ciao ;)

[lupoxxx87]

se è un bst ogni vertice dell'albero ha zero, uno o due figli.
chiamiamoli quindi destro e sinistro.

tu sai che ogni foglia (i vertici con 0 figli) è ad una determinata profondità.
un modo semplice potrebbe essere fare una visita in ordine simmetrico dell'albero e ogni volta che arrivi ad una foglia salvare la sua profondità in una lista, o array, o stringa; comunque in una struttura esterna all'albero.

finita la visita ti basta fare una lettura della tua struttura con i da 0 a l/2 confrontando gli elementi [i] e [l-1-i].
se gli elementi hanno la stessa profondità prosegui la lettura, altrimenti restituisci false.
se alla fine della lettura non hai mai restituito false, restituisci true.

ti sembra fattibile ?

[Doraemond]

#include<iostream>

using namespace std;

struct Tnodo{
int info;
Tnodo *sx,*dx;
};
typedef Tnodo *Pnodo;

void menu();
Pnodo crea_nodo(int info);
void inserimento(Pnodo &L,int info);
Pnodo cerca(Pnodo L,int info);
Pnodo cerca2(Pnodo L,int info);
void stampa(Pnodo L,int i);
Pnodo TrovaDatoT(int d, Pnodo A);
bool simmetrico(Pnodo L);
bool confronta(Pnodo ,Pnodo);

int main(){
int temp,scelta;
Pnodo L;
L=new Tnodo;
L=NULL;
do{
menu();
cin>>scelta;
switch(scelta){
case 1:
cout<<"inserisci valore: ";
cin>>temp;
inserimento(L,temp);
break;
case 2:
Pnodo trovato;
trovato=new Tnodo;
trovato=NULL;
cout<<"inserisci valore da cercare: ";
cin>>temp;
trovato=cerca(L,temp);
if(trovato!=NULL)
cout<<trovato->info<<" e' stato trovato e ha come indirizzo : "<<trovato<<endl;
else
cout<<"il valore da ricercare non e' stato trovato\n\n";
break;
case 3:
if(simmetrico(L))
cout<<"l'albero e' simmetrico\n";
else
cout<<"l'albero non e' simmetrico\n";
break;
case 4:
stampa(L,0);
break;
case 5:
cout<<"\t ciao ;-)\n\n";
break;
default:
cout<<"\n\tscelta errata,riprovare\n\n";
break;
}
}while(scelta!=5);
system("pause");
return 0;
}

void menu(){
cout<<"1) inserimento nuovo nodo\n";
cout<<"2) cerca nodo nell'albero\n";
cout<<"3) verifica se l'albero e' simmetrico\n";
cout<<"4) stampa albero\n";
cout<<"5) esci\n";
cout<<"\t scelta: ";
}

Pnodo crea_nodo(int info){
Pnodo temp;
temp=new Tnodo;
temp->info=info;
temp->sx=NULL;
temp->dx=NULL;
return temp;
}

void inserimento(Pnodo &L,int info){
if(L==NULL)
L=crea_nodo(info);
else if(info > L->info)
inserimento(L->dx,info);
else if(info < L->info)
inserimento(L->sx,info);
else
cout<<"\n\tnodo gia inserito\n\n";
}


void stampa(Pnodo L,int i){
if(L!=NULL){
stampa(L->dx,i+1);
for(int j=1;j<=i;j++){
cout<<" ";
}
cout<<L->info<<endl;
stampa(L->sx,i+1);
}
}

Pnodo cerca(Pnodo L,int info){
if(L!=NULL){
if(info > L->info)
return cerca(L->dx,info);
else if(info < L->info)
return cerca(L->sx,info);
else
return L;
}
else
return NULL;
}

bool confronto(Pnodo L){
if(L!=NULL)
return true;
else
return false;
}

bool simmetrico(Pnodo L){
if(L==NULL){
return true;
}
else{
return confronta(L->sx,L->dx);
}
}

bool confronta(Pnodo x, Pnodo y) {
if(x==NULL && y==NULL) {
return true;
}
else if(x!=NULL && y!=NULL) {
return (confronta(x->sx, y->dx) && confronta(x->dx,y->sx));
}
else{
return false;
}
}


questo è il codice che ho scritto,sembrerebbe andare bene,casomai se puoi dare una ricontrollata al codice e mi dici se sbaglio in qlk,comunque grazie 1000

P.S non so se sn riuscito a mettere il codice in un tag separato casomai puoi spiegarmi come fare XDXD

[:.Blizzard.:]

Una BFS a partire dalla radice - e qualche aggiustamento di codice - anche potrebbe andare secondo me, no?

[Doraemond]

potresti spiegarti meglio,la bfs (breadth-first search) non l'ho ancora studiata,x quanto riguarda gli aggiustamenti di codice potresti dirmi dove posso migliorarlo,grazie

[lupoxxx87]

la bfs o visita in ordine simmetrico ha il seguente come pseudo codice

visitasimm(vertice *v) {
if (v->sinistro != null) visitasimm(v->sinistro);
>fai quello che devi fare con v<
if (v->destro != null) visitasimm(v->destro);
}


questo tipo di visita ti permette, se i dati sono inseriti ordinatamente, di visitarli tutti dal minore al maggiore (o dal maggiore al minore, a seconda della relazione d'ordine usata nell'inserimento)

[DanieleC88]

la bfs o visita in ordine simmetrico ha il seguente come pseudo codice

visitasimm(vertice *v) {
if (v->sinistro != null) visitasimm(v->sinistro);
>fai quello che devi fare con v<
if (v->destro != null) visitasimm(v->destro);
}


questo tipo di visita ti permette, se i dati sono inseriti ordinatamente, di visitarli tutti dal minore al maggiore (o dal maggiore al minore, a seconda della relazione d'ordine usata nell'inserimento)
Veramente quella è una visita in-order e sarebbe corrispondente più che altro ad una DFS (http://en.wikipedia.org/wiki/Depth-first_search), invece una visita per livelli corrisponde più precisamente ad una BFS (http://en.wikipedia.org/wiki/Breadth-first_search).

[lupoxxx87]

Veramente quella è una visita in-order e sarebbe corrispondente più che altro ad una DFS (http://en.wikipedia.org/wiki/Depth-first_search), invece una visita per livelli corrisponde più precisamente ad una BFS (http://en.wikipedia.org/wiki/Breadth-first_search).

ah si si sorry mi sono confuso...anche perchè sinceramente....la visita in ampiezza di un albero non la troverei utile per questo problema..

io l'avrei risolto, come dico sopra, con una visita in ordine simmetrico (o visita in profondità se lo consideriamo un grafo) più qualche accorgimento