Algoritmo per calcolo di altezza su ABR iterativo.

[purpleinarose]

Ciao a tutti, ho bisogno di scrivere l'algoritmo per il calcolo dell'altezza di un albero binario di ricerca in forma iterativa, visto che in modo ricorsivo mi riempie lo stack della jvm quando lavora su una quantita' di dati molto alta (10000000 inserimenti).
Potreste darmi una mano, o almeno spiegarmi come fare, senza stare a scrivere righe di codice?
Per favore, sto impazzendo. Grazie in anticipo

[fr84]

Prova così, dovrebbe funzionare.
L'algoritmo cercà il nodo a profondità massima prima nel sottoalbero sinistro, poi in quello destro.
Se hai bisogno di chiarimenti, chiedi pure

public int altezza(Nodo nodo) {
    //costanti 
    final int RICERCA_A_SINISTRA = 0;
    final int RITORNO_INDIETRO = 1;
    final int RICERCA_A_DESTRA=2;
    final Integer SINISTRA=Integer.valueOf(RICERCA_A_SINISTRA);
    final Integer DESTRA=Integer.valueOf(RICERCA_A_DESTRA);
    final Integer INDIETRO=Integer.valueOf(RITORNO_INDIETRO);
		
    int profondita_massima = 0;
    int profondita_attuale = 0;
    /* il Vector "nodi" conterrà i nodi che l'algoritmo percorrerà durante la ricerca della
     * profondità massima. Permette all'algoritmo di tornare al nodo precedente quando
     * ha terminato le operazioni su un sottoalbero
     */
    Vector<Nodo> nodi = new Vector<Nodo>();
    /* il Vector "operazione" conterrà l'operazione da eseguire ad ogni nodo; le operazioni
     * possono essere le seguenti:
     * SINISTRA: ricerca nel sottoalbero sinistro
     * DESTRA: ricerca nel sottoalbero destro
     * INDIETRO: dopo aver terminato la ricerca nei sottoalberi destro e sinistro di un
     *nodo l'algoritmo torna al nodo precedente    
     */
    Vector<Integer> operazione = new Vector<Integer>();
    if (nodo == null) //se l'albero è vuoto ritorno 0
        return 0;
    else {
        profondita_massima++;
        profondita_attuale++;
        nodi.add(nodo);
        operazione.add(SINISTRA); //l'albero sarà esplorato a partire dal sottoalbero sinistro
    }
    while (nodi.size() > 0) {
        Nodo temp;
        switch (operazione.lastElement()) {
             case (RICERCA_A_SINISTRA):
                 temp = nodi.lastElement();
                 //se il sottoalbero sinistro è vuoto cerco in quello destro 
                 if (temp.sx == null)
                    operazione.setElementAt(DESTRA,operazione.size() - 1);
                 else {
                     //quando l'algoritmo tornerà a questo nodo avrà già esplorato il sottoalbero
                     //sinistro e dovrà esplorare quello destro
                     operazione.setElementAt(DESTRA,operazione.size() - 1);
                     nodi.add(temp.sx);
                     operazione.add(SINISTRA);
                     profondita_attuale++;
	        if (profondita_attuale > profondita_massima)
	            profondita_massima = profondita_attuale;
                 }
	break;
	case (RICERCA_A_DESTRA):
	    temp = nodi.lastElement();
	    //se il sottoalbero destro è vuoto torno al nodo precedente 
                 if (temp.dx == null)
                     operazione.setElementAt(INDIETRO,operazione.size() - 1);
                 //quando l'algoritmo tornerà a questo nodo avrà già esplorato sia il sottoalbero
                 //sinistro che quello destro e dovrà tornare al nodo precedente
                 else {
                     operazione.setElementAt(INDIETRO,operazione.size() - 1);
                     nodi.add(temp.dx);
                     profondita_attuale++;
                     if (profondita_attuale > profondita_massima)
                         profondita_massima = profondita_attuale;
                     operazione.add(SINISTRA);
                 }
	break;
	case (RITORNO_INDIETRO):
                 //se la ricerca in un dato sottoalbero è stata completata, l'algoritmo non
                 //tornerà più a quel nodo, sarà quindi possibile rimuoverlo da "nodi"
                 nodi.removeElementAt(nodi.size() - 1);
                 operazione.removeElementAt(operazione.size() - 1);
                 profondita_attuale--;
	break;
         }
     }
     return profondita_massima;
}