Newsgroup: it.comp.java
Titolo: strutture dati non lineari in java

Salve a tutti,
sto facendo degli esercizi di programmazione in java che riguardano gli
alberi binari. Uno di questri dice così:
Data una rappresentazione collegata di alberi binari in cui
l'informazione in ciascun nodo è una stringa, realizzare un metodo
statico pubblico che, dato il riferimento alla radice di un albero
binario alb e data una stringa x, restituisca il padre del nodo la cui
informazione è x; se nessun nodo ha informazione x, il metodo deve
restituire null. Specificare il costo asintotico in tempo e in spazio
del metodo, indicando esplicitamente la dimensione dell'input,
l'istruzione dominante e descrivendo il caso peggiore quando
necessario.
Io ho fatto così:
public static NodoAlbero padre(NodoAlbero a, String x)
{
if ((a.right == null) || (a.left == null))
return null;
else if (a.right.info.equals(x) || a.left.info.equals(x))
return a;
else return (padre(a.left, x) == null) ? padre(a.right, x) :
padre(a.left, x);
}
ma funziona solo se l'albero è simmetrico e quindi non gli ritornano
null altrimenti fa "Exception in thread "main"
java.lang.NullPointerException".
Qualcuno mi può dare una mano?
PS
Chiedi scusa per il cross prosting (su it.comp.programmare) ma sono
proprio alla frutta 8-)

 writes:
P> Salve a tutti, sto facendo degli esercizi di programmazione in java
P> che riguardano gli alberi binari. Uno di questri dice così:
0001 public static NodoAlbero padre(NodoAlbero a, String x)
0002 {
0003   if ((a.right == null) || (a.left == null))
0004     return null;
0005   else if (a.right.info.equals(x) || a.left.info.equals(x))
0006     return a;
0007   else return (padre(a.left, x) == null) ? 
0008 	 padre(a.right, x) :
0009 	 padre(a.left, x);
0010 
0011 }
P> ma funziona solo se l'albero è simmetrico e quindi non gli
P> ritornano null altrimenti fa "Exception in thread "main"
P> java.lang.NullPointerException".
P> Qualcuno mi può dare una mano?
La tua  eccezione è in main,  non in padre,  quindi è in main  che usi
(male)  il  valore null  tornato  da  padre()!  CERCA IN  QUEL  METODO
l'errore.
Peraltro il test in linea 3 di padre() è errato.
Prova a creare quest'albero:
<-- SINISTRA               DESTRA -->
            PAPERINO
           /        \
          /          \
       PIPPO         PLUTO
        / \          /   \
     null null      /    null
                  OSSO
e a cercare OSSO...
-- 
 /\            ___
/___/\__|_|\_|__|___Gian Uberto Lauri_____________________
  //--\ | | \|  |   Integralista GNUslamico  
\/		    e allevatore di bug da competizione

 e a cercare OSSO...
		NodoAlbero b = padre(A, "OSSO");
		if (b != null)
		  System.out.println(
b.info
);
		else
		  System.out.println("Nodo non trovato");
Con queste righe nel metodo main mi stampa a video "Nodo non trovato"
mentre se cerco "PIPPO" mi stampa "PAPERINO".

> Prova a creare quest'albero: [CUT]
P> Fatto
P> Con queste righe nel metodo main mi stampa a video "Nodo non
P> trovato" mentre se cerco "PIPPO" mi stampa "PAPERINO".
Dato che le specifiche dicono 
   "Data una  rappresentazione collegata  di alberi binari  in cui
    l'informazione in  ciascun nodo  è una stringa,  realizzare un
    metodo statico  pubblico che, dato il  riferimento alla radice
    di un albero binario alb  e data una stringa x, restituisca il
    padre  del nodo la  cui informazione  è x;  se nessun  nodo ha
    informazione x, il metodo deve restituire null.
direi che  l'output per l'input PIPPO  è corretto.  Quello  per OSSO è
ovviamente errato  perché quell'albero è  stato fatto apposta  per far
dare un risultato sbagliato al tuo codice :).


 Qualcuno mi può dare una mano?
Hint: stampa lo stacktrace, contiene un sacco di informazioni utili
(non ultima la linea in cui viene sollevata la NullPointerException).
Così, ad occhio, ti posso dire che quel codice è error-prone se gli
arriva un parametro 'a' null o se trova un nodo con info a null. E' il
massimo che si può dire.

 return null;
Questo ritorna NULL se uno dei 2 figli č vuoto, ma un nodo č foglia se 
entrambi sono vuoti, quindi dovrebbe essere:
if ((a.right == null) && (a.left == null))
return null;