Newsgroup: it.comp.lang.c++
Titolo: Alberi Binari

Salve,
ho la necessità di creare una classe  template che implementi un albero
binario che operi su dati definiti esternamente in una struttura:
La classe dovrà essere quanto più astratta possibile in quanto dovrà essere
compilata in una dll.
La struct nodo (vedi esempio) sarà utilizzata all'interno del programma
dunque esternamente alla dll.
Es.
        struct nodo {
                string Nome;
                string Cognome;
        }
        template <class TreeType> class tree {
                                 TreeType a;              // Dubbio?
                                 TreeType *left,*right,*parent;
        public:
                 tree()         {left=right=parent=NULL;}
                 ......
};
Arrivato a questo punto non riesco a continuare...
Qualcuno può aiutarmi?

 La struct nodo (vedi esempio) sarà utilizzata all'interno del programma
Idem, la struct nodo (ovvero quella che io chiamo Tree) e' nella dll (credo)
mentre il tipo sara' nel programma.  Il tipo puo' essere int, string,
vector..... Persona etc....
Ora non voglio nemmeno pensare a tutta la storia delle DLL, questo non mi
interessa e non interessa al NG.... quindi su questa parte NON commentero'
anche se forse sarebbe da rivedere.....
Ora se hai voglia di chiedere altri aiuti specifici sull'albero/nodo e sua
implementazione, fai pure!
Tommy

 anche se forse sarebbe da rivedere.....
Anzi, altrimenti ti fai del male....
Chiedo scusa per la seguente spiegazione puerile di come funzionano i
template.... spero possa aiutare tuttavia...
I template non funzionano at run-time, ma at compile-time.
Non puoi compilare una dll (con i templates) che non sa con quali tipi di
dato verranno usati !
Sai come funzionano i templates?
template <class T>
struct Tree{
    T val;
    Tree *left;
    Tree *right;
};
se dichiaro:
Tree<int> *pa=0;
e
Tree<double> *pb=0;
il compilatore usera' il "template" (stampino se ti risulta piu' facile (non
e' la traduzione)) per creare le due strutture:
struct __int_Tree{
    int val;
    __int_Tree *left;
    __int_Tree *right;
};
struct __double_Tree{
    double val;
    __double_Tree *left;
    __double_Tree *right;
};
* i nomi __double_Tree e  __int_Tree  li ho inventati io... ogni compilatore
decide il suo site per il name mangling o name decoration.
la chiamata:
Tree<int> *pa=0;
verra convertita in:
__int_Tree *pa=0;
etc....
In pratica il template e' uno stampino che viene utilizzato per produrre
tutte le versioni richeste, dove le versioni richieste sono tutte quelle che
vengono usate. Il codice viene "duplicato" (produco copie dallo stampino)
quando compilo.
In pratica la tua DLL, una votla compilata non puo' piu' sfruttare in nessun
modo i templates!!!
Forse devi cercare una soluzione alternativa...
Spero di essere stato chiaro. A volte non e' semplice.... Ci ho provato.
Tommy

 una struttura:
Implementare un buon albero binario non e' proprio semplicissimo. La
Libreria Standard del C++ pero' ti mette a disposizione contenitori come
set e map che molto spesso sono implementati con alberi red-black (sono
alberi binari "abbastanza" bilanciati).
Se t'interessa andare a fondo su questo argomento ti suggerisco l'ottimo
Cormen, Leiserson, Rivest "Introduction to Algorithms" che esiste anche
in italiano edito dalla Jackson. Nella parte finale del primo volume
trovi lo pseudocodice che ti serve.
Ciao
Gian Michele

 Tommy
Grazie Tommy,
ho modificato la classe con i tuoi consigli ti passo il codice:
#include <iostream>
#include <string>
using namespace std;
struct Persona{
 string Nome,Cognome;
};
template <class T> class Tree{
 T *persona;
 Tree<T> *left,*right,*parent;
public:
 Tree() {left=right=parent=NULL;} //costruttore
 void addNodo(Tree<T> *p, T *dati); //aggiunge nodo all'albero
};
template <class T> void Tree<T>::addNodo(Tree<T> *p, T *dati)
{
        //.....Come faccio?
}
int main()
{
 Tree<Persona> *a;
 Persona *dati;
 a=new Tree<Persona>; //alloca spazio per il nodo
 dati=new Persona;  //alloca spazio per struttura Persona
 dati->Cognome="Pippo";
 dati->Nome="Pluto";
 return 0;
}
Il compilatore non da errori...
Vorrei ora creare un metodo della classe Tree per inserire i dati
nell'albero.
    Premetto che le caratteristiche degli alberi binari le conosco.
    Mi servirebbe una key per stabilire se il nodo da inserire deve essere
il figlio di destra o di sinistra del padre. Da come ho intuito la key non
deve far parte della struct Persona o mi sbaglio?
Mi potresti dare un consiglio.
Grazie Tommy.

 deve far parte della struct Persona o mi sbaglio?
Non capisco la domanda scusa, ma forse ti ho gia' risposto.
Spero di esserti stato di aiuto.
Tommy

 questo operatore, il compilatore dara' un errore (se lo usi, ovvio!).
Grazie per il consiglio.Creo un operator!
Ti faccio sapere.
Scusami alcuni banali errori ma è da poco che programmo in c++ con classi e
strutture dati.

 Grazie per il consiglio.Creo un operator!
Con un approccio leggermente più generico (quello adottato anche dalle
classi della libreria standard) puoi evitare di imporre la presenza di
operator< come prerequisito di T.
Aggiungi un ulteriore parametro template che rappresenti una classe
funzionale (classe che implementa operator()), con default std::less<T>:
 template< class T, /* ... , */ class CompareT = std::less<T> >
 
Quindi, anziché invocare esplicitamente operator<, userai un'instanza di
CompareT per effettuare il confronto. Cioè, se l'instanza si chiama
'comp', e 'v1' e 'v2' sono due instanze di T, userai:
           comp( v1, v2 )
 
Poiché std::less<T> usa automaticamente operator< di T, se T ne è
provvisto lascerai il valore di default di CompareT. Se invece T ne è
privo, oppure vuoi imporre un ordinamento diverso da quello previsto, ti
basta definire una classe funzionale appropriata.
Max