Salve a tutti sono nuovo di questo forum e nell'utilizzare C++
Devo scrivere una funzione che dato un albero nario deve calcolarmi il numero di foglie presenti.
Ecco il codice della funzione
codice:
template<class _value_type> int util_n_tree<_value_type>::n_leaf(const Albero<_value_type> &T) {
if (T.alberoVuoto())
return 0;
if (T.primofiglio(T.radice()) == NULL) {
return 1 + n_leaf(T.succFratello());
} else {
return (n_leaf(T.primoFiglio(T.radice()))
+ n_leaf(T.succFratello(T.radice)));
}
}
Questo il codice della struttura
codice:
#ifndef _ALBERON_H_#define _ALBERON_H_
#include "Cella.h"
#include <cassert>
#include <iostream>
using namespace std;
template <class T> class Albero {
public:
// tipi
typedef T tipoelem;
typedef Cella<T>* Nodo;
// costruttori e distruttori
Albero();
~Albero();
// operatori
void creaAlbero();
bool alberoVuoto();
void insRadice(Nodo);
Nodo radice();
Nodo padre(Nodo);
bool foglia(Nodo);
Nodo primoFiglio(Nodo);
bool ultimoFratello(Nodo);
Nodo succFratello(Nodo);
void insPrimoSottoalbero(Nodo,Albero<T>&);
void insSottoalbero(Nodo,Albero<T>&);
void cancSottoalbero(Nodo); //
// operazioni di lettura / scrittura sui nodi
void scriviNodo(Nodo,tipoelem);
tipoelem leggiNodo(Nodo);
// servizio
void stampa(Nodo,int); // stampa il sottoalbero di radice Nodo posto a livello int
private:
bool appartiene(Nodo);
Nodo root; // un albero � identificato dalla sua radice
};
template <class T> Albero<T>::Albero()
{creaAlbero();}
template <class T> Albero<T>::~Albero()
{}
template <class T> void Albero<T>::creaAlbero()
{
root=NULL;
}
template <class T> bool Albero<T>::alberoVuoto()
{
return (root==NULL);
}
template <class T> void Albero<T>::insRadice(Nodo n)
{
assert (alberoVuoto());
root=n;
root->setPRIMOFIGLIO(NULL); // non ha figli
root->setPROXFRATELLO(NULL); // non ha fratelli
root->setPADRE(NULL); // non ha genitore
}
template <class T> Cella<T>* Albero<T>::radice()
{
assert (!alberoVuoto());
return (root);
}
template <class T> Cella<T>* Albero<T>::padre(Nodo n)
{
assert (n!=radice());
assert (appartiene(n));
return (n->getPADRE());
}
template <class T> bool Albero<T>::appartiene(Nodo n)
{
return (true);
}
template <class T> bool Albero<T>::foglia(Nodo n)
{
assert(appartiene(n));
return (n->getPRIMOFIGLIO()==NULL); // NODO FOGLIA SE NON HA FIGLI
}
template <class T> Cella<T>* Albero<T>::primoFiglio(Nodo n)
{
assert (appartiene(n));
assert (n->getPRIMOFIGLIO()!=NULL);
return (n->getPRIMOFIGLIO());
}
template <class T> bool Albero<T>::ultimoFratello(Nodo n)
{
assert (appartiene(n));
return (n->getPROXFRATELLO()==NULL); // ULTIMO FRATELLO SE NON HA FRATELLI
}
template <class T> Cella<T>* Albero<T>::succFratello(Nodo n)
{
assert (appartiene(n));
assert (!ultimoFratello(n));
return (n->getPROXFRATELLO());
}
template <class T> void Albero<T>::insPrimoSottoalbero(Nodo n, Albero<T> &a)
{
assert (!a.alberoVuoto()); // a non � vuoto
assert (appartiene(n)); // n � nell'albero corrente
a.radice()->setPROXFRATELLO(n->getPRIMOFIGLIO()); // quello che era il primo figlio di n diventa fratello della radice di a
a.radice()->setPADRE(n); // n diventa padre della radice di a
n->setPRIMOFIGLIO(a.radice()); // la radice di a diventa primo figlio di n
}
template <class T> void Albero<T>::insSottoalbero(Nodo n, Albero<T> &a)
{
assert (!a.alberoVuoto()); // a non � vuoto
assert (appartiene(n)); // n � nell'albero corrente
assert (radice()!=n); // n � nell'albero corrente
a.radice()->setPROXFRATELLO(n->getPROXFRATELLO()); // quello che era il fratello di n diventa fratello della radice di a
// ERRATO a.radice()->setPADRE(radice()); // n diventa padre della radice di a
a.radice()->setPADRE(n->getPADRE()); // il padre di n diventa padre della radice di a
n->setPROXFRATELLO(a.radice()); // la radice di a diventa primo figlio di n
}
template <class T> void Albero<T>::scriviNodo(Nodo n, tipoelem e)
{
assert (appartiene(n)); // n � nell'albero corrente
n->setElemento(e);
}
template <class T> T Albero<T>::leggiNodo(Nodo n)
{
assert (appartiene(n)); // n � nell'albero corrente
return (n->getElemento());
}
template <class T> void Albero<T>::stampa(Nodo n, int livello)
{
assert(appartiene(n));
assert(livello>=0);
if (alberoVuoto())
{
cout << "albero vuoto!" << endl;
return;
}
const int Nspaces=4;
int spaces=livello*Nspaces;
// stampo il nodo
for (int i=1;i<spaces;i++)
cout << " ";
cout << leggiNodo(n) << endl; // stampo il nodo
if (!foglia(n))
{
livello++; // ed i suoi eventuali figli: passo al livello successivo
stampa(primoFiglio(n),livello);
Nodo iter=primoFiglio(n);
bool ancora_fratelli = !ultimoFratello(iter);
while (ancora_fratelli)
{
iter=succFratello(iter);
stampa(iter,livello);
ancora_fratelli=!ultimoFratello(iter);
}
}
}
template <class T> void Albero<T>::cancSottoalbero(Nodo n)
{
assert (appartiene(n)); // n � nell'albero corrente
cout << "entro nella procedura per eliminare nodo: " << n->getElemento() << endl;
// spezzo i legami tra n, il padre ed i fratelli
if (radice()==n)
{
cout << "cancellazione dalla radice!" << endl;
delete root;
}
else
{
if (n==primoFiglio(padre(n))) // n � il primo figlio
{
cout << "cancello un primogenito!" << endl;
if (ultimoFratello(n))
padre(n)->setPRIMOFIGLIO(NULL);
else
padre(n)->setPRIMOFIGLIO(succFratello(n));// allora ha un fratello che diventa il primo figlio
}
else
{
// sono nel ramo else dunque n non � primo figlio
Nodo prec=primoFiglio(padre(n));
cout << "prec: " << leggiNodo(prec) << endl;
Nodo current=succFratello(prec);
cout << "current: " << leggiNodo(current) << endl;
while (current!=n)
{
prec=current;
current=succFratello(current);
}
cout << "trovato!" << endl;
// current=n
if (ultimoFratello(n))
prec->setPROXFRATELLO(NULL);
else
prec->setPROXFRATELLO(succFratello(n));
}
}
delete n;
}
#endif /* _ALBERON_H_ */
Ma quando compilo il codice ho i seguenti errori
codice:
make all Building file: ../src/main.cpp
Invoking: GCC C++ Compiler
g++ -O0 -g3 -Wall -c -fmessage-length=0 -MMD -MP -MF"src/main.d" -MT"src/main.o" -o "src/main.o" "../src/main.cpp"
../src/main.cpp: In function ‘int main(int, char**)’:
../src/main.cpp:103:9: warning: unused variable ‘nleaf’ [-Wunused-variable]
int nleaf = ut.n_leaf(tree);
^
In file included from ../src/main.cpp:6:0:
../src/util_n_tree.h: In instantiation of ‘int util_n_tree<_value_type>::n_leaf(const Albero<_value_type>&) [with _value_type = int]’:
../src/main.cpp:103:31: required from here
../src/util_n_tree.h:62:2: error: passing ‘const Albero<int>’ as ‘this’ argument discards qualifiers [-fpermissive]
if (T.alberoVuoto())
^
In file included from ../src/main.cpp:3:0:
../src/AlberoN.h:53:25: note: in call to ‘bool Albero<T>::alberoVuoto() [with T = int]’
template <class T> bool Albero<T>::alberoVuoto()
^
In file included from ../src/main.cpp:6:0:
../src/util_n_tree.h:64:32: error: ‘const class Albero<int>’ has no member named ‘primofiglio’
if (T.primofiglio(T.radice()) == NULL) {
^
../src/util_n_tree.h:64:32: error: passing ‘const Albero<int>’ as ‘this’ argument discards qualifiers [-fpermissive]
In file included from ../src/main.cpp:3:0:
../src/AlberoN.h:67:30: note: in call to ‘Cella<T>* Albero<T>::radice() [with T = int]’
template <class T> Cella<T>* Albero<T>::radice()
^
In file included from ../src/main.cpp:6:0:
../src/util_n_tree.h:65:20: error: no matching function for call to ‘Albero<int>::succFratello() const’
return 1 + n_leaf(T.succFratello());
^
In file included from ../src/main.cpp:3:0:
../src/AlberoN.h:107:30: note: candidate: Cella<T>* Albero<T>::succFratello(Albero<T>::Nodo) [with T = int; Albero<T>::Nodo = Cella<int>*]
template <class T> Cella<T>* Albero<T>::succFratello(Nodo n)
^
../src/AlberoN.h:107:30: note: candidate expects 1 argument, 0 provided
In file included from ../src/main.cpp:6:0:
../src/util_n_tree.h:67:17: error: passing ‘const Albero<int>’ as ‘this’ argument discards qualifiers [-fpermissive]
return (n_leaf(T.primoFiglio(T.radice()))
^
In file included from ../src/main.cpp:3:0:
../src/AlberoN.h:67:30: note: in call to ‘Cella<T>* Albero<T>::radice() [with T = int]’
template <class T> Cella<T>* Albero<T>::radice()
^
In file included from ../src/main.cpp:6:0:
../src/util_n_tree.h:67:17: error: passing ‘const Albero<int>’ as ‘this’ argument discards qualifiers [-fpermissive]
return (n_leaf(T.primoFiglio(T.radice()))
^
In file included from ../src/main.cpp:3:0:
../src/AlberoN.h:94:30: note: in call to ‘Cella<T>* Albero<T>::primoFiglio(Albero<T>::Nodo) [with T = int; Albero<T>::Nodo = Cella<int>*]’
template <class T> Cella<T>* Albero<T>::primoFiglio(Nodo n)
^
In file included from ../src/main.cpp:6:0:
../src/util_n_tree.h:67:17: error: no matching function for call to ‘util_n_tree<int>::n_leaf(Cella<int>*)’
return (n_leaf(T.primoFiglio(T.radice()))
^
../src/util_n_tree.h:59:33: note: candidate: int util_n_tree<_value_type>::n_leaf(const Albero<_value_type>&) [with _value_type = int]
template<class _value_type> int util_n_tree<_value_type>::n_leaf(
^
../src/util_n_tree.h:59:33: note: no known conversion for argument 1 from ‘Cella<int>*’ to ‘const Albero<int>&’
../src/util_n_tree.h:68:13: error: invalid use of non-static member function
+ n_leaf(T.succFratello(T.radice)));
^
src/subdir.mk:18: recipe for target 'src/main.o' failed
make: *** [src/main.o] Error 1
Grazie in anticipo per la risposta