PDA

Visualizza la versione completa : [C++] Albero binario: implementazione del metodo SwapTree


pietrol83
20-02-2012, 13:05
ciao a tutti, sto creando una class Utiltree, dove tra i metodi c' SwapTree che inverte il nodo figlio destro con il figlio sinitro di tutto l'albero. come prtrei fare??? le sto provando tutte ma non ci riesco a implementare il nodo.
la segnatura del metodo Swaptree la seguente:

void SwapTree()

ramy89
20-02-2012, 21:42
Posta il codice.

pietrol83
20-02-2012, 22:34
il problema che devo fare il codice. ho bisogno di implementare un metodo che, dato un albero binario, inverta il figlio sinistro con quello destro di ogni nodo. non so come farlo.

ramy89
20-02-2012, 23:02
L' albero binario c' da qualche parte, hai una classe? :confused:

pietrol83
21-02-2012, 12:31
l'albero binario l'ho implementato ed il seguente:

nodoalberop.h


#ifndef nodoalberop_h
#define nodoalberop_h

#include<iostream>
#include<stdlib.h>

using namespace std;

template<class tipoelem>
class nodoalberop
{
public:
nodoalberop();

void setpadre(nodoalberop *);
void setfigliosx(nodoalberop *);
void setfigliodx(nodoalberop *);
void setetichetta(tipoelem);

nodoalberop *getpadre();
nodoalberop *getfigliosx();
nodoalberop *getfigliodx();
tipoelem getetichetta();

nodoalberop operator=(nodoalberop);
private:
nodoalberop *padre;
nodoalberop *figliosx;
nodoalberop *figliodx;
tipoelem etichetta;
};

#endif

template<class tipoelem>
nodoalberop<tipoelem>::nodoalberop()
{
padre = NULL;
figliosx = NULL;
figliodx = NULL;
etichetta = 0;
}

template<class tipoelem>
void nodoalberop<tipoelem>::setpadre(nodoalberop<tipoelem> *p)
{
padre = p;
}

template<class tipoelem>
void nodoalberop<tipoelem>::setfigliosx(nodoalberop<tipoelem> *fsx)
{
figliosx = fsx;
}

template<class tipoelem>
void nodoalberop<tipoelem>::setfigliodx(nodoalberop<tipoelem> *fdx)
{
figliodx = fdx;
}

template<class tipoelem>
void nodoalberop<tipoelem>::setetichetta(tipoelem elem)
{
etichetta = elem;
}

template<class tipoelem>
nodoalberop<tipoelem>::nodoalberop<tipoelem> *nodoalberop<tipoelem>::getpadre()
{
return(padre);
}

template<class tipoelem>
nodoalberop<tipoelem>::nodoalberop<tipoelem> *nodoalberop<tipoelem>::getfigliosx()
{
return(figliosx);
}

template<class tipoelem>
nodoalberop<tipoelem>::nodoalberop<tipoelem> *nodoalberop<tipoelem>::getfigliodx()
{
return(figliodx);
}

template<class tipoelem>
tipoelem nodoalberop<tipoelem>::getetichetta()
{
return(etichetta);
}

template<class tipoelem>
nodoalberop<tipoelem> nodoalberop<tipoelem>::operator=(nodoalberop<tipoelem> node)
{
this->setpadre(node.getpadre());
this->setfigliosx(node.getfigliosx());
this->setfigliodx(node.getfigliodx());
this->setetichetta(node.getetichetta());
}

binalberop.h

#ifndef alberobinp_h
#define alberobinp_h

#include "nodoalberop.h"
#include<iostream>
#include<stdlib.h>

using namespace std;

template<class tipoelem>
class alberobinp
{
public:
typedef nodoalberop<tipoelem> *nodo;
alberobinp();

void creabinalbero();
bool binalberovuoto();
nodo binradice();
nodo binpadre(nodo);
nodo figliosinistro(nodo);
nodo figliodestro(nodo);
bool sinistrovuoto(nodo);
bool destrovuoto(nodo);
tipoelem legginodo(nodo);
void scrivinodo(nodo, tipoelem);
void insbinradice(nodo);
void insfigliosinistro(nodo);
void insfigliodestro(nodo);
void cancsottoalbero(nodo);
private:
nodo radice;
};

#endif

template<class tipoelem>
alberobinp<tipoelem>::alberobinp()
{
this->creabinalbero();
}

template<class tipoelem>
void alberobinp<tipoelem>::creabinalbero()
{
radice = NULL;
}

template<class tipoelem>
bool alberobinp<tipoelem>::binalberovuoto()
{
return(radice == NULL);
}

template<class tipoelem>
typename alberobinp<tipoelem>::nodo alberobinp<tipoelem>::binradice()
{
return(radice);
}

template<class tipoelem>
typename alberobinp<tipoelem>::nodo alberobinp<tipoelem>::binpadre(typename alberobinp<tipoelem>::nodo node)
{
return(node->getpadre());
}

template<class tipoelem>
typename alberobinp<tipoelem>::nodo alberobinp<tipoelem>::figliosinistro(typename alberobinp<tipoelem>::nodo node)
{
return(node->getfigliosx());
}

template<class tipoelem>
typename alberobinp<tipoelem>::nodo alberobinp<tipoelem>::figliodestro(typename alberobinp<tipoelem>::nodo node)
{
return(node->getfigliodx());
}

template<class tipoelem>
bool alberobinp<tipoelem>::sinistrovuoto(typename alberobinp<tipoelem>::nodo node)
{
return(node->getfigliosx() == NULL);
}

template<class tipoelem>
bool alberobinp<tipoelem>::destrovuoto(typename alberobinp<tipoelem>::nodo node)
{
return(node->getfigliodx() == NULL);
}

template<class tipoelem>
void alberobinp<tipoelem>::insbinradice(typename alberobinp<tipoelem>::nodo node)
{
radice = node;
}

template<class tipoelem>
void alberobinp<tipoelem>::insfigliosinistro(typename alberobinp<tipoelem>::nodo node)
{
nodo temp = new nodoalberop<tipoelem>;
node->setfigliosx(temp);
temp->setpadre(node);
}

template<class tipoelem>
void alberobinp<tipoelem>::insfigliodestro(typename alberobinp<tipoelem>::nodo node)
{
nodo temp = new nodoalberop<tipoelem>;
node->setfigliodx(temp);
temp->setpadre(node);
}

template<class tipoelem>
void alberobinp<tipoelem>::cancsottoalbero(alberobinp<tipoelem>::nodo node)
{
if(node->getfigliosx() != NULL)
this->cancsottoalbero(node->getfigliosx());
if(node->getfigliodx() != NULL)
this->cancsottoalbero(node->getfigliodx());
if(node == this->binradice())
radice = NULL;
delete node;
}

ora l'esercizio mi chiede di implkementare la seguente classe:

class UtilTree
{
public:
void SwapTree();
void RemoveLeavesTree();
bool SubTree(alberobinp<tipoelem>);
private:
alberobinp<tipoelem> tree;
};

in pratica come potrei implementare il metodo SwapTree??

Loading