[Java] Algoritmo ricorsivo per un albero binario

[absinth]

Ciao a tutti! Non riesco a venirne fuori da questo algoritmo.
Non è specificato di farlo in Java ma è l'unico linguaggio che conosco un po'. La consegna è:

Sia T un albero binario proprio dove ogni nodo $v \in T$ memorizza un valore $v.val$ che può essere 1 o -1. Un nodo $v \in T$ si dice strong se la somma dei valori memorizzati nei nodi del sottoalbero $T_v$ è $>0$. Progettare un algoritmo ricorsivo per contare il numero di nodi strong in T, analizzandone la complessità.

La mia idea sarebbe quella di calcolare ricorsivamente in ogni sottoalbero la somma dei valori facendo un attraversamento. E' chiaro che mentre calcolo la somma mi conviene contare già il numero di nodi strong. Il problema è dove salvare il conta strong? Lo spazio di ritorno dalla ricorsione è già occupato dalla somma dei valori.

Java non consente l'utilizzo di pointer arithmetic come in C. Poteva essere comodo passare il contatore per parametro.
Java consente il passaggio per riferimento ad oggetti ma quando sono oggetti Integer, non si possono incrementare ma riassegnare i riferimenti quindi problema identico. (comunque non l'ho mai capito fino in fondo il discorso dei riferimenti)
Siccome non è specificato nulla nella consegna, credo che non si possa modificare in alcun modo l'albero e pensavo di creare nella classe in cui si trovano i metodi di Strong una variabile diciamo globale. Lo so che non è l'idea migliore, però eventualmente viene azzerata dopo la chiamata del metodo. Può andare o non ha senso farlo secondo voi? Prestazioni O(n)

-------classe---------------------------------------------
private int count=0; //variabile globale

public static <T> int nStrong(BinaryTree<T> a)
{
	private int sum = getSum(a.root());
	int s = count;
	count=0;
	return s;
}
private static <T> int getSum(Position<T> v)
{
	int sum=v.val();
	if(v.isExternal())
		return v.val();
	sum += getSum(v.getLeft()) + getSum(v.getRight());
	if(sum>0)
		count++;
	return sum;
}

[xneo1]

Ho poco tempo ora, quindi non ho controllato se l'algoritmo che hai postato è corretto (per il momento mi fido).
Invece di passare alle chiamate ricorsive un int come contatore puoi passare un array int[] di dimensione 1.

[absinth]

Non sono bravo con gli array, così può funzionare?:

public static <T> int nStrong(BinaryTree<T> a)
{
	private int[] somma = getSum(a.root());
	return somma[1];
}
private static <T> int[2] getSum(Position<T> v)
{
	int[] sum = new int[2];
	sum[0] = v.val();
	sum[1] = 0;			
	if(v.val()==1)
		sum[1] = 1;		//se fosse una foglia sarebbe strong
	if(v.isExternal())
		return sum;
	int[] sumLeft = getSum(v.getLeft());
	int[] sumRight = getSum(v.getRight());
	sum[0] += sumLeft[0] + sumRight[0];
	sum[1] = sumLeft[1] + sumRight[1];
	if(sum[0]>0)
		sum[1]++;
	return sum;
}

[xneo1]

no,
invece di sum=new int[2] usa un count=new int[1] e ogni volta che il nodo è strong aggiorni con count[0]++;

[absinth]

grazie per la risposta, scusa ma la prima volta non avevo letto bene la tua risposta, credevo intendessi dimensione 2 per eliminare la variabile globale, ma che differenza c'è allora tra l'avere un array int di dimensione 1 invece di un int? diventa semplicemente un array ma è ancora globale

[xneo1]

No, attenzione, l'array count, lo puoi passare come parametro alle chiamate del metodo ricorsivo.
tu hai il metodo

public static <T> int nStrong(BinaryTree<T> a) {
    int[] count=new int[1]; //contatore
    int sum = getSum(a.root(), count);
    if(sum>0) count[0]++; //anche la radice è un nodo strong, e quindi va contato.
    return count[0]; //count[0] contiene il numero di tutti i nodi strong dell'intero albero
}

che una volta terminato restituisce il numero di nodi strong presenti nell'intero albero.

il metodo ricorsivo lo puoi definire così

private static <T> int getSum(Position<T> v, int[] count) {
   int sum=v.val();
   if(v.isExternal())
      return v.val();
   sum += getSum(v.getLeft()) + getSum(v.getRight());
   if(sum>0)
      count[0]++; //incrementi il contatore.
   return sum;
}

in questo modo quando trovi un nodo strong, puoi incrementare il count scrivendo count[0]++; Essendo un array, e quindi un oggetto, la modifica persisterà anche nelle prossime chiamate ricorsive.

Java usa sempre il passaggio per valore (o per copia) sia che si tratti di un tipo primitivo sia che si tratti di un oggetto.
In Java, quando passi un oggetto come parametro, il nome del parametro punta al valore dello stesso oggetto passato.
cioè
int[] count=new int[0] puoi vederlo in memoria come

count ----------> [0]

se hai un metodo void m(int[] c) //lasciami utlizzare un nome diverso per il parametro, per capirci meglio
e invochi quindi il metodo passando count, m(count), in memoria hai questa situazione

count ----------> [0]<---|
                         |
c -----------------------| 

cioè sia count, che c, sono nomi che stanno puntando allo stesso oggetto (e un riferimento altro non è che un nome che punta ad un oggetto). Ogni modifica che fa c si ripercuote su count e ogni modifica che fa count si ripercuote su c.


Spero di essere stato chiaro.

[absinth]

Si sei stato chiaro grazie mille! L'avevo sentito sto discorso ma non ero sicuro. Pensavo infatti di farlo con un oggetto Integer ma il problema è che Integer è immutable cioè non si può incrementare, invece l'array si ed è ancora un oggetto. Quindi quell'inconveniente (per questa applicazione) che Java sembrava avere rispetto a C in realtà si può superare facilmente

[xneo1]

Si, in questo caso un semplice array va benissimo, ma nulla ti avrebbe impedito di scriverti una classe wrapper mutabile.
Ad esempio avresti potuto scriverti una classe così definita

class Counter {
    private int counter=0;
    public void increment() {
        counter++;
    }

    public int getCounter() {
        return counter;
    }
}