corso ASD
Corso di Algoritmi e Strutture Dati a.a. 2013/2014

Esercizio 04

Si consideri la seguente implementazione di albero binario, commentata a lezione. Successivamente si esegua l'esercizio richiesto. Dopo aver testato adeguatamente la struttura, ed aver realizzato tutti i punti richiesti, inviare all'indirizzo paolo.buono@uniba.it l'esercitazione, in una cartella compressa in formato zip. Il file deve essere chiamato: "[ASDBR1314] esercizio04 - cognome.zip" e deve contenere solo file .h, .cpp, e il file di progetto. Scadenza dell'invio dell'esercitazione: 23.59 di domenica 1 dicembre.

//  main.cpp
#include <iostream>
 #include "alberobin.h"
int main(int argc, const char * argv[]){

    Alberobin test;
    //aggiungere codice...
    
    std::cout << "Hello, World!\n";
    return 0;
}
//  alberobin.h
#ifndef _alberobin_h
#define _alberobin_h

#include <iostream>
#include "nodoalberobin.h"

typedef bool boolean;

class Alberobin {
public:
    Alberobin();
    ~Alberobin();       
    void creaBinalbero();

        boolean binalberoVuoto();
        NodoB  binRadice();
        NodoB  binPadre(NodoB);
        NodoB  figlioSinistro(NodoB);
        NodoB  figlioDestro(NodoB);
        boolean sinistroVuoto(NodoB);
        boolean destroVuoto(NodoB);

        tipoelem leggiNodo(NodoB);
        void scriviNodo(tipoelem, NodoB);

        void insRadice();
        void insFiglioSinistro(NodoB);
        void insFiglioDestro(NodoB);
        void cancSottoBinalbero(NodoB);

private:
    NodoB  albero;
};

#endif
//  alberobin.cpp
#include "alberobin.h"
#include <iostream>
using namespace std;

Alberobin::Alberobin() {
        creaBinalbero();
}

Alberobin::~Alberobin() {
}

void Alberobin::creaBinalbero(){
        albero = NULL;
}

boolean Alberobin::binalberoVuoto() {
        return (albero == NULL);
}

NodoB Alberobin::binRadice() {
                return albero;
}

NodoB Alberobin::binPadre(NodoB u) {
        if (!binalberoVuoto() && u != binRadice())
                return u->getGenitore();
        else
                return NULL;
}

NodoB Alberobin::figlioSinistro(NodoB u) {
        if (!binalberoVuoto() && !sinistroVuoto(u))
                return u->getSinistro();
        else
                return NULL;
}

NodoB Alberobin::figlioDestro(NodoB u) {
        if (!binalberoVuoto() && !destroVuoto(u))
                return u->getDestro();
        else
                return NULL;
}

boolean Alberobin::sinistroVuoto(NodoB u) {
        return (u->getSinistro() == NULL);
}

boolean Alberobin::destroVuoto(NodoB u) {
        return (u->getDestro() == NULL);
}

tipoelem Alberobin::leggiNodo(NodoB u) {
        return u->contenuto();
}

void Alberobin::scriviNodo(tipoelem elem, NodoB u) {
        u->contenuto(elem);
}

void Alberobin::insRadice() {
        if (binalberoVuoto())
                albero = new NodoAlberobin;
}

void Alberobin::insFiglioSinistro(NodoB u) {
        if ((!binalberoVuoto()) && (sinistroVuoto(u))) {
                NodoB temp = new NodoAlberobin;
                u->setSinistro(temp);
                temp->setGenitore(u);
        };
}

void Alberobin::insFiglioDestro(NodoB u) {
        if ((!binalberoVuoto()) && (destroVuoto(u))) {
                NodoB temp = new NodoAlberobin;
        u->setDestro(temp);
                temp->setGenitore(u);
        };
}

/**restituisce nodo padre del nodo u da cancellare, NULL se u radice*/
void Alberobin::cancSottoBinalbero(NodoB u) {
        if (!binalberoVuoto()) {
                if (u == albero)
                        delete albero;
                else {
                        NodoB padre;
                        padre = u->getGenitore();
                        if (padre->getSinistro() == u)
                                delete padre->getSinistro();
                        else
                                delete padre->getDestro();
                };
        };
}
//  nodoalberobin.h
#ifndef _nodoalberobin_h
#define _nodoalberobin_h
#include "elemento.h"

typedef Elemento tipoelem;
class NodoAlberobin;
typedef NodoAlberobin * NodoB; //notazione piu leggera

class NodoAlberobin {
public:
        NodoAlberobin();
        ~NodoAlberobin();
    
        void contenuto(tipoelem);
        tipoelem contenuto();
    
        void setSinistro(NodoB);
        NodoB getSinistro();
    
        void setDestro(NodoB);
        NodoB getDestro();
    
        void setGenitore(NodoB);
        NodoB getGenitore();
    
private:
        tipoelem etichetta;
        NodoB sinistro;
        NodoB destro;
        NodoB genitore;
};

#endif

//  nodoalberobin.cpp
#include "nodoalberobin.h"

NodoAlberobin::NodoAlberobin() {
        sinistro = destro = genitore = 0;//impostati a NULL (0) i puntatori
}

void NodoAlberobin::contenuto(tipoelem elem) {
        etichetta = elem;
}
tipoelem NodoAlberobin::contenuto() {
        return etichetta;
}
//se passo puntatore vuoto cancella il nodo puntato da sinistro void NodoAlberobin::setSinistro(NodoB sx) {
        if (sx == 0)
        delete sinistro;
        else
                sinistro = sx;
}

NodoB NodoAlberobin::getSinistro() {
        return sinistro;
}

void NodoAlberobin::setDestro(NodoB dx) {
        if (dx == 0)
                delete destro;
        destro = dx;
}

NodoB NodoAlberobin::getDestro() {
        return destro;
}

void NodoAlberobin::setGenitore(NodoB padre) {
        //non imposta il genitore del nodo radice        
        genitore = padre;
}

NodoB NodoAlberobin::getGenitore() {
        return genitore;
}

NodoAlberobin::~NodoAlberobin() {
        delete sinistro;
        delete destro;
        delete genitore;
}
//  elemento.h
#ifndef elemento_h
#define elemento_h

#include <string>
using namespace std;

class Elemento{
public:
    string nome();
    void nome(string);
    
    string matricola();
    void matricola(string);

private:
    string _nome;
    string _matricola;
};

#endif
//  elemento.cpp
#include "elemento.h"

string Elemento::nome(){
    return _nome;
};

void Elemento::nome(string nome){
    _nome=nome;
};

string Elemento::matricola(){
    return _matricola;
};

void Elemento::matricola(string matricola){
    _matricola=matricola;
};
//  codaalberobin.h
#ifndef _CodaAlberoBin_h
#define _CodaAlberoBin_h

const int MAXLUNG=100;

#include "nodoalberobin.h"

class CodaAB{
public:
    CodaAB();
    ~CodaAB();
    void creaCoda();
    bool codaVuota() const;
    NodoB leggiCoda() const;
    void fuoriCoda();
    void inCoda (NodoB);
private:
    NodoB elementi[MAXLUNG];
    int testa;
    int lunghezza;
};

#endif //CodaAlberoBin_h
// codaalberobin.cpp
#include <iostream>
#include <assert.h>
#include "codalberobin.h"

using namespace std;

CodaAB::CodaAB(){
    creaCoda();
}

CodaAB::~CodaAB() {};

void CodaAB::creaCoda(){
    testa=0;
    lunghezza=0;
}

bool CodaAB::codaVuota() const {
    return (lunghezza==0);
}

NodoAlberobin* CodaAB::leggiCoda() const {
    assert (!codaVuota());
    return elementi[testa];
}

void CodaAB::inCoda(NodoAlberobin* el){
    assert (testa<=MAXLUNG);
    elementi[(testa+lunghezza)%MAXLUNG]=el;
    lunghezza++;
}

void CodaAB::fuoriCoda() {
    assert (!codaVuota());
    testa=(testa+1)%MAXLUNG;
    lunghezza--;
}
// visitealberobin.h
#ifndef _visitealberobin_h
#define _visitealberobin_h

#include <iostream>
#include "alberobin.h"
#include "codalberobin.h"

void previsita (NodoAlberobin *, Alberobin);
void postvisita(NodoAlberobin *, Alberobin);
void simmetrica(NodoAlberobin *, Alberobin);
void bfs(Alberobin); 

#endif
// visitealberobin.h
#include "visitealberobin.h"
#include <iostream>
using namespace std;


// visita in preordine
void previsita(NodoB u, Alberobin T) {
        if (!T.binalberoVuoto()) {
                cout << "["<<T.leggiNodo(u).matricola()<<","<< T.leggiNodo(u).nome() << ", ";
                if (!T.sinistroVuoto(u))
                        previsita(T.figlioSinistro(u), T);
        else cout << "_";
        cout<<", ";
                if (!T.destroVuoto(u))
                        previsita(T.figlioDestro(u), T);
        else cout << "_";
        cout << "]";
        }
}

//simmetrica postordine
void postvisita(NodoB u, Alberobin T) {
        if (!T.binalberoVuoto()) {
                if (!T.sinistroVuoto(u)) {
                        postvisita(T.figlioSinistro(u), T);
                }
                if (!T.destroVuoto(u)) {
                        postvisita(T.figlioDestro(u), T);
                }
                cout << "["<<T.leggiNodo(u).matricola()<<","<< T.leggiNodo(u).nome() << ", ";
        };
}

//visita simmetrica
void simmetrica(NodoB u, Alberobin T) {
        if (!T.binalberoVuoto()) {
                if (!T.sinistroVuoto(u)) {
                        simmetrica(T.figlioSinistro(u), T);
                }
                cout << "["<<T.leggiNodo(u).matricola()<<","<< T.leggiNodo(u).nome() << ", ";
                if (!T.destroVuoto(u)) {
                        simmetrica(T.figlioDestro(u), T);
                }
        };
}

// visita dell'albero per livello
void bfs(Alberobin T) {
        CodaAB c;
        NodoB x;
      
        c.creaCoda();
        if (!T.binalberoVuoto()) {
                cout << "["<<T.leggiNodo(T.binRadice()).matricola()<<","<<T.leggiNodo(T.binRadice()).nome()<< "] ";
                c.inCoda(T.binRadice());
                while (!c.codaVuota()) {
                        x = c.leggiCoda();
                        c.fuoriCoda();
                        if (!T.sinistroVuoto(x)) {
                                cout << "["<<T.figlioSinistro(x)->contenuto().matricola()<<","<<T.figlioSinistro(x)->contenuto().nome()<< " ";
                                c.inCoda(T.figlioSinistro(x));
                        }
                        if (!T.destroVuoto(x)) {
                                cout << "["<<T.figlioDestro(x)->contenuto().matricola()<<","<<T.figlioDestro(x)->contenuto().nome()<< " ";
                                c.inCoda(T.figlioDestro(x));
                        }
                }
        }
}

Si realizzino le seguenti funzioni / metodi:

  1. Funzione Alberobin popolaAlbero(Alberobin), che inserisce sette nodi nell'albero;
  2. Funzione Alberobin trovaNodo(Alberobin, stringa) che cerchi il nodo avente per etichetta una matricola scelta dall'utente e stampi matricola e nome dello studente;
  3. Funzione Alberobin eliminaSottoAlbero(Alberobin, Nodo) che consente la potatura dell'albero a partire dal nodo passato dalla funzione trovaNodo;

Creare un nuovo tipo di nodo che contenga un carattere nell'insieme {'+', '-', '*', '/', '(', ')'} ed un numero, e sostituire il nodo dell'albero binario esistente. Si realizzino le seguenti funzioni / metodi:

  1. inserimento di un'espressione algebrica nell'albero, con input chiesto dall'utente;
  2. string stampaEspressione(), chedell'espressione algebrica inserita;
  3. float calcoloEspressione(), che risolve l'espressione dandone il risultato.
corso ASD