Salve ragazze sono disperato, non capisco come implementare una funzione che restituisca un nodo nuovo su cui è stata effettuata la copia di un alber binario.
La struttura astratta che ho creato è questa:
#include <iostream>
using namespace std;
template <class T, class N>
class Albero_binario_astratto{
public:
typedef T tipo;
typedef N Nodo;
//Operatori
virtual void crea() = 0;
virtual bool vuoto() const = 0;
virtual Nodo radice() const = 0;
virtual Nodo genitore(Nodo) const = 0;
virtual Nodo sinistro(Nodo) const = 0;
virtual Nodo destro(Nodo) const = 0;
virtual bool sinistro_vuoto(Nodo) const = 0;
virtual bool destro_vuoto(Nodo) const = 0;
virtual void cancella(Nodo) = 0;
virtual tipo leggi(Nodo) const = 0;
virtual void scrivi(Nodo, tipo) = 0;
virtual void inserire_radice(Nodo) = 0;
virtual void inserire_sinistro(Nodo) = 0;
virtual void inserire_destro(Nodo) = 0;
//funzioni di servizio da implementare qui
//virtual void previsita(Nodo);
//virtual void invisita(Nodo);
//virtual void postvisita(Nodo);
//funzione di stampa
virtual void stampa() const;
void visita();
private:
virtual void stampa_sottoalbero(const Nodo) const;
};
L'implementazione della classe astratta è questa ed è stata fatta con puntatori:
#include <iostream>
#include "Albero_binario_astratto.h"
#include "alberobinario_eccezioni.h"
template <class T>
class Albero_binario_p;
template <class T>
class cella{
friend class Albero_binario_p<T>;
public:
cella<T>* genitore;
cella<T>* sinistro;
cella<T>* destro;
T valore;
};
template <class T>
class Albero_binario_p : public Albero_binario_astratto<T, cella<T>*>{
public:
typedef typename Albero_binario_astratto<T, cella<T>*>::tipo tipo;
typedef typename Albero_binario_astratto<T, cella<T>*>::Nodo Nodo;
//Costruttore e distruttore
Albero_binario_p();
~Albero_binario_p();
//Operatori
void crea();
bool vuoto() const;
Nodo radice() const;
Nodo genitore(Nodo) const;
Nodo sinistro(Nodo) const;
Nodo destro(Nodo) const;
bool sinistro_vuoto(Nodo) const;
bool destro_vuoto(Nodo) const;
void cancella(Nodo);
T leggi(Nodo) const;
void scrivi(Nodo, tipo);
void inserire_radice(Nodo);
void inserire_sinistro(Nodo);
void inserire_destro(Nodo);
Nodo copiaSottoAlbero(Nodo t, Nodo g);
public:
cella<T>* inizio;
};
//Ok
template <class T>
Albero_binario_p<T>::Albero_binario_p(){
crea();
}
//Ok
template <class T>
Albero_binario_p<T>::~Albero_binario_p(){
cancella(radice());
delete inizio;
}
//Ok
template <class T>
void Albero_binario_p<T>::crea(){
inizio = new cella<T>;
inizio->genitore = inizio;
inizio->sinistro = nullptr;
inizio->destro = nullptr;
}
//Ok
template <class T>
bool Albero_binario_p<T>::vuoto() const{
return (inizio->sinistro == nullptr && inizio->destro == nullptr);
}
//Ok
template <class T>
typename Albero_binario_p<T>::Nodo Albero_binario_p<T>::radice() const{
return inizio;
}
//Ok
template <class T>
typename Albero_binario_p<T>::Nodo Albero_binario_p<T>::genitore(Nodo n) const{
if(n != nullptr)
return n->genitore;
else
throw NodoNullo();
}
//Ok
template <class T>
typename Albero_binario_p<T>::Nodo Albero_binario_p<T>::sinistro(Nodo n) const{
if(n != nullptr)
return n->sinistro;
else
throw NodoNullo();
}
//Ok
template <class T>
typename Albero_binario_p<T>::Nodo Albero_binario_p<T>::destro(Nodo n) const{
if(n != nullptr)
return n->destro;
else
throw NodoNullo();
}
//Ok
template <class T>
bool Albero_binario_p<T>::sinistro_vuoto(Nodo n) const{
if(n != nullptr)
{
bool esito = false;
if (n->sinistro == n)
esito = true;
else
esito = false;
return esito;
}
else
throw NodoNullo();
}
//Ok
template <class T>
bool Albero_binario_p<T>::destro_vuoto(Nodo n) const{
if(n != nullptr)
{
bool esito = false;
if (n->destro == n)
esito = true;
else
esito = false;
return esito;
}
else
throw NodoNullo();
}
//Ok
template <class T>
void Albero_binario_p<T>::cancella(Nodo n){
if (!vuoto())
{
if(sinistro(n) != n)
{
cancella(sinistro(n));
}
if(destro(n) != n)
{
cancella(destro(n));
}
if(n == radice())
{
n->sinistro = nullptr;
n->destro = nullptr;
}
else
{
if(sinistro(genitore(n)) == n)
{
n->genitore->sinistro = n->genitore;
delete n;
}
else
{
n->genitore->destro = n->genitore;
delete n;
}
}
}
}
template <class T>
T Albero_binario_p<T>::leggi(Nodo n) const{
if(n != nullptr)
return n->valore;
else
throw NodoNullo();
}
template <class T>
void Albero_binario_p<T>::scrivi(Nodo n, tipo v){
if(!vuoto())
{
if(n != nullptr)
n->valore = v;
else
throw NodoNullo();
}
else
throw AlberoVuoto();
}
template <class T>
void Albero_binario_p<T>::inserire_radice(Nodo n){
if(vuoto())
{
if(n != nullptr)
{
inizio = n;
inizio->sinistro = n;
inizio->destro = n;
inizio->genitore = n;
}
else
throw NodoNullo();
}
else
throw RadiceEsiste();
}
template <class T>
void Albero_binario_p<T>::inserire_sinistro(Nodo n){
if(!vuoto())
{
if(sinistro_vuoto(n))
{
cella<T>* nuovo = new cella<T>;
n->sinistro = nuovo;
n->sinistro->sinistro = n->sinistro;
n->sinistro->destro = n->sinistro;
n->sinistro->genitore = n;
}
else
throw NodoEsiste();
}
else
throw AlberoVuoto();
}
template <class T>
void Albero_binario_p<T>::inserire_destro(Nodo n){
if(!vuoto())
{
if(destro_vuoto(n))
{
cella<T>* nuovo = new cella<T>;
n->destro = nuovo;
n->destro->sinistro = n->destro;
n->destro->destro = n->destro;
n->destro->genitore = n;
}
else
throw NodoEsiste();
}
else
throw AlberoVuoto();
}
In sostanza il mio albero binario è così implementato:
- La variabile "inizio" punta alla radice dell'albero;
- Dalla variabile "inizio" è possibile accedere al campo valore, indirizzo figlio destro e indirizzo figlio sinistro e così via.
- Di ogni nodo sappiamo figlio destro, figlio sinistro e genitore.
- La radice ha come genitore se stessa
- In caso non vi sia discendente sinistro o destro allora il nodo punterà a se stesso (Ho usato questa soluzione perchè se uso nullptr o NULL crasha e non so come risolvere)
IL PROBLEMA E' IL SEGUENTE:
- Come faccio a creare una funzione tipo questa: Nodo creaSottoAlbero(Nodo)
In sostanza io passo un qualsiasi nodo di un altro albero alla funzione e questa restituisce un nodo su cui è stato creato un albero di copia.
Questa funzione potrà quindi essere usata per il costruttore di copia.
Il punto è che non riesco a capire come mantenere i collegamenti fra le varie celle. Come faccio a non perdere l'indirizzo del genitore?
Ho abbozzato una soluzione davvero pessima :
template <class T>
typename Albero_binario_p<T>::Nodo Albero_binario_p<T>::copiaSottoAlbero(Nodo t, Nodo g){
cella<T>* nuovo = new cella<T>;
nuovo->genitore = g;
nuovo->valore = t->valore;
if(t->sinistro != t){
nuovo->sinistro = copiaSottoAlbero(t->sinistro, nuovo->genitore);
} else nuovo->sinistro = nuovo;
if(t->destro != t){
nuovo->destro = copiaSottoAlbero(t->destro, nuovo->genitore);
} else nuovo->destro = nuovo;
return nuovo;
}
In sostanza passo alla funzione due campi: il nodo da copiare e il genitore del vecchio nodo in modo da non perdere l'indirizzo. Ma ovviamente non funziona e non capisco davvero come risolvere. Se non ci fosse il collegamento nodo->genitore sarebbe molto più facile perchè basterebbe scendere nell'albero in maniera ricorsiva e copiare il valore.
Qualche soluzione, anche solo teorica???