class e struct sono praticamente la stessa cosa, l'unica differenza e' lo specificatore di visibilita' di default: private in una classe, public in una struct.
vorrei sapere, se qualcuno mi può aiutare, è corretto creare due classi:
-Nodo con attributi pubblici
In linea generale non è sbagliato; semplifica l'implementazione ed evita noiose complicazioni. Diciamo piuttosto che se non strettamente necessario, l'implementazione del nodo dovrebbe stare nel file.cpp piuttosto che nel file.h. In fin dei conti quello che interessa è il payload (in questo caso il campo chiave), per cui i metodi di Albero dovrebbero restituire quello invece che un nodo (che interessa solo l'implementazione, non l'utente).