[C++] BST - FOGLIE SULLO STESSO LIVELLO

[Doraemond]

devo creare un algoritmo che dato un albero binario bst mi controlli tramite una funzione booleana se l'albero ha tutte le foglie sullo stesso livello,ho buttato giu un pezzo di codice ma nn mi si impalla xkè probabilmente quando vado a conftollare se il nodo è una foglia o meno nel caso in cui il nodo è nullo vado a deferenziare una zona di memoria non allocata,almeno credo.
posto il codice che ho iniziato a scrivere:
bool stesso_lev(Pnodo L){
if(L==NULL)
return true;
else
return confronta(L->sx,L->dx);
}

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

dove e molto probabilmento ho sbagliato??

[fero86]

ho capito bene?
[...] edit - vedi post #4

[DanieleC88]

Il tuo errore è di cercare di leggere subito i vari x->sx o x->dx senza controllare che il nodo x stesso in questione sia valido o meno.

Secondo me puoi fare anche un'altra cosa figa. :D
Puoi fare una visita per livelli, e per ogni livello controllare che siano tutte foglie o tutte non foglie. In altre parole, partendo dal primo nodo di ogni livello, se quel nodo non è una foglia, tutti gli altri nodi del livello non devono essere foglia, e simmetricamente se quel nodo è una foglia, tutti gli altri nodi del livello devono essere foglie. :)

ciao ;)

[fero86]

pardon, posto una versione un po' migliore :p
avevo scritto un metodo "Greatest" inutile, c'é giá std::max.
#include <iostream>
#include <algorithm>
using namespace std;


class CNode {
public:
virtual unsigned int Height() const = 0;
virtual bool Complete() const = 0;
};

class CLeaf :
public CNode {
public:
virtual unsigned int Height() const {
return 0;
}

virtual bool Complete() const {
return true;
}
};

class CTree :
public CNode {
private:
const CNode &m_rLeft;
const CNode &m_rRight;

public:
CTree(const CNode &a_rLeft, const CNode &a_rRight)
:
m_rLeft(a_rLeft),
m_rRight(a_rRight) {
}

virtual unsigned int Height() const {
return 1 + max(m_rLeft.Height(), m_rRight.Height());
}

virtual bool Complete() const {
return m_rLeft.Complete() && m_rRight.Complete() && (m_rLeft.Height() == m_rRight.Height());
}
};


int main() {
cout << CTree(CLeaf(), CLeaf()).Complete() << endl;
cout << CTree(CTree(CLeaf(), CLeaf()), CLeaf()).Complete() << endl;
return 0;
}

[marco.r]

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

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

dove e molto probabilmento ho sbagliato??

Chiami confronta senza verificare se sono puntatori nulli o meno.
In ogni caso l'algoritmo che proponi lo vedo sbagliato (funziona se un nodo ha solo una foglia, ma non se due interi sottorami hanno altezze diverse).
Vedo due alternative (relativamente simili).
La prima e' di verificare che ogni nodo dell'albero ha i due sottorami sinistro e destro di uguale altezza. L'altra e' quella di percorrere l'albero e controllare l'altezza di ogni foglia, controllandola con quella precedentemente trovata tramite una variabile condivisa.

[Doraemond]

hai usato le classi nel tuo codice ma purtroppo le classi nn le ho ancora studiate qnd nn c capisco nnt del tuo codice!!

[Doraemond]

daniele esiste un metodo per scorrere l'albero per livelli??

[DanieleC88]

Certo che esiste.
Crei una coda vuota, e le aggiungi la radice dell'albero.
Poi in un ciclo while (che si fermerà solo quando la coda è vuota) prendi un nodo alla volta dalla coda e lo "visiti". Poi aggiungi alla coda i suoi figli (se esistono) e ripeti il ciclo.
In questo modo avrai una visita per livelli.

Il problema è che in questo modo ti trovi a prendere un nodo alla volta e non sai a quale livello apparteneva. Direi che ti basterà aggiungere un'informazione "livello" ai nodi che inserirai nella coda, in modo da poter poi inserire i figli del nodo estratto nella coda con un valore del livello incrementato di 1. (Ok?)

A quel punto diventa una fesseria.

[marco.r]

Certo che esiste.
Crei una coda vuota, e le aggiungi la radice dell'albero.
Poi in un ciclo while (che si fermerà solo quando la coda è vuota) prendi un nodo alla volta dalla coda e lo "visiti". Poi aggiungi alla coda i suoi figli (se esistono) e ripeti il ciclo.
In questo modo avrai una visita per livelli.

Il problema è che in questo modo ti trovi a prendere un nodo alla volta e non sai a quale livello apparteneva. Direi che ti basterà aggiungere un'informazione "livello" ai nodi che inserirai nella coda, in modo da poter poi inserire i figli del nodo estratto nella coda con un valore del livello incrementato di 1. (Ok?)

A quel punto diventa una fesseria.

Direi che una cosa in questo caso e' un tantino overkill. Molto piu' semplice:

istanzi una variabile intera "altezzaFoglie" a -1
chiami ricorsivamente una funzione sulla radice alla quale passi
- altezza corrente dell'albero (all'inizio ovviamente 0)
- puntatore ad "altezzaFoglie"
il valore di ritorno sara true se il (sotto)albero e' bilanciato, false altrimenti

quando trovi una foglia verifichi il valore di "altezzaFoglie". Se e' -1 hai trovato la prima foglia e quindi imposti il valore all'altezza corrente e ritorni true. Se e' >= 0 confronti i due valori e ritorni true solo se sono uguali.

quando hai un nodo interno non fai che chiamare ricorsivamente la funzione sui due figli aumentando di uno l'altezza e ritornando l'OR tra i due risultati.

e' piu' corto da scrivere che da spiegare :D

[DanieleC88]

Sicuramente ci sono modi migliori di farlo (basta una funzione ricorsiva che controlli se l'albero è completo, come ha fatto fero86), però è una soluzione simpatica. :D
Perché non fargli sperimentare più di una strada? ;)

[fero86]

hai usato le classi nel tuo codice ma purtroppo le classi nn le ho ancora studiate qnd nn c capisco nnt del tuo codice!! sono indubbiamente il modo migliore per risolvere l'esercizio, infatti quelle assieme all'uso dei reference ti risparmiano da qualunque controllo di puntatori nulli, che sono la fonte dei tuoi problemi; se ci fai caso il mio codice non contiene manco un if.

studialo tutto il C++, é molto potente e ti permette di essere molto piu produttivo del C :)

[Doraemond]

uff...mi sto esaurendo io e quest'esercizio,qualcuno potrebbe postarmi un po di pseudocodice??

P.s.
anke io volevo farlo con la variabile che mi segnava il livello del nodo foglia ma il prof mi disse che dovevo afrlas senza ausilio di variabili,così mi scocciai e abbandonai l'esercizio,ma ora volendo imparare bene a programmare voglio risolvere anke questo problema,mi ricordo cmq che il prof mi disse che dovevo prima controllare se l'albero era bilanciato,e nel caso in cui fosse bilanciato effettuare i controlli sulle foglie...
:help: :help: :help: :help: :help: :help: :help: :help:

[DanieleC88]

Be', perché lo pseudocodice? fero86 ti ha dato un codice completo e funzionante. L'idea è quella che ha utilizzato lui, ed è banalissima. Se tutte le foglie si trovano sullo stesso livello, allora quello deve necessariamente essere l'ultimo livello preso per intero. E ciò accade in un albero binario (di ricerca o no, non ha importanza) quando quest'ultimo è completo. (E quando è completo, tutti i suoi nodi hanno un coefficiente di bilanciamento pari a 0, per cui non capisco del tutto il suggerimento del tuo professore.)

Quindi, ti basta controllare che, per ogni nodo, il sottoalbero radicato nel figlio sinistro ed il sottoalbero radicato nel figlio destro abbiano la stessa identica altezza.

[Doraemond]

ho visto ke mi ha dato il codice ma nn ci capisco nulla,siccome fatto cn le classi,quindi nn saprei come adattarlo al mio codice !!
in pseudocisice sarebbe + facile x me capirlo!!

[DanieleC88]

Lo pseudocodice viene quasi identico al codice di fero86 per quel che riguarda le parti "interessanti".

Sarebbe una cosa del tipo:
algoritmo Albero-Altezza(albero T) → intero {
se (T è vuoto) {
restituisci 0;
}
altrimenti {
restituisci 1 + max{ Albero-Altezza(T->sinistro), Albero-Altezza(T->destro) };
}
}

algoritmo Albero-Completo(albero T) → booleano {
se (T è vuoto) {
restituisci vero;
}
altrimenti {
se (Albero-Completo(T->sinistro) AND Albero-Completo(T->destro)) {
restituisci (Albero-Altezza(T->sinistro) == Albero->Altezza(T->destro));
}
altrimenti {
restituisci falso;
}
}
}

[marco.r]

Lo pseudocodice viene quasi identico al codice di fero86 per quel che riguarda le parti "interessanti".

Sarebbe una cosa del tipo:
algoritmo Albero-Altezza(albero T) → intero {
se (T è vuoto) {
restituisci 0;
}
altrimenti {
restituisci 1 + max{ Albero-Altezza(T->sinistro), Albero-Altezza(T->destro) };
}
}

algoritmo Albero-Completo(albero T) → booleano {
se (T è vuoto) {
restituisci vero;
}
altrimenti {
se (Albero-Completo(T->sinistro) AND Albero-Completo(T->destro)) {
restituisci (Albero-Altezza(T->sinistro) == Albero->Altezza(T->destro));
}
altrimenti {
restituisci falso;
}
}
}

Resto dell'idea che una singola funzione che fa tutto il lavoro sia una soluzione piu' adatta, non fosse altro perche' puoi evitare di visitare tutto l'albero qualora non sia necessario.


algoritmo alberoCompleto(albero T,int altezzaFoglie,altezzaCorrente) → booleano

se t vuoto
se altezzaFoglie==-1
altezzaFoglie = altezzaCorrente
restituisci vero
altrimenti
restituisci altezzaCorrente == altezzaFoglie
altrimenti
restituisci alberoCompleto( t->sinistro, altezzaFoglie, altezzaCorrente+1 ) e
alberoCompleto( t->destro, altezzaFoglie, altezzaCorrente+1 )

Da usare con chiamata iniziale

altezzaFoglie = -1
alberoCompleto( radice, altezzaFoglie, 0 )

[DanieleC88]

Non è che cambi molto, la complessità asintotica è la stessa per il caso peggiore (cioè quello in cui effettivamente l'albero è completo, in cui è richiesto comunque un attraversamento di ogni nodo, rendendo la complessità Θ(n), con n numero di nodi nell'albero).
In questo modo riusciresti tutt'al più a minimizzare il costo nel caso migliore, che è quello in cui l'albero è evidentemente non completo. :)

ciao ;)

[marco.r]

Non è che cambi molto, la complessità asintotica è la stessa per il caso peggiore (cioè quello in cui effettivamente l'albero è completo, in cui è richiesto comunque un attraversamento di ogni nodo, rendendo la complessità Θ(n), con n numero di nodi nell'albero).
In questo modo riusciresti tutt'al più a minimizzare il costo nel caso migliore, che è quello in cui l'albero è evidentemente non completo. :)

ciao ;)

Non hai fatto i conti con il caso medio :p.
Con la mia soluzione, il costo C per l'algoritmo e' il seguente:

C(t) = C(t->left) + 1 se t->left non e' bilanciato
= C(t->left) + 1 + C(t->right) altrimenti

Visto che nulla e' stato detto a riguardo, immagino che la distribuzione degli alberi sia uniforme. Ora, gli alberi completi sono solo una minima parte dei possibili ( O(log(n)) contro O(n) sul numero di nodi)
Nel primo caso il costo e' O(n), nel secondo O(log(n)). Il costo dell'algoritmo per tutti gli alberi e' quindi O(n)log(n) e quindi log(n) nel caso medio (invece che O(n)).

La dimostrazione non e' proprio formale, ma spero renda l'idea.

[DanieleC88]

Ma infatti io stavo parlando del caso peggiore. :D

[Doraemond]

marco.r ma net tuo pseudocodice

algoritmo alberoCompleto(albero T,int altezzaFoglie,altezzaCorrente) → booleano

se t vuoto
se altezzaFoglie==-1
altezzaFoglie = altezzaCorrente
restituisci vero
altrimenti
restituisci altezzaCorrente == altezzaFoglie
altrimenti
restituisci alberoCompleto( t->sinistro ) e alberoCompleto( t->destro )

dove ho segnato in rosso,fai delle chiamate della funzione albero completo senza passargli i parametri altezza foglie e altezza corrente...
in quel passaggio devo riportare i parametri così come sono o devo incrementarli/decrementarli??

[Doraemond]

deniele nel tuo pseudocodice

algoritmo Albero-Altezza(albero T) → intero {
se (T è vuoto) {
restituisci 0;
}
altrimenti {
restituisci 1 + max{ Albero-Altezza(T->sinistro), Albero-Altezza(T->destro) };
}
}

richiami una funzione max,ma di cosa si tratta??

[marco.r]

marco.r ma net tuo pseudocodice

dove ho segnato in rosso,fai delle chiamate della funzione albero completo senza passargli i parametri altezza foglie e altezza corrente...
in quel passaggio devo riportare i parametri così come sono o devo incrementarli/decrementarli??
scusa, ho appena corretto il codice. Devi incrementare il valore di altezzaCorrente di uno. altezzaFoglie invece va passato per puntatore perche' devi poterlo modificare.

[Doraemond]

/*Si consideri un Abero Binario di Ricerca caratterizzato da insieme di studenti:

Ad ogni studente corrisponde una struttura studente contenente i seguenti campi:
- Nome;
- Cognome ;
- Eta';


Si implementino:
una procedura per la creazione di un albero binario di ricerca A di studenti, ordinato per cognome;
una procedura per la stampa ordinata dei nodi dell'albero
una procedura per il calcolo del numero di Nodi dell'albero
una procedura per il calcolo del numero di Foglie dell'albero
una funzione ricorsiva booleana che verifica se l'albero ha tutte le foglie al medesimo livello
una funzione ricorsiva che, dato l'albero A e un intero n, restituisca gli n nodi più piccoli*/

#include<iostream>

using namespace std;

struct Tstudente{
char nome[20];
char cognome[20];
int eta;
Tstudente *sx,*dx;
};
typedef Tstudente *Pnodo;

void menu();
Pnodo crea_nodo(Tstudente x);
void inserimento(Pnodo &L,Tstudente x);
void stampa(Pnodo L,int i);
void conta_nodi(Pnodo L,int &);
void conta_foglie(Pnodo L,int &i);
void nodi_n(Pnodo L,int n);
bool completo(Pnodo L,int &altezzaFoglie,int altezzaCorrente);
int altezza(Pnodo L);

int main(){
int scelta,i=0,altezzaFoglie;
Tstudente temp;
Pnodo L;
L=new Tstudente;
L=NULL;
do{
menu();
cin>>scelta;
fflush(stdin);
switch(scelta){
case 1:
cout<<"INSERISCI COGNOME STUDENTE: ";
cin.getline(temp.cognome,20,'\n');
cout<<"INSERISCI NOME STUDENTE: ";
cin.getline(temp.nome,20,'\n');
cout<<"INSERISCI ETA STUDENTE: ";
cin>>temp.eta;
inserimento(L,temp);
cout<<"\n\tOPERAZIONE COMPLETATA\n\n";
break;
case 2:
stampa(L,0);
break;
case 3:
conta_nodi(L,i);
cout<<"L'ALBERO CONTIENE "<<i<<" NODI\n";
i=0;
break;
case 4:
conta_foglie(L,i);
cout<<"L'ALBERO CONTIENE "<<i<<" FOGLIE\n";
i=0;
break;
case 5:
altezzaFoglie=-1;
if(completo(L,altezzaFoglie,0))
cout<<"L'ALBERO HA TUTTE LE FOGLIE SULLO STESSO LIVELLO\n";
else
cout<<"L'ALBERO NON HA TUTTE LE FOGLIE SULLO STESSO LIVELLO\n";
break;
case 6:
cout<<"INSERIRE VALORE: ";
cin>>i;
nodi_n(L,i);
i=0;
cout<<"\n\n";
break;
case 7:
cout<<"\n\tCIAO :)\n\n";
break;
default:
cout<<"\n\tSCELTA ERRATA,RIPROVA!!\n\n";
break;
}
}while(scelta!=7);
system("pause");
return 0;
}

void menu(){
cout<<"1) INSERIMENTO NUOVO STUDENTE ORDINATO PER COGNOME\n";
cout<<"2) STAMPA ORDINATA NODI DELL'ALBERO\n";
cout<<"3) CALCOLA IL NUMERO DI NODI DELL'ALBERO\n";
cout<<"4) CALCOLA IL NUMERO DI FOGLIE DELL'ALBERO\n";
cout<<"5) VERIFICA SE L'ALBERO HA TUTTE LE FOGLIE AL MEDESIMO LIVELLO\n";
cout<<"6) RESTITUISCI I NODI DELL ALBERO MINORI DI UN VALORE DATO IN INPUT\n";
cout<<"7) ESCI\n";
cout<<"\t SCELTA: ";
}

Pnodo crea_nodo(Tstudente x){
Pnodo temp;
temp=new Tstudente;
strcpy(temp->cognome,x.cognome);
strcpy(temp->nome,x.nome);
temp->eta=x.eta;
temp->sx=NULL;
temp->dx=NULL;
}

void inserimento(Pnodo &L,Tstudente x){
if(L==NULL){
L=crea_nodo(x);
return;
}
else if(strcmp(x.cognome,L->cognome)>0)
inserimento(L->dx,x);
else if(strcmp(x.cognome,L->cognome)<0)
inserimento(L->sx,x);
else
cout<<"\n\tELEMENTO 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<<"\t";
}
cout<<L->cognome<<endl;
stampa(L->sx,i+1);
}
}

void conta_nodi(Pnodo L,int &i){
if(L!=NULL){
i++;
conta_nodi(L->sx,i);
conta_nodi(L->dx,i);
}
else
return;
}

void conta_foglie(Pnodo L,int &i){
if(L!=NULL){
if(L->sx==NULL && L->dx==NULL)
i++;
else{
conta_foglie(L->sx,i);
conta_foglie(L->dx,i);
}
}
}

void nodi_n(Pnodo L,int n){
if(L!=NULL){
nodi_n(L->sx,n);
nodi_n(L->dx,n);
if(L->eta < n)
cout<<L->cognome<<" --> ";
}
}

bool completo(Pnodo L,int &altezzaFoglie,int altezzaCorrente){
if(L==NULL){
if(altezzaFoglie==-1){
altezzaFoglie=altezzaCorrente;
return true;
}
else
return (altezzaCorrente == altezzaFoglie);
}
else
return completo(L->sx,altezzaFoglie,altezzaCorrente+1) && completo(L->dx,altezzaFoglie,altezzaCorrente+1);
}

questo è il codice completo che ho scritto,ma nn mi funge,nn so se ho sbagliato io o...
nel caso in cui inserisco un albero così:

P
K
G
C
B

l'algoritmo mi restituisce false quando poi dovrebbe restituirmi true!!

non so se il disegno viene bene ma la radice è g che ha come sottoalberi K e C
K ha sottoalbero P
C ha sottoalbero B

[DanieleC88]

deniele nel tuo pseudocodice [...] richiami una funzione max,ma di cosa si tratta??
Di una funzione che, dati n numeri in input, scelga il numero che ha il valore più grande.

[fero86]

ho visto ke mi ha dato il codice ma nn ci capisco nulla,siccome fatto cn le classi,quindi nn saprei come adattarlo al mio codice !! e studiare le classi allora no? :mbe:
perché ti ostini a chiamare C++ quello che di fatto é codice C? no perché scusa se te lo dico ma tuo "codice C++" fa schifo, non mi stupisce che tu non riesca a concludere dovendo avere a che fare con quella monnezza.

PS: non stai scrivendo SMS, scrivi in italiano corretto per cortesia.

[fero86]

richiami una funzione max,ma di cosa si tratta?? andiamo bene :asd:

[fero86]

Non hai fatto i conti con il caso medio :p.
Con la mia soluzione, il costo C per l'algoritmo e' il seguente:

C(t) = C(t->left) + 1 se t->left non e' bilanciato
= C(t->left) + 1 + C(t->right) altrimenti

Visto che nulla e' stato detto a riguardo, immagino che la distribuzione degli alberi sia uniforme. Ora, gli alberi completi sono solo una minima parte dei possibili ( O(log(n)) contro O(n) sul numero di nodi)
Nel primo caso il costo e' O(n), nel secondo O(log(n)). Il costo dell'algoritmo per tutti gli alberi e' quindi O(n)log(n) e quindi log(n) nel caso medio (invece che O(n)).

La dimostrazione non e' proprio formale, ma spero renda l'idea. credo di aver colto l'idea, ma guarda che anche la mia versione (con due funzioni, Height e Complete) si ferma subito se l'albero non é completo, questo grazie al fatto che il lazy AND non valuta la parte (Height() == Height()) quando una delle due parti Complete() restituisce false.

edit - e invece ho detto una parziale sciocchezza dato che fino a un certo punto, cioé fino a che la parte di albero esaminata é completa, Complete() chiama Height() :D

[fero86]

riformulo!
#include <iostream>
using namespace std;


class CNode {
public:
virtual unsigned int Height() const = 0;

bool Complete() const try {
Height();
return true;
} catch (bool) {
return false;
}
};

class CEmpty :
public CNode {
public:
virtual unsigned int Height() const {
return 0;
}
};

class CTree :
public CNode {
private:
CNode &m_rLeft;
CNode &m_rRight;

public:
CTree(CNode &a_rLeft, CNode &a_rRight)
:
m_rLeft(a_rLeft),
m_rRight(a_rRight) {
}

virtual unsigned int Height() const {
unsigned int nHeight = m_rLeft.Height();
if (nHeight != m_rRight.Height()) {
throw false;
}
return nHeight + 1;
}
};


int main() {
cout << CTree(CEmpty(), CEmpty()).Complete() << endl;
cout << CTree(CTree(CEmpty(), CEmpty()), CEmpty()).Complete() << endl;
cout << CTree(CEmpty(), CTree(CEmpty(), CEmpty())).Complete() << endl;
cout << CTree(CTree(CEmpty(), CEmpty()), CTree(CEmpty(), CEmpty())).Complete() << endl;
return 0;
}


questa versione usa una sola funzione ricorsiva :p
mi sono reso conto che due funzioni erano inutili riflettendo sul funzionamento della mia vecchia Height(): essa nel caso induttivo restituiva il massimo tra le due altezze dei sottoalberi, quindi "sprecava" un'informazione: quando trovava due sottoalberi di altezza diversa buttava via l'informazione del fatto che i due alberi sono di altezza diversa.

la nuova Height() in quel caso lancia un'eccezione, che viene catturata dalla Complete() che in quel caso restituisce false. la Complete non é piu ne' virtuale ne' ricorsiva, serve solo come wrapper per la chiamata iniziale di Height().

[Doraemond]

fero guarda che questo è il primo anno che studio informatica e cn il prof siamo arrivati a questo,le classi le studierò l'anno prox ,x ora abbiamo fatto solo un accenno delle classi x qst nn sn pronto a programmare cn le classi...so k c++ usa gli oggetti ma x ora di programmaz ad oggetti nn ne ho fatta....e poi se l'esercizio mi è stato assegnato 2 mesi fa senza aver ancora introdotto le classi,ci sn solo 2 risposte,o dv farlo senza classi o il mio prof è pazzo!!

[DanieleC88]

Mi viene in mente che se si strutturasse l'albero in modo che ogni nodo conservi il numero di nodi contenuti nel sottoalbero in esso radicato e l'altezza del sottoalbero in questione, allora la soluzione sarebbe O(1).
Chiamato n il numero di nodi nell'albero ed h l'altezza dell'albero (quindi i campi di cui dicevo prima, letti dalla radice), allora basterà controllare che sia n = 2^h - 1.
È il solito compromesso spazio/tempo.

ciao ;)

[Doraemond]

bool compara_foglie(Pnodo rad){
if(rad==NULL)
return true;
else if(compara_foglie(rad->sx)&& compara_foglie(rad->dx)&& altezza(rad->sx,rad->dx))
return true;
else
return false;
}

bool altezza(Pnodo radsx,Pnodo raddx){
if(radsx && raddx){
int min=10000;
int max=0;
high(radsx,0,max,min);
high(raddx,0,max,min);
if(max-min==0)
return true;
else
return false;
}
else
return true;
}

void high(Pnodo rad,int livello,int& max,int& min){
if(rad!=NULL){
if(rad->sx==NULL && rad->dx==NULL){
if(livello>max)
max=livello;
if(livello<min)
min=livello;
}
high(rad->sx,livello+1,max,min);
high(rad->dx,livello+1,max,min);
}
}


questo è il codice che mi ha passato un mio amico e funziona!!

[fero86]

questo è il codice che mi ha passato un mio amico e funziona!! buon per te; ora puoi andare a studiarti le classi e tutto il resto del C++, cosi capisci anche come mai quel codice fa schifo.

[DanieleC88]

cosi capisci anche come mai quel codice fa schifo.
Non serve studiare il C++ per capirlo, lo si vede già così. :cool:
:Prrr: