[Java][Alberi Binari] Perplessità

[shatteringlass]

A una settimana all'esame, mi sto scontrando con le ultimissime resistenze opposte dalle strutture dati. In questo caso fatico a trovare un modo semplice per implementare quanto richiesto dall'esercizio inserito nello spoiler. Anticipo che si tratta di un esercizio un po'particolare...Grazie a chi vorrà e/o saprà aiutarmi.

public class NodoBin {
    String info;
    NodoBin sin;
	NodoBin des;
	
	public NodoBin(String i, NodoBin s, NodoBin d) {
		this.info = i;
		this.sin = s;
		this.des = d;
	}
}

Data la rappresentazione collegata di alberi binari presentata qui
sopra, i cui nodi contengono un'informazione di tipo stringa, scrivere
nella classe Eserc4.java un metodo statico exists
che preso in ingresso
il riferimento alla radice di un albero binario a ed una stringa s,
restituisca un valore booleano TRUE se esiste almeno un nodo dell'albero che ha un numero dispari di figli e che contiene la stringa s,
FALSE altrimenti.

[Rggb1]

Anche se fatichi a trovare un modo semplice, parti dal modo che hai in mente: proponi e vediamo.

[apatriarca]

Un piccolo suggerimento nel caso non ti venissero idee:

Potrebbe essere comodo avere un metodo che, dato un nodo dell'albero, restituisce il numero di nodi presenti nell'albero che ha quel nodo come radice, un valore booleano che ti restituisce vero se la stringa che stai cercando è presente nell'albero e un ulteriore booleano che ti dice se un qualche sottoalbero rispetta la condizione del tuo problema. Data una funzione di questo tipo la funzione exists dovrebbe semplicemente restituire l'ultimo valore restituito dalla funzione. Java, sfortunatamente, non supporta nativamente tuple di valori e devi quindi implementare una classe adeguata per il valore di ritorno di quel metodo.

[shatteringlass]

public class Eserc4
{
	public static boolean exists (NodoBin rad, String s)
	{
		if(rad==null)
			return false;
		if(rad.info.equals(s)&&(rad.sin!=null||rad.des!=null))
			return true;
		else
			return exists(rad.sin,s)||exists(rad.des,s);
	}
}

Questo è il codice dell'esercizio da me stilato. Va sottolineato che questa non è la soluzione, infatti con una classe di prova appositamente scritta ottengo true a sproposito.

[apatriarca]

Ho appena notato di aver letto male il problema. Pensavo ad un problema leggermente diverso: stabilire cioè se esiste un sottoalbero contenente la stringa e che ha un numero di nodi pari (i discendenti della radice sono dispari). Ma il problema dato è molto più semplice. Ti invito comunque una volta risolto questo a provare questo nuovo problema.

Il metodo più semplice è forse quello di dividere il tuo problema risolvendo ognuna delle condizioni separatamente. Per un qualche nodo, exists è vero se lo è per un suo qualche sottoalbero oppure se contiene la stringa cercata e ha un numero di figli dispari. È quasi tutto corretto tranne il test per stabilire se il numero di figli è dispari. Dovrebbe essere:

((rad.sin!=null && rad.des==null)||(rad.sin==null && rad.des!=null))

infatti devi verificare che uno dei due sia nullo e l'altro no.

[apatriarca]

O meglio ancora potresti usare:

((rad.sin == null) ^ (rad.des == null))

dove ^ è l'operatore XOR di or esclusivo che è quello che desideri in questo caso. Solo una delle due condizioni deve essere verificata. Puoi anche usare != null.

[shatteringlass]

Ero arrivato anche io alla soluzione

((rad.sin!=null && rad.des==null)||(rad.sin==null && rad.des!=null)) 

In effetti inizialmente il problema l'avevo interpretato proprio come te. In quel caso non saprei bene come procedere. Ho pensato anche io di creare un metodo che conta i nodi e verifica se sono in numero pari o dispari...però credo che la ricerca dell'oggetto non possa procedere ricorsivamente.
Deve infatti essere verificato contemporaneamente che un sottoalbero abbia nodi in numero dispari (esclusa la radice) e contenga in uno dei suoi nodi la stringa cercata. Perciò credo sia necessario visitare l'albero intero prima di poter giudicare, anche se la stringa viene trovata subito. Ad esempio se si trova nel figlio sinistro della radice, si può decidere di contare i nodi del solo sottoalbero sinistro, e restituire true se e solo se essi sono in numero pari, false altrimenti. dico male?