[C++] BST - FOGLIE SULLO STESSO LIVELLO

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

Originariamente inviato da Doraemond

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]

Originariamente inviato da Doraemond

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]

Originariamente inviato da 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 !!

e studiare le classi allora no?
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]

Originariamente inviato da Doraemond

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

andiamo bene

[fero86]

Originariamente inviato da marco.r

Non hai fatto i conti con il caso medio .
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()

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

Originariamente inviato da Doraemond

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]

Originariamente inviato da fero86

cosi capisci anche come mai quel codice fa schifo.

Non serve studiare il C++ per capirlo, lo si vede già così.