[JAVA] Ricorsione e alberi

[Javino89]

So che probabilmente già il titolo farà fuggire molte persone ma spero che qualche buon'anima venga ad aiutarmi xD

Allora premetto che queste sono cose che provengono dritte dritte dall'università.

Ho dovuto implementare una classe per un Albero generico, con vari metodi di supporto. Ho dei problemi con alcuni metodi RICORSIVI per il calcolo di proprietà dell'albero in questione.

Intanto, un metodo richiesto è: Dato un nodo, calcolarne la profondità.
La segnatura del metodo data è: public int depth()

Ora il problema qual'è.. la mia classe albero fa uso dei tipi generici.

public class MyTree<E> implements Tree<E>...
{
private Position<E> root;

ecc..

Ora, dal main, dove creo l'albero,chiamato t ad esempio, come faccio a chiamare il metodo depth(nodo creato nel main)? Mi da problemi.

Nel main ho:

Tree<Integer> t = new MyTree<Integer>();
Position<Integer> nodo1 = new MyNodo(100);
Position... ecc..

Non posso passare argomenti a depth, quindi come diamine faccio a calcolare la profondità di uno specifico nodo?

Ammesso che potessi passargli argomenti, se gli passo una Position<Integer> nodo, mi da errore perché nella classe albero giustamente uso il tipo generico E..

Se può servire, il codice che calcola la profondità di un nodo è questo:

public int depth(Position<E> v)
{
	if(isRoot(v))
	{
		return 0;
	}
	else return 1 + depth(v.getParent());
}

Grazie.

Ps: Ho problemi poi con la realizzazione di veri e propri metodi ricorsivi, ma li vediamo dopo, meglio una cosa alla volta^^'

[Javino89]

Vaaa beneeeee questa prima cosa nessuno l'ha capita ma ho risolto da solo per fortuna.

Altra domanda, devo fare un metodo che mi restituisce il numero di occorrenze di un dato
elemento (int) in un albero.
Quello che ho scritto io restituisce sempre zero...

public int contaOccorrenze(E e)
{
	int h = 0;
	if(root.element() == e)
	{
		h = h + 1;
	}
	contaOccorrenze(e,root,h);
	return h;
}

private void contaOccorrenze(E e, Position<E> n, int h)
{
	for(Position<E> w : n.getChildren())
	{
		if(w.element() == e)
		{
			h = 1 + contaOccorrenze(e,w,h);
		}
		contaOccorrenze(e,w,h);
	}
}

[Pastore12]

    // ok
    int h = 0;
    if(root.element() == e)
    {
        // se i due oggetti sono lo stesso oggetto h = 1
        h = h + 1;
    }
    // h è un int, quindi viene passato per valore, quindi questa istruzione non modifica h
    contaOccorrenze(e,root,h);

    // h=0 oppure h=1, a seconda dell' if precedente
    return h; 

[Javino89]

Ok quindi come faccio a modificare h?

public int contaOccorrenze(E e)
{
	return contaOccorrenze(e,root);
}

public int contaOccorrenze(E e, Position<E> v)
{
	int h = 0;
	
	if(v.element() == e)
	{
		h = h + 1;
	}
	for(Position<E> w : v.element())
	{
		return contaOccorrenze(e,w);
	}
	return h;
}

Può andare?

Edit: No, mi torna 0 pure così u.u

Facendo così mi conta bene solo se il nodo che gli passo è foglia, altrimenti torna 0... sto per spaccare il pc, odio la ricorsione!

public int contaOccorrenze(E elem)
    {
        return contaOccorrenzeRic(elem, root,0);
    }

    private int contaOccorrenzeRic(E elem, Position<E> r, int h)
    {
        for(Position<E> w : r.getChildren())
        {
            if(w.element() == elem)
            {
                h = 1 + contaOccorrenzeRic(elem,w,h);
            }
            h = contaOccorrenzeRic(elem,w,h);
        }
        return h;
    }

[Pastore12]

Originariamente inviato da Javino89
odio la ricorsione!

Immagina un ceffone in arrivo all'altezza della tempia destra. Ma è meglio se ti fai aiutate da un amico, meglio se palestrato, a simulare per bene la situazione.

Hai un albero di cui conosci la radice, che alla fine è un nodo pure lui.

Il tuo metodo riceve un nodo E e un nodo N.
Chiamiamolo contaOccorrenze (E,N)
E è il nodo che cerchi, N è un nodo generico dell'albero che navighi.
Quindi il metodo che fa: controllo se E ed N coincidono.
Poi chiama ricorsivamente se stesso su tutti i figli F1, F2, ..., Fn di N, passandogli E.
Il risultato della chiamata ricorsiva i contaOccorrenze (E,Fi) è il numero delle ricorrenze di E nel sottoalbero con radice Fi.
Il numero di ricorrenze complessive sarà dato dalla somma di tutte le ricorrenze trovate nei figli di N e in N stesso. Il metodo ricorsivo contaOccorrenze restituisce questa somma.

Ovviamente il sottoalbero di E non dovrebbe contenere occorrenze di E... altrimenti la navigazione dell'albero se ne va a quel paese...

[Javino89]

Scusa non ho capito l'ultima frase. Io devo contare tutte le occorrenze di e nell'albero, cosa vuoi dire che il sottoalbero di e non deve contenere occorrenze di e?

Il ragionamento che hai fatto mi è chiaro, ma mi sfugge come "trattare" la variabile che mi memorizzerà ogni volta le occorrenze di e.

[Pastore12]

Potrebbe andare:

contaOccorrenze (N, E)
   numeroOccorrenze = 0
   se N==E
      numeroOccorrenze = 1
   per ogni figlio Fi di N
      numeroOccorrenze = numeroOccorrenze + contaOccorrenze (Fi, E)

   return numeroOccorrenze

}

Se N==E, significa che i figli di N sono gli stessi figli di E?
Se è così e se nel sottoalbero con radice E c'è almeno un altro nodo E, allora nel sottoalbero di E ci sono infiniti nodi E.

[Javino89]

No allora, E è un tipo generico. E == N significa : if(N.getElement() == e)

Cioé i nodi hanno un campo di tipo E accessibile tramite il metodo getElement(). Io devo contare quanti nodi nell'albero hanno l'elemento e passato come parametro.

Il codice java corrispondente a ciò che hai scritto risulta:

public int contaOccorrenze(E e, Position<E> n)
{
    int occ = 0;
	if(n.getElement() == e)
	{
		occ = 1;
	}
	for(Position<E> w : n.getChildren())
	{
		occ = occ + contaOccorrenze(e,w);
	}
	return occ;
}

Ora vado a pranzo,dopo lo provo e faccio sapere

[Pastore12]

Mi raccomando però... A==B in java, per gli oggetti, significa che l'oggetto A ha lo stesso riferimento in memoria dell'oggetto B, ossia A e B sono esattamente lo stesso oggetto, non solo che A e B hanno al loro interno valori identici.

[VincenzoTheBest]

Originariamente inviato da Pastore12
Potrebbe andare:

contaOccorrenze (N, E)
   numeroOccorrenze = 0
   se N==E
      numeroOccorrenze = 1
   per ogni figlio Fi di N
      numeroOccorrenze = numeroOccorrenze + contaOccorrenze (Fi, E)

   return numeroOccorrenze

}

Se N==E, significa che i figli di N sono gli stessi figli di E?
Se è così e se nel sottoalbero con radice E c'è almeno un altro nodo E, allora nel sottoalbero di E ci sono infiniti nodi E.

Questo algoritmo non fa ciò che la specifica del metodo richiede.
Inoltre Position<E> n incapsula E e (l'informazione del nodo), quindi non ha senso fare questo genere di confronto N==E.