//inizio classe

protected class Node implements Serializable {

/**
* L'elemento contenuto nel nodo [in questo caso un ObjectWithKey].
*/
E element;

/**
* I riferimenti ai nodi figli (destro e sinistro).
*/
Node left, right;

/**
* Crea un nodo vuoto [con tutti i campi a null].
*/
Node() {
element = null;
left = null;
right = null;
}

/**
* Metodo di appoggio che visita l'albero inorder e restituisce una
* String con tutti gli elementi.
*
* @param s la stringa che contine la stampa in order,questo parametro e' utile per la ricorsione.
* @return La stringa contenente gli elementi in order.
*/
String toStringInorder(String s) {
if(!left.isEmpty()) s = left.toStringInorder(s);
s = s + "\n" + element.getKey().toString();
if(!right.isEmpty()) s = right.toStringInorder(s);
return s;
}

/**
* Metodo di appoggio per calcolare l'altezza dell'albero.
*
* @param p un intero che rappresenta l'altezza del nodo su cui si richiama la height.
* @return l'altezza dell'albero che ha come radice il nodo corrente.
*/
int height(int p) {
if(!isEmpty()) {
if(left.isEmpty() && right.isEmpty()) return p;
else if(left.isEmpty()) return right.height(p+1);
else if(right.isEmpty()) return left.height(p+1);
else if(left.height(p+1) > right.height(p+1)) return left.height(p+1);
else return right.height(p+1);
}
else return p;
}
/*Qui sotto riportiamo una soluzione piu' "vicina" alla definizione
induttiva di altezza, che e' piu' elegante ma leggermente meno
efficente*/
//return left.isEmpty() && right.isEmpty() ? p : 1 + Math.max (left.height(p), right.height(p));

/**
* Metodo di appoggio che conta il numero di nodi che compongono l'albero.
*
* @param n il numero di nodi precedenti al nodo corrente.
* @return il numero di nodi dell'albero.
*/
int countNode(int n) {
if(!isEmpty()) {
if(!left.isEmpty()) {n = left.countNode(n+1);}
if(!right.isEmpty()) {n = right.countNode(n+1);}
return n;
}
else return n;
}

/**
* Metodo di appoggio che restituisce l'elemento cercato data una chiave.
*
* @param key la chiave secondo cui fare la ricerca.
* @return l'elemento corrispondente alla chiave data.
*/
private E find(K key) {
Node node = this;
int confronto = 0;
while(!node.isEmpty() && (confronto = key.compareTo(node.element.getKey())) != 0) {
if(confronto < 0) node = node.left;
else node = node.right;
}
return node.element;
}

/**
* Metodo di appoggio che verifica se un nodo e' vuoto.
*/
boolean isEmpty() {
return element == null && left == null && right == null;
}

/**
* Metodo che sovrascrive i dati del nodo corrente con quelli del nodo specificato.
*
* @param nd nodo che contiene i valori da assegnare ai campi del nodo corrente.
*/
void setTo(Node nd) {
element = nd.element;
left = nd.left;
right = nd.right;
}

/**
* Metodo che crea una foglia [left e right = nodo vuoto].
*
* @param element l'elemento che deve contenere la foglia che si vuole creare.
*/
void setToLeaf(E element) {
this.element = element;
left = new Node();
right = new Node();
}

/**
* Metodo di appoggio che aggiunge un nuovo nodo lasciando invariato l'ordine dell'albero.
*
* @param elemToAdd l'elemento che dovra' contenere il nuovo nodo.
* @return ritorna null se l'elemento che si vuole aggiungere non ha una
* chiave preesistente nell'albero, se la chiave è gia presente nell'albero
* sovrascrive il nodo preesistente e ne restituisce il valore.
*/
private E add(E el) {
E ris = null;
Node t = this;
while(!t.isEmpty()) {
if(el.getKey().compareTo(t.element.getKey()) < 0) t = t.left;
else if(el.getKey().compareTo(t.element.getKey()) > 0) t = t.right;
else {
ris = t.element;
t.element = el;
return ris;
}
}
t.setToLeaf(el);
return ris;
}

/**
* Metodo di appoggio che effettua la rimozione dell'elemento di chiave specificata.
*
* @param key la chiave dell'elemento che si desidera rimuovere.
* @return E l'elemento rimosso , null se non esiste.
*/
private E remove(K key) {
E ris = null;
Node node = this;
while(!node.isEmpty() && key != node.element.getKey()) {
if(key.compareTo(node.element.getKey()) < 0) node = node.left; //questi non devono essere setTo
else if(key.compareTo(node.element.getKey()) > 0) node = node.right;//perche' servono per fare le iterazioni
}
if(!node.isEmpty()) {
if(node.left.isEmpty()) node.setTo(node.right);
else if(node.right.isEmpty()) node.setTo(node.left);
else {
ris = node.element;
node.element = findAndDeleteMin(node.right);
}
}
return ris;
}

/**
* Metodo di appoggio per la remove per restituire e cancellare il
* minimo elemento di un albero.
*
* @param node il nodo-radice dell'albero di cui si vuole trovare il minimo.
* @return il valore del nodo cancellato [il minimo elemento].
*/
private E findAndDeleteMin(Node node) {
while(!node.left.isEmpty()) node = node.left;
E min = node.element;
node.setTo(node.right);
return min;
}

}

//fine classe

questo è il codice che implementa serializable...:-D...è un pò lunghino...