ciao a tutti, ho creato un albero binario di ricerca e tra i metodi da testare ce n'è uno che fa una cosa strana. in pratica nell'inserimento dei nodi, il primo nodo da inserire è la radice. nel fare ciò il metodo ha un'if per controllare se l'albero è vuoto o meno in modo da decidere se inserire la radice o un figlio; inizialmente il controllo dell'if è vero ma dopo aver eseguito il blocco "then" esegue anche un'istruzione del blocco "else". ho controllato anche le parentesi e sono bilanciate, quindi non dovrebbero esserci problemi. come mai fa questa cosa??? posto i codici.
nodoalberop.h
codice:
#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);
void setchiave(int);
nodoalberop *getpadre();
nodoalberop *getfigliosx();
nodoalberop *getfigliodx();
tipoelem getetichetta();
int getchiave();
nodoalberop operator=(nodoalberop);
int livello;
private:
nodoalberop *padre;
nodoalberop *figliosx;
nodoalberop *figliodx;
tipoelem etichetta;
int chiave;
};
#endif
template<class tipoelem>
nodoalberop<tipoelem>::nodoalberop()
{
padre = NULL;
figliosx = NULL;
figliodx = NULL;
livello = -1;
}
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>
void nodoalberop<tipoelem>::setchiave(int key)
{
chiave = key;
}
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>
int nodoalberop<tipoelem>::getchiave()
{
return chiave;
}
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());
}
alberobinp.h
codice:
#ifndef alberobinp_h
#define alberobinp_h
#include "nodoalberop.h"
#include<assert.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 figliosx(nodo);
nodo figliodx(nodo);
bool sxvuoto(nodo);
bool dxvuoto(nodo);
tipoelem legginodo(nodo);
void scrivinodo(nodo, tipoelem);
void insbinradice(nodo);
void insfigliosx(nodo);
void insfigliodx(nodo);
void cancsottoalbero(nodo);
protected:
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()
{
assert(!this->binalberovuoto());
return(radice);
}
template<class tipoelem>
typename alberobinp<tipoelem>::nodo alberobinp<tipoelem>::binpadre(typename alberobinp<tipoelem>::nodo node)
{
assert(!this->binalberovuoto() && (node != radice));
return(node->getpadre());
}
template<class tipoelem>
typename alberobinp<tipoelem>::nodo alberobinp<tipoelem>::figliosx(typename alberobinp<tipoelem>::nodo node)
{
assert(!this->binalberovuoto());
return(node->getfigliosx());
}
template<class tipoelem>
typename alberobinp<tipoelem>::nodo alberobinp<tipoelem>::figliodx(typename alberobinp<tipoelem>::nodo node)
{
assert(!this->binalberovuoto());
return(node->getfigliodx());
}
template<class tipoelem>
bool alberobinp<tipoelem>::sxvuoto(typename alberobinp<tipoelem>::nodo node)
{
assert(!this->binalberovuoto());
return(node->getfigliosx() == NULL);
}
template<class tipoelem>
bool alberobinp<tipoelem>::dxvuoto(typename alberobinp<tipoelem>::nodo node)
{
assert(!this->binalberovuoto());
return(node->getfigliodx() == NULL);
}
template<class tipoelem>
tipoelem alberobinp<tipoelem>::legginodo(typename alberobinp<tipoelem>::nodo node)
{
return(node->getetichetta());
}
template<class tipoelem>
void alberobinp<tipoelem>::scrivinodo(typename alberobinp<tipoelem>::nodo node, tipoelem elem)
{
node->setetichetta(elem);
}
template<class tipoelem>
void alberobinp<tipoelem>::insbinradice(typename alberobinp<tipoelem>::nodo node)
{
assert(this->binalberovuoto());
radice = node;
}
template<class tipoelem>
void alberobinp<tipoelem>::insfigliosx(typename alberobinp<tipoelem>::nodo node)
{
assert(!this->binalberovuoto() && this->sxvuoto(node));
nodo temp = new nodoalberop<tipoelem>;
node->setfigliosx(temp);
temp->setpadre(node);
}
template<class tipoelem>
void alberobinp<tipoelem>::insfigliodx(typename alberobinp<tipoelem>::nodo node)
{
assert(!this->binalberovuoto() && this->dxvuoto(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;
}
bstreep.h
codice:
#ifndef bstreep_h
#define bstreep_h
#include "alberobinp.h"
#include<iostream>
#include<stdlib.h>
#include<assert.h>
template<class tipoelem>
class bstreep : public alberobinp<tipoelem>
{
public:
typedef nodoalberop<tipoelem> *nodo;
bstreep();
tipoelem min();
bool appartiene(nodo);
void inserisci(nodo);
void cancella(nodo);
};
#endif
template<class tipoelem>
bstreep<tipoelem>::bstreep()
{}
template<class tipoelem>
tipoelem bstreep<tipoelem>::min()
{
nodo min = this->binradice();
while(!this->sxvuoto(min))
min = this->figliosx(min);
return min->getetichetta();
}
template<class tipoelem>
bool bstreep<tipoelem>::appartiene(typename bstreep<tipoelem>::nodo node)
{
bool trovato = false;
nodo tmp = this->binradice();
while(!trovato && !(this->sxvuoto(tmp) && this->dxvuoto(tmp)))
{
if(tmp->getetichetta() == node->getetichetta())
trovato = true;
else
{
if(tmp->getchiave()< node->getchiave())
tmp = this->figliodx(tmp);
else
tmp = this->figliosx(tmp);
}
}
return trovato;
}
template<class tipoelem>
void bstreep<tipoelem>::inserisci(typename bstreep<tipoelem>::nodo node)
{
if(this->binalberovuoto())
this->insbinradice(node);
else
{
typename alberobinp<tipoelem>::nodo tmp = this->binradice();
bool trovato = false;
if(!this->appartiene(node))
{
while(!trovato)
{
if(node->getchiave() < tmp->getchiave())
{
if(this->sxvuoto(tmp))
{
this->insfigliosx(tmp);
trovato = true;
}
else
tmp = this->figliosx(tmp);
}
else
{
if(this->dxvuoto(tmp))
{
this->insfigliodx(tmp);
trovato = true;
}
else
tmp = this->figliodx(tmp);
}
}
}
}
}
template<class tipoelem>
void bstreep<tipoelem>::cancella(typename bstreep<tipoelem>::nodo node)
{
if(this->sxvuoto(node) && this->dxvuoto(node))
this->cancsottoalbero(node);
else
{
if(!this->sxvuoto(node) && !this->dxvuoto(node))
{
nodo tmp = this->min();
this->cancella(this->min());
node->getetichetta() = tmp->getetichetta();
node->getchiave() = tmp->getchiave();
}
else
{
if(this->sxvuoto(node) && !this->dxvuoto(node))
{
nodo tmp = this->figliodx(node);
node->setfigliodx(NULL);
this->cancsottoalbero(node);
if(node == this->figliosx(this->padre(node)))
this->insfigliosx(tmp);
else
this->insfigliodx(tmp);
}
else
{
nodo tmp = this->figliosx(node);
node->setfigliosx(NULL);
this->cancsottoalbero(node);
if(node == this->figliosx(this->padre(node)))
this->insfigliosx(tmp);
else
this->insfigliodx(tmp);
}
}
}
}
testbstreep.cpp
codice:
#include "bstreep.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
int main()
{
bstreep<int> T;
cout << "bstreevuoto() = " << T.binalberovuoto() << "\n\n";
int value = 0;
int key = 0;
while(value != -1)
{
cin >> value;
cin >> key;
cout << "\n";
alberobinp<int>::nodo n = new nodoalberop<int>;
n->setetichetta(value);
n->setchiave(key);
T.inserisci(n);
cout << T.binalberovuoto() << "\n";
cout << T.sxvuoto(T.binradice()) << "\n";
cout << T.dxvuoto(T.binradice()) << "\n\n";
}
cout << "min = " << T.min() << "\n\n";
system("pause");
return 0;
}
le istruzioni che non vanno bene sono quelle in rosso.
facendo il debugging, subito dopo l'esecuzione del blocco "if"
ho notato che il cursore va sulla parentesi di fine del blocco else che si trova nel ciclo while (parentesi rossa), quando nell'inserimento della radice il ciclo while non deve essere incontrato. perchè?
Rispondi quotando
