Alberi binari C++ con templates: problema

[Mino]

Ciao a tutti. Per l'Università ho preparato un elaborato dove implemento gli alberi binari di ricerca.
Ho usato i template, per la struttura dati.

Il problema è il seguente: se scrivo tutto in un unico file .cpp nessun problema, ma se voglio dividere in più files (file.h per la definizione di classe e i prototipi, file.cpp per le definizioni delle funzioni membro, main.cpp come client) mi dà errori in compilazione.
In sostanza il codice è il seguente:

file.h

template <class Item>
class BinaryTree
{
private:
struct node
{
node*left;//Puntatore al figlio sinistro
node*right;//Puntatore al figlio destro
node*p;//Puntatore al padre
Item item;
node(Item& i) {left=NULL; right=NULL; item=i;}
};

typedef struct node* link;
link root; //Puntatore alla radice dell'albero

public:

BinaryTree();//Costruttore
linklink Get_Root();//Ritorna il puntatore alla radice

...
};

file.cpp

#include <iostream>
#include "BinaryTree.h"
//typedef struct Tree::node* link;


template<class Item> BinaryTree<Item>::BinaryTree()//Costruttore
{
root=NULL;//Albero vuoto
}

template<class Item> BinaryTree<Item>::link BinaryTree<Item>::Get_Root()//Ritorna il puntatore alla radice
{//NON FUNZIONA
return root;
}

Main.cpp

#include <iostream>
#include "BinaryTree.h"

int main (void);
main()
{
BinaryTree<int> b1;
int scelta;
int controllo=1;

std::cout<<"FONDAMENTI DI INFORMATICA II - ELABORATO - MINO MARAZZINI"<<std::endl;
std::cout<<std::endl;
std::cout<<"ALBERI BINARI DI RICERCA"<<std::endl;
std::cout<<std::endl;
do
{
std::cout<<"MENU:"<<std::endl;
std::cout<<"TASTO 1 PER INSERIRE UN ELEMENTO"<<std::endl;
std::cout<<"TASTO 2 PER CANCELLARE UN ELEMENTO"<<std::endl;
std::cout<<"TASTO 3 PER RICERCARE UN ELEMENTO"<<std::endl;
std::cout<<"TASTO 4 PER LA STAMPA ORDINATA"<<std::endl;
std::cout<<"TASTO 5 PER LA STAMPA ANTICIPATA"<<std::endl;
std::cout<<"TASTO 6 PER LA STAMPA POSTICIPATA"<<std::endl;
std::cout<<"TASTO 7 PER STAMPARE L'ELENCO DEI PREDECESSORI"<<std::endl;
std::cout<<"TASTO 8 PER STAMPARE L'ELENCO DEI SUCCESSORI"<<std::endl;
std::cout<<"TASTO 9 PER STAMPARE IL MINIMO"<<std::endl;
std::cout<<"TASTO 10 PER STAMPARE IL MASSIMO"<<std::endl;
std::cout<<std::endl;
std::cout<<"OPZIONE SCELTA => ";
std::cin>>scelta;

switch (scelta)
{
case 1://Inserimento
{
int x;
std::cout<<"DIGITARE IL NUMERO DA INSERIRE => ";
std::cin>>x;
b1.It_Ins(x);
break;
}

case 2://Cancellazione
{
int y;
std::cout<<"DIGITARE IL NUMERO DA RIMUOVERE => ";
std::cin>>y;
b1.Delete(y);
break;
}

case 3://Ricerca
{
int z;
int risultato;
std::cout<<"DIGITARE IL NUMERO DA RICERCARE => ";
std::cin>>z;
risultato=b1.Search(z);
if(risultato==1)
std::cout<<"ELEMENTO PRESENTE NELL'ALBERO";
else
std::cout<<"ELEMENTO NON PRESENTE NELL'ALBERO";
break;
}

case 4://Stampa in ordine
{
b1.Print(b1.Get_Root());
break;
}

case 5://Stampa anticipata
{
b1.Preord_Stampa(b1.Get_Root());
break;
}

case 6://Stampa posticipata
{
b1.Postord_Stampa(b1.Get_Root());
break;
}

case 7://Stampa predecessori
{
b1.Stampa_Pred(b1.Get_Root());
break;
}

case 8://Stampa successori
{
b1.Stampa_Succ(b1.Get_Root());
break;
}

case 9://Stampa il minimo
{
std::cout<<"IL MINIMO E' => "<<b1.Min();
break;
}

case 10://Stampa il massimo
{
std::cout<<"IL MASSIMO E' => "<<b1.Max();
break;
}

default:
std::cout<<"ERRORE! NESSUNA OPZIONE CORRISPONDENTE!!!"<<std::endl;
}

std::cout<<std::endl;
std::cout<<"PREMERE 1 PER UNA NUOVA OPERAZIONE, 0 PER TERMINARE => ";
std::cin>>controllo;
std::cout<<std::endl;
system("cls");

}while(controllo!=0);

return 0;

}


Ecco, il problema sono le funzioni che ritornano un link, cioè un puntatore a struct node. Quando faccio la costruzione (la compilazione va bene) del Main, mi dice "UNRESOLVED EXTERNAL SYMBOLS".
Il problema è come scrivere le definizioni delle funzioni (visto che la classe è template) nel file separato .cpp, e le funzioni che riportano uno struct node: tale struct è interna ad una classe template, e dà problemi.
Come faccio?

[anx721]

qundo linki, linki anche il file.cpp? che comandi usi per creare l'eseguibile?

[Mino]

Si, linko anche il .cpp.
Niente comandi, ho Visual Studio.
Qualche idea?

[anx721]

posta l'errore completo

[anx721]

molto probabilemnte si tratta di un errore legato alla sintassi del template che no conosco. Usando ilcompilatore gcc in fase di compilazione del file.cpp, in corrispondenza della riga iniziale della funzione getRoot dà il seguente warning:

file.cpp:12: warning: `BinaryTree<Item>::link' is implicitly a typename
file.cpp:12: warning: implicit typename is deprecated

[/\/\@®¢Ø]

Per il C++ template con argomenti differenti sono tipi differenti. Ad esempio BinaryTree<Item> e' diverso da BinaryTree<int>. Tra le altre cose, questo vuol dire che il compilatore deve generare codice diverso per ogni tipo. Visto che non lo puo' fare per tutti i tipi possibili e immaginabili, lo fa solo per quei tipi che vede essere usati. Ma quando viene compilato file.cpp, come fa a sapere che tu vuoi usare BinaryTree<Item> in main.cpp ? Non lo sa, ed infatti non ti genera il codice relativo.
La soluzione piu' semplice rimane quella di includere tutto il sorgente in file.h, cosiche' quando compili main.cpp il compilatore puo' generarti il codice opportuno. Il metodo meno intrusivo e' un bel
#include "file.cpp"
alla fine di file.h

[anx721]

a questo punto megli omettere l'implementazione dei metodi all'interno della classe se no includendo file.cpp inpiu parti si ha l'errore di definizioni multiple

[Mino]

Proverò le soluzioni che mi avete suggerito.
Colgo l'occasione per ringraziarvi di cuore, siete stati davvero gentilissimi !
Vi saprò dire (appena avrò tempo).