Alberi Binari e ricorsione

[Framek]

Salve a tutti cari amici del forum...
Avrei da chiedervi una mano per quanto concerne degli algoritmi ricorsivi sugli alberi binari ed alberi binari di ricerca.
Ora... non sono prorpio terra terra con Java ma ho quanlche problema a sviluppare alcuni metodi ricorsivi....
Mi spiego meglio... Un caso particolare è quello che: avendo a disposizione una interfaccia come la seguente:

package alberi;  
public interface AlberoBinario extends Albero{  	
public int val(); //Restituisce il valore della radice 	
public AlberoBinario getSin(); 
public AlberoBinario getDes();  
}//AlberoBinario.java

si vuole realizzare un metodo ricorsivo per verificare se un albero binario passato al metodo è un albero binario di ricerca o no. Il metodo avrà questa signature:

public static boolean diRicerca(ABR a, int l){ ... }

E' risaputo che la condizione per cui un ABR lo sia e' che:

"Per ogni nodo V dato, il figlio sx sia minore di V e quello dx sia maggiore di V".

[antotan]

Beh, utilizzando la visita in ordine simmetrico, rimane poco da fare.
Visita l'albero e confronta l'elemento corrente con quello precedente (edit: o meglio, l'elemento padre con l'elemento corrente, segnandoti se il corrente è il figlio destro o il sinistro [serve per sapere che relazione usare]) e vedi se viene rispettata la proprietà dei BST.

Qui ci sono alcuni algoritmi sui BST in C++. La logica è, ovviamente, la stessa, e non dipende troppo dal linguaggio, quindi puoi dare un'occhiata se ti va. Ci trovi anche l'implementazione della visita in ordine simmetrico:

BST

[Framek]

Ciao e grazie per avermi risposto... guarda...io ho provato cosi:

public static boolean diRicerca(AlberoBinImpl a, int root){ 		 		   if(a==null) 			
return true; 		 		
if(a.getSin()!=null && a.getDes()!=null) 			
return (root>=a.getSin().getVal() && root<=a.getDes().getVal());
	return diRicerca(a.getSin(), a.getVal()) && diRicerca(a.getDes(), a.getVal()); 	}

ed ho creato un main tipo questo per testarlo:

package alberi;  
public class MainTree {  	
public static void main(String[] args) { 	 		
AlberoBinImpl  a,b, c, d, e, f, g; 		 		
g = new AlberoBinImpl(13,null,null); 		
f = new AlberoBinImpl(11,null,null); 		
e = new AlberoBinImpl(4,null,null); 		
d = new AlberoBinImpl(3,null,null); 		 		
b = new AlberoBinImpl(5,d,e); 		
c = new AlberoBinImpl(12, f, g); 		
a = new AlberoBinImpl(10,b,c); 
		 		 		
System.out.println(a); 				 		System.out.println(AlberoBinImpl.diRicerca(a, a.getVal())); 			
} 
}//MainTree.java

Il tutto funziona per il primo albero diciamo...ovvero la root ed i 2 figli... poi è come se la ricorsione no venisse fatta sugli altri alberi...In cosa sto sbagliando?
Grazie

[Framek]

AriSalve a tutti... ma non c'è nesusno che mi può dare na mano a testa re se un Albero Binario è un BST???...ormai non ci dormo più la notte!!!

A livello teorico ho capito bene che occorre sempre verificare, oltre al fatto che dato un nodo il figlio sx deve avere valore minore ed il figlio dx deve avere valore maggiore, il fatto che data una root che fa da ""spartitraffico"" tra i due insiemi, l'insieme di sx deve avere tutti valori rigorosamente minori della rott e dualmente l'insieme dx deve avere val maggiori!!!
Spero che qualcuno mi aiuti!!!

[Framek]

Secondo voi è coretta in questo modo??? Di andare va...:

public static boolean isBST(AlberoBinImpl a){

if(a==null)
return true;

else
return isBST(a.getSin())&&
isBST(a.getDes())&&
eMinoreDi(a.getVal(), a.getSin())&&
eMaggioreDi(a.getVal(), a.getDes());
}

private static boolean eMinoreDi(int val, AlberoBinImpl a) {

if(a==null) return true;

else if(a.getSin()==null && a.getDes()==null)
return a.getVal()<val;
else
return a.getVal()<val && eMinoreDi(val, a.getSin()) && eMinoreDi(val, a.getDes());
}
private static boolean eMaggioreDi(int val, AlberoBinImpl a) {

if(a==null) return true;

else if(a.getSin()==null && a.getDes()==null)
return a.getVal()>val;

return a.getVal()>val && eMaggioreDi(val, a.getSin()) && eMaggioreDi(val, a.getDes());
}