C++ albero binario

[pietrol83]

ciao a tutti ho creato la struttura albero binario con vettore, puntatore e cursore; inoltre ho creato una classe base con dei metodi che funzionano con tutti e tre i tipi di realizzazione. in pratica, quando faccio il test con l'albero con cursore (penso dia lo stesso problema anche con le altre realizzazioni) e arrivo al metodo visitaampiezza(), va in crash l'esecuzione. posto i codici.

codap.h

#ifndef codap_h
#define codap_h

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

using namespace std;

template<class tipoelem>
class codap
{
   public:
      codap();
      
      void creacoda();
      bool codavuota();
      tipoelem leggicoda();
      void incoda(tipoelem);
      void fuoricoda();
   private:
      nodop<tipoelem> *testa;
      nodop<tipoelem> *coda;
};

#endif

template<class tipoelem>
codap<tipoelem>::codap()
{
   this->creacoda();
}

template<class tipoelem>
void codap<tipoelem>::creacoda()
{
   testa = NULL;
   coda = NULL;
}

template<class tipoelem>
bool codap<tipoelem>::codavuota()
{
   return((testa == NULL) && (coda == NULL));
}

template<class tipoelem>
tipoelem codap<tipoelem>::leggicoda()
{
   return(testa->getelem());
}

template<class tipoelem>
void codap<tipoelem>::incoda(tipoelem elem)
{
   nodop<tipoelem> *tmp = new nodop<tipoelem>;
   
   if(this->codavuota())
   {
      tmp->setprec(NULL);
      tmp->setsuc(NULL);
      testa = tmp;
      coda = tmp;
   }
   else
   {
      coda->setprec(tmp);
      tmp->setprec(NULL);
      tmp->setsuc(coda);
   }
   tmp->setelem(elem);
   coda = tmp;
}

template<class tipoelem>
void codap<tipoelem>::fuoricoda()
{
   if(!this->codavuota())
   {
      nodop<tipoelem> *tmp = new nodop<tipoelem>;
      tmp = testa;
      testa = testa->getprec();
      testa->setsuc(NULL);
   }
   else
      cerr << "la coda e' vuota.\n\n";
}

alberobin.h

#ifndef alberobin_h
#define alberobin_h

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

using namespace std;

template<class nodo, class tipoelem>
class alberobin
{
   public:
      virtual void creabinalbero() = 0;
      virtual bool binalberovuoto() = 0;
      virtual nodo binradice() = 0;
      virtual nodo binpadre(nodo) = 0;
      virtual nodo figliosx(nodo) = 0;
      virtual nodo figliodx(nodo) = 0;
      virtual bool sxvuoto(nodo) = 0;
      virtual bool dxvuoto(nodo) = 0;
      virtual tipoelem legginodo(nodo) = 0;
      virtual void scrivinodo(nodo, tipoelem) = 0;
      virtual void insbinradice(nodo) = 0;
      virtual void insfigliosx(nodo) = 0;
      virtual void insfigliodx(nodo) = 0;
      virtual void cancsottoalbero(nodo) = 0;
      
      void test();
      void visitaampiezza();
      void previsita(nodo);
      void postvisita(nodo);
      void simmvisita(nodo);
};

#endif

template<class nodo, class tipoelem>
void alberobin<nodo, tipoelem>::test()
{
   cout << "                          ***test metodo CREABINALBERO***\n\n";
   cout << "il metodo CREABINALBERO crea un albero binario vuoto. per provare\n";
   cout << "la correttezza del metodo basta invocar eil metodo BINALBEROVUOTO\n";
   cout << "il quale deve dare come risulatato il valore booleano vero (1).\n\n";
   cout << "   binalberovuoto() = " << this->binalberovuoto() << "\n\n";
   system("pause");
   system("cls");
   
   cout << "                          ***test del metodo BINALBEROVUOTO***\n\n";
   cout << "il metodo BINALBEROVUOTO testa se l'albero binario ho o meno nodi\n";
   cout << "(compresa la radice) fornendo un valore booleano a seconda della\n";
   cout << "presenza dei nodi.\n\n";
   cout << "   test con albero privo di nodi:\n";
   cout << "      binalberovuoto() = " << this->binalberovuoto() << "\n\n";
   cout << "   test con albero con almeno un nodo:\n";
   cout << "      inserimento della radice con un valore:\n";
   cout << "      radice = ";
   nodo node;
   tipoelem a;
   cin >> a;
   this->insbinradice(node);
   this->scrivinodo(this->binradice(), a);
   cout << "      binalberovuoto() = " << this->binalberovuoto() << "\n\n";
   system("pause");
   system("cls");
   
   cout << "                         ***test del metodo BINRADICE***\n\n";
   cout << "il metodo BINRADICE restituisce il riferimento alla radice\n";
   cout << "dell'albero binario.\n\n";
   cout << "   binradice() = " << this->binradice() << "\n\n";
   system("pause");
   system("cls");
   
   cout << "                         ***test del metodo BINPADRE***\n\n";
   cout << "il metodo BINPADRE restituisce il riferimento al nodo padre\n";
   cout << "del nodo fornito come argomento.\n\n";
   cout << "poiché l'albero è costituito dalla sola radice, la quale non\n";
   cout << "ha padre, bisogna inserire un ulteriore nodo come figlio sx o\n";
   cout << "dx della radice.\n\n";
   nodo temp;
   this->insfigliosx(this->binradice());
   cout << "   binpadre(figliosx(radice())) = " << this->binpadre(this->figliosx(this->binradice())) << "\n\n";
   system("pause");
   system("cls");
   
   cout << "                         ***test del metodo FIGLIOSX***\n\n";
   cout << "il metodo FIGLIOSX fornisce il nodo che è figlio sinistro del\n";
   cout << "nodo passato come argomento.\n\n";
   cout << "   figliosx(radice()) = " << this->figliosx(this->binradice()) << "\n\n";
   system("pause");
   system("cls");
   
   cout << "                         ***test del metodo FIGLIODX***\n\n";
   cout << "analogo al metodo FIGLIODX\n\n";
   nodo tmp2;
   this->insfigliodx(this->binradice());
   cout << "   figliodx(radice()) = " << this->figliodx(this->binradice()) << "\n\n";
   system("pause");
   system("cls");
   
   cout << "                        ***test del metodo SXVUOTO***\n\n";
   cout << "il metodo SXVUOTO fornisce un valore booleano a seconda che il\n";
   cout << "nodo passato come argomento ha o meno figlio sinistro.\n\n";
   cout << "   test con esito positivo:\n";
   cout << "      sxvuoto(figliosx(radice())) = " << this->sxvuoto(this->figliosx(this->binradice())) << "\n\n";
   cout << "   test con esito negativo:\n";
   cout << "      sxvuoto(radice()) = " << this->sxvuoto(this->binradice()) << "\n\n";
   
   system("pause");
   system("cls");
   
   cout << "                        ***test del metodo DXVUOTO***\n\n";
   cout << "analogo al metodo SXVUOTO.\n\n";
   cout << "   test con esito positivo:\n";
   cout << "      dxvuoto(figliosx(radice())) = " << this->dxvuoto(this->figliosx(this->binradice())) << "\n\n";
   cout << "   test con esito negativo:\n";
   cout << "      dxvuoto(radice()) = " << this->dxvuoto(this->binradice()) << "\n\n";
   system("pause");
   system("cls");
   
   cout << "                       ***test dei metodi SCRIVINODO e LEGGINODO***\n\n";
   cout << "il metodo SCRIVINODO scrive un valore nell'etichetta del nodo\n";
   cout << "passato come argomento. il metodo LEGGINODO fornisce tale valore.\n\n";
   cout << "   scrittura nella radice di un valore: ";
   cin >> a;
   this->scrivinodo(this->binradice(), a);
   this->scrivinodo(this->figliosx(this->binradice()), 2);
   this->scrivinodo(this->figliodx(this->binradice()), 3);
   cout << "   lettura del valore della radice:\n";
   cout << "      legginodo(radice()) = " << this->legginodo(this->binradice()) << "\n\n";
   system("pause");
   system("cls");
   
   cout << "         ***metodi PREVISITA, POSTVISITA, SIMMETRICA e AMPIEZZA***\n\n";
   cout << "   previsita() = ";
   this->previsita(this->binradice());
   cout << "\n\n";
   cout << "   postvisita() = ";
   this->postvisita(this->binradice());
   cout << "\n\n   simmetrica() = ";
   this->simmvisita(this->binradice());
   cout << "\n\n   ampiezza() = ";
   this->visitaampiezza();
   cout << "\n\n";
   system("pause");
   system("cls");
   
   cout << "i metodi INSBINRADICE, INSFIGLIOSX e INSFIGLIODX sarebbero gia'\n";
   cout << "testati in quanto sono stati utilizzati per testare i metodi\n";
   cout << "BINRADICE, FIGLIOSX e FIGLIODX.\n\n";
   system("pause");
   system("cls");
   
   cout << "                      test del metodo CANCSOTTOALBERO***\n\n";
   cout << "il metodo CANCSOTTOALBERO cancella tutti i nodi dell'albero a partire\n";
   cout << "dal nodo passato come argomento. nel test viene cancellato tutto l'albero\n";
   cout << "e viene invocato il metodo BINALBEROVUOTO per verificare se il mtodo\n";
   cout << "ha funzionato correttamente.\n\n";
   cout << "   cancellazione dell'albero:\n";
   this->cancsottoalbero(this->binradice());
   cout << "   verifica: bianlberovuoto() = " << this->binalberovuoto() << "\n\n";
}

template<class nodo, class tipoelem>
void alberobin<nodo, tipoelem>::visitaampiezza()
{
   codap<nodo> Q;
   tipoelem a;
   nodo u = this->binradice();
   Q.incoda(u);
   while(!Q.codavuota())
   {
      u = Q.leggicoda();
      a = this->legginodo(u);
      cout << a << "  ";
      Q.fuoricoda();
      system("pause");
      if(!this->sxvuoto(u))
         Q.incoda(this->figliosx(u));
      if(!this->dxvuoto(u))
         Q.incoda(this->figliodx(u));
   }
}

template<class nodo, class tipoelem>
void alberobin<nodo, tipoelem>::previsita(nodo node)
{
   cout << this->legginodo(node) << "  ";
   if(!this->sxvuoto(node))
      this->previsita(this->figliosx(node));
   if(!this->dxvuoto(node))
      this->previsita(this->figliodx(node));
}

template<class nodo, class tipoelem>
void alberobin<nodo, tipoelem>::postvisita(nodo node)
{
   if(!this->sxvuoto(node))
      this->postvisita(this->figliosx(node));
   if(!this->dxvuoto(node))
      this->postvisita(this->figliodx(node));
   cout << this->legginodo(node) << "  ";
}

template<class nodo, class tipoelem>
void alberobin<nodo, tipoelem>::simmvisita(nodo node)
{
   if(!this->sxvuoto(node))
      this->simmvisita(this->figliosx(node));
   cout << this->legginodo(node) << "  ";
   if(!this->dxvuoto(node))
      this->simmvisita(this->figliodx(node));
}

CONTINUA----->

[pietrol83]

alberobinc.h

#ifndef alberobinc_h
#define alberobinc_h

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

using namespace std;

template<class tipoelem>
class alberobinc : public alberobin<int, tipoelem>
{
    public:
       typedef struct Nodo
       {
          tipoelem etichetta;
          int livello;
          int padre;
          int figliosx;
          int figliodx;
       } nod;
       typedef int nodo;
       
       alberobinc(int);
       
       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);
    private:
       nod *spazio;
       int nodiliberi;
       int nodolibero;
       nodo radice;
       int numnodi;
       int dimspazio;
};

#endif

template<class tipoelem>
alberobinc<tipoelem>::alberobinc(int dim)
{
   dimspazio = dim;
   this->creabinalbero();
}

template<class tipoelem>
void alberobinc<tipoelem>::creabinalbero()
{
   spazio = new struct Nodo[dimspazio];
   spazio[0].padre = -1;
   spazio[0].figliosx = -1;
   spazio[0].figliodx = 1;
   for(int i = 1; i < dimspazio - 1; i++)
   {
      spazio[i].padre = -1;
      spazio[i].figliosx = (i - 1) % dimspazio;
      spazio[i].figliodx = (i + 1) % dimspazio;
   }
   spazio[dimspazio - 1].padre = -1;
   spazio[dimspazio - 1].figliosx = dimspazio - 2;
   spazio[dimspazio - 1].figliodx = -1;
   nodiliberi = dimspazio;
   nodolibero = 0;
   radice = nodolibero;
   numnodi = 0;
}

template<class tipoelem>
bool alberobinc<tipoelem>::binalberovuoto()
{
   return(numnodi == 0);
}

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

template<class tipoelem>
typename alberobinc<tipoelem>::nodo alberobinc<tipoelem>::binpadre(typename alberobinc<tipoelem>::nodo node)
{
   assert(node != this->binradice());
   return(spazio[node].padre);
}

template<class tipoelem>
typename alberobinc<tipoelem>::nodo alberobinc<tipoelem>::figliosx(typename alberobinc<tipoelem>::nodo node)
{
   return(spazio[node].figliosx);
}

template<class tipoelem>
typename alberobinc<tipoelem>::nodo alberobinc<tipoelem>::figliodx(typename alberobinc<tipoelem>::nodo node)
{
   return(spazio[node].figliodx);
}

template<class tipoelem>
bool alberobinc<tipoelem>::sxvuoto(typename alberobinc<tipoelem>::nodo node)
{
   return(spazio[node].figliosx == -1);
}

template<class tipoelem>
bool alberobinc<tipoelem>::dxvuoto(typename alberobinc<tipoelem>::nodo node)
{
   return(spazio[node].figliodx == -1);
}

template<class tipoelem>
tipoelem alberobinc<tipoelem>::legginodo(typename alberobinc<tipoelem>::nodo node)
{
   return(spazio[node].etichetta);
}

template<class tipoelem>
void alberobinc<tipoelem>::scrivinodo(typename alberobinc<tipoelem>::nodo node, tipoelem elem)
{
   spazio[node].etichetta = elem;
}

template<class tipoelem>
void alberobinc<tipoelem>::insbinradice(typename alberobinc<tipoelem>::nodo node)
{
   assert(this->binalberovuoto());
   nodo temp = nodolibero;
   nodolibero = spazio[nodolibero].figliodx;
   spazio[nodolibero].figliosx = -1;
   spazio[temp].figliosx = -1;
   spazio[temp].figliodx = -1;
   numnodi++;
   nodiliberi--;
   radice = temp;
}

template<class tipoelem>
void alberobinc<tipoelem>::insfigliosx(typename alberobinc<tipoelem>::nodo node)
{
   assert(!this->binalberovuoto() && this->sxvuoto(node));
   nodo temp = nodolibero;
   nodolibero = spazio[nodolibero].figliodx;
   spazio[node].figliosx = temp;
   spazio[temp].padre = node;
   spazio[temp].figliosx = -1;
   spazio[temp].figliodx = -1;
   nodiliberi--;
   numnodi++;
}

template<class tipoelem>
void alberobinc<tipoelem>::insfigliodx(typename alberobinc<tipoelem>::nodo node)
{
   assert(!this->binalberovuoto() && this->dxvuoto(node));
   nodo temp = nodolibero;
   nodolibero = spazio[nodolibero].figliodx;
   spazio[node].figliodx = temp;
   spazio[temp].padre = node;
   spazio[temp].figliosx = -1;
   spazio[temp].figliodx = -1;
   nodiliberi--;
   numnodi++;
}

template<class tipoelem>
void alberobinc<tipoelem>::cancsottoalbero(typename alberobinc<tipoelem>::nodo node)
{
   if(!this->sxvuoto(node))
      this->cancsottoalbero(this->figliosx(node));
   if(!this->dxvuoto(node))
      this->cancsottoalbero(this->figliodx(node));
   if(node != this->binradice())
   {
      if(node == this->figliosx(spazio[node].padre))
         spazio[spazio[node].padre].figliosx = -1;
      else
         spazio[spazio[node].padre].figliodx = -1;
   }
   spazio[node].figliosx = -1;
   spazio[node].figliodx = nodolibero;
   nodolibero = node;
   nodiliberi++;
   numnodi--;
}

testalberobin.cpp

#include "alberobin.h"
#include "alberobinv.h"
#include "alberobinp.h"
#include "alberobinc.h"
#include<iostream>
#include<stdlib.h>

using namespace std;

int main()
{
   alberobinv<int> T(5);
   alberobinp<int> T2;
   alberobinc<int> T3(20);
   
   
   /*cout << "          ***test albero binario con vettore***\n\n";
   T.test();
   system("pause");
   system("cls");
   
   cout << "          ***test albero binario con puntatore***\n\n";
   T2.test();
   system("pause");
   system("cls");*/
   
   cout << "          ***test albero binario con cursore***\n\n";
   T3.test();
   system("pause");
   system("cls");
   
   system("pause");
   return 0;
}

in pratica ho notato che l'esecuzione va in crash quando si arriva ad eseguire l'istruzione "delete tmp;" del metodo fuoricoda nella struttura coda. questo metodo viene chiamato in visitaampiezza nella struttura base alberobin.

perchè va in crash??? mi sembra fatto bene il metodo.

[ramy89]

Non capisco perché in questo metodo:

template<class tipoelem>
void codap<tipoelem>::fuoricoda()
{
   if(!this->codavuota())
   {
      nodop<tipoelem> *tmp = new nodop<tipoelem>;
      tmp = testa;
      testa = testa->getprec();
      testa->setsuc(NULL);
   }
   else
      cerr << "la coda e' vuota.\n\n";
}

Allochi spazio per un nuovo nodo ma poi fai l' assegnamento tmp=testa.Guarda che così facendo viene perso il riferimento al nuovo nodo allocato.
E questi metodi setprec e getsuc dove stanno?

[pietrol83]

in precedenza non avevo allocato la memoria ma avevo dichiarato tem e l'avevo inizializzato a testa ma mi crashava comunque. poi ho provato ad allocare la memoria ma il risultato non cambia.

i metodi getprec ecc ecc sono nella classe nodop.h che non ho postato. dato che funzionano correttamente ho pensato non fosse necessario postare anche quella classe.
posto anche la classe nodop.h

nodop.h

#ifndef nodop_h
#define nodop_h

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

using namespace std;

template<class tipoelem>
class nodop
{
   public:
      nodop();
      
      void setprec(nodop *);
      void setelem(tipoelem);
      void setsuc(nodop *);
      
      nodop *getprec();
      tipoelem getelem();
      nodop *getsuc();
   private:
      nodop *precedente;
      tipoelem elemento;
      nodop *successivo;
};
#endif

template<class tipoelem>
nodop<tipoelem>::nodop()
{
   precedente = NULL;
   elemento = 0;
   successivo = NULL;
}

template<class tipoelem>
void nodop<tipoelem>::setprec(nodop *prec)
{
   precedente = prec;
}

template<class tipoelem>
void nodop<tipoelem>::setelem(tipoelem elem)
{
   elemento = elem;
}

template<class tipoelem>
void nodop<tipoelem>::setsuc(nodop *suc)
{
    successivo = suc;
}

template<class tipoelem>
nodop<tipoelem> *nodop<tipoelem>::getprec()
{
   return(precedente);
}

template<class tipoelem>
tipoelem nodop<tipoelem>::getelem()
{
   return(elemento);
}

template<class tipoelem>
nodop<tipoelem> *nodop<tipoelem>::getsuc()
{
   return(successivo);
}

[ramy89]

in precedenza non avevo allocato la memoria ma avevo dichiarato temp e l'avevo inizializzato a testa ma mi crashava comunque. poi ho provato ad allocare la memoria ma il risultato non cambia.

Ma stai provando a caso? :dubbioso
Allocare memoria per cosa? Qual'è lo scopo di quella allocazione?

template<class tipoelem>
void codap<tipoelem>::fuoricoda()
{
   if(!this->codavuota())
   {
      nodop<tipoelem> *tmp=testa;
      testa = testa->getprec();
      testa->setsuc(NULL);
   }
   else
      cerr << "la coda e' vuota.\n\n";
}

Ma rimane un problema: non stai deallocando i nodi che vengono estratti.
Però non capisco in che riga il programma va in crash.
Dici che va in crash dopo l' istruzione "delete temp", ma in tutto il codice che hai postato non esegui dichiari mai "delete tmp".
Posta anche il codice del main.

[pietrol83]

scusami ho fatto delle modifiche, sperando di risolvere il problema. il metodo era questo:

template<class tipoelem>
void codap<tipoelem>::fuoricoda()
{
if(!this->codavuota())
{
nodop<tipoelem> *tmp=testa;
testa = testa->getprec();
testa->setsuc(NULL);
delete tmp;
}
else
cerr << "la coda e' vuota.\n\n";
}

e va in crash all'istruzione delete tmp;

[ramy89]

edit

[pietrol83]

non ti seguo!!!

[ramy89]

Posta anche il metodo codavuota.
Posta tutto, anche il main.

[pietrol83]

il metodo codavuota sta nel codice codap.h all'inizio della discussione.
il main sta in testalberobin, nella discussione. direi che ci sono tutti i codici necessari.