Universita algoritmo in java

[spud85]

ciao mi si richiedeva come esercizio di utilizzare la ricorsione per la ricerca del predecessore di un numero in un albero binario di ricerca;
questo è il codice che ho fatto e mi restituisce sempre la radice dell'albero anziche del predecessore....dove sbaglio???

class prec {

public static int precprec(int k, BSTnode root) {

BSTnode p= root;
if(root == null)
return 0;

else if((count(root)==1) || (count(root)==2))
return 0;


else {

BSTnode prev = p;
if(prev.info >= k)

precprec(k, p.left);
else {

precprec(k, p.right);
}

return prev.info;
}

}


public static int count(BSTnode h) {

if(h==null) return 0;

return 1+ count(h.left) + count(h.right);
}

public static BSTnode albero2() {

BSTnode a,b,c,d,e,f,g;

a = new BSTnode();
b = new BSTnode();
c = new BSTnode();
d = new BSTnode();
e = new BSTnode();
f = new BSTnode();
g = new BSTnode();

a.info = 25; a.left= null;a.right=null;
b.info = 75; b.left=null;b.right=null;
c.info = 150;c.left=null;c.right=null;
d.info = 300;d.left=null;d.right=null;
e.info = 50;e.left = a;e.right=b;
f.info =200;f.left=c;f.right=d;
g.info=100;g.left=e;g.right=f;
BSTnode albero = g;
return albero;
}




public static void main(String args[]) {

BSTnode p = albero2();
int r=precprec(75, p);
int numeronodi= count(p);
System.out.println(r);
System.out.println(p);



}

}


************************************************** ******
************************************************** ******
class BSTnode {

public BSTnode left, right;
public int info;




public BSTnode(){
left =null;
right=null;
info= 0;
}

public BSTnode(BSTnode l, BSTnode r, int i) {
left=l;
right=r;
info=i;
}

public BSTnode(int i) {
left=right=null;
info=i;
}


public boolean isLeaf() {
return left==null && right==null;
}
}

[Pastore12]

dove sbaglio???

A non usare il tag [c ode] [/c ode] o [p hp] [/p hp] come da regolamento...

class prec
{

	public static int precprec(int k, BSTnode root)
	{
		BSTnode p= root;
		if(root == null)
			return 0;

		if((count(root)==1) || (count(root)==2))
			return 0;
			
		// Ho eliminato qualche else ininfluenti...

		BSTnode prev = p;
		if(prev.info >= k)
			precprec(k, p.left);
		else
			precprec(k, p.right);
		
		return prev.info;
	}


	public static int count(BSTnode h)
	{
		if(h==null) return 0;
		return 1+ count(h.left) + count(h.right);
	}


	public static BSTnode albero2()
	{
		BSTnode a,b,c,d,e,f,g;

		a = new BSTnode();
		b = new BSTnode();
		c = new BSTnode();
		d = new BSTnode();
		e = new BSTnode();
		f = new BSTnode();
		g = new BSTnode();

		a.info = 25; a.left= null;a.right=null;
		b.info = 75; b.left=null;b.right=null;
		c.info = 150;c.left=null;c.right=null;
		d.info = 300;d.left=null;d.right=null;
		e.info = 50;e.left = a;e.right=b;
		f.info =200;f.left=c;f.right=d;
		g.info=100;g.left=e;g.right=f;
		BSTnode albero = g;

		return albero;
	}




	public static void main(String args[])
	{
		BSTnode p = albero2();
		int r=precprec(75, p);
		int numeronodi= count(p);
		System.out.println(r);
		System.out.println(p);
	}
}


********************************************************
********************************************************

class BSTnode
{

	public BSTnode left, right;
	public int info;

	public BSTnode()
	{
		left =null;
		right=null;
		info= 0;
	}

	public BSTnode(BSTnode l, BSTnode r, int i)
	{
		left=l;
		right=r;
		info=i;
	}

	public BSTnode(int i)
	{
		left=right=null;
		info=i;
	}


	public boolean isLeaf()
	{
		return left==null && right==null;
	}
}

Alcune note un po' stupide...:

// Nome delle con la prima lettera maiuscola!!!
class prec
{

	// Forse il nome doveva essere precPrec
	public static int precprec(int k, BSTnode root)
	{

E adesso si aspetta...

[Pastore12]

Controlla questo codice... :

    public static int precprec(int k, BSTnode root)
    {
        BSTnode p= root;
        if(root == null)
            return 0;

        if((count(root)==1) || (count(root)==2))
            return 0;
            
        // Ho eliminato qualche else ininfluenti...

        BSTnode prev = p;
        if(prev.info >= k)
            precprec(k, p.left);
        else
            precprec(k, p.right);
        
        return prev.info;
    } 

chiami precprec(k, p.left);oppure precprec(k, p.right); ma non usi il risultato di questa chimata, alla fine è come se queste chiamate non le facessi proprio, visto che in ogni caso restituisci prev.info; dove prev è la root dell'albero... spero ti sia chiaro...

[spud85]

ok...questo l'ho capito.....solo nn so come riuscire a mantenere un riferimento al nodo visitato ad ogni ricorsione... in termini di codice.....