[JAVA] Verificare se due alberi binari sono uguali

[marcoeanna]

Salve a tutti, mi sono iscritto da poco su questo forum, spero di trovarmi bene Apro questa discussione in quanto sto preparando l'esame di Strutture Dati ma ho delle difficoltà sull'argomento degli alberi binari e quindi anche con la ricorsione.

Sto provando a fare l'esercizio che chiede di scrivere una funzione che restituisce true o false se gli alberi binari in questione sono uguali.
Ho scritto il codice ma non funziona bene, in particolare noto che se vado a cambiare i valori dei figli sinistri non mi ritorna false, mentre cambiando sui figli destri funziona. Dove sbaglio?

package alberoBinario;

import java.util.logging.Logger;

import binaryTree.BinaryTree;
import binaryTree.LinkedBinaryTree;
import position.Position;

public class Ex4 {

	private static Logger logger = Logger.getLogger("global");

	public static void main(String[] args){
		LinkedBinaryTree<Integer> alberoT = new LinkedBinaryTree<>();
		Position<Integer> radiceT = alberoT.addRoot(0);
		Position<Integer> t1 = alberoT.insertLeft(radiceT, 1);
		Position<Integer> t2 = alberoT.insertRight(radiceT, 2);
		Position<Integer> t3 = alberoT.insertLeft(t2, 3);
		Position<Integer> t4 = alberoT.insertRight(t2, 4);


		LinkedBinaryTree<Integer> alberoS = new LinkedBinaryTree<>();
		Position<Integer> radiceS = alberoS.addRoot(0);
		Position<Integer> s1 = alberoS.insertLeft(radiceS, 1);
		Position<Integer> s2 = alberoS.insertRight(radiceS, 2);
		Position<Integer> s3 = alberoS.insertLeft(s2, 3);
		Position<Integer> s4 = alberoS.insertRight(s2, 4);

		System.out.println("I due alberi binari sono uguali? "+uguali(alberoT, alberoS));
	}


	public static <E> boolean uguali(BinaryTree<E> T, BinaryTree<E> S){
		if(T.isEmpty() && !S.isEmpty())
			return false;
		if(S.isEmpty() && !T.isEmpty())
			return false;
		if(T.isEmpty() && S.isEmpty())
			return true;
		return uguali(T, T.root(), S, S.root(), false);
	}


	public static <E> boolean uguali(BinaryTree<E> T, Position<E> vT, BinaryTree<E> S, Position<E> vS, boolean result){
		if(vT.element().equals(vS.element()))
			result = true;
		else
			return false;


		if( (T.hasLeft(vT) && !S.hasLeft(vS))   ||   (!T.hasLeft(vT) && S.hasLeft(vS)) ){
			result = false;
			return result;
		}

		if(T.hasRight(vT) && !S.hasRight(vS)    ||   (!T.hasRight(vT) && S.hasRight(vS)) ){
			result = false;
			return result;
		}

		if(T.hasLeft(vT) && S.hasLeft(vS))
			result = uguali(T, T.left(vT), S, S.left(vS), result);


		if(T.hasRight(vT) && S.hasRight(vS))
			result = uguali(T, T.right(vT), S, S.right(vS), result);


		return result;
	}
}

Spero di leggere qualche vostra risposta grazie in anticipo

[sottovento]

Sarebbe interessante provarlo; puoi postare le parti mancanti? (vale a dire i package binaryTree e position?)

[marcoeanna]

ecco il pacchetto binaryTree

[marcoeanna]

ecco il pacchetto position

[sottovento]

Purtroppo mi sono accorto che non e' cosi' semplice perche' quei package fanno riferimento ad altri package quali

position
tree
nodeList
exception


pertanto non si puo' compilare.

Comunque non credo che serva. E' meglio controllare questo pezzo di codice del metodo uguali() (il secondo):

		if(T.hasLeft(vT) && S.hasLeft(vS))
			result = uguali(T, T.left(vT), S, S.left(vS), result);


		if(T.hasRight(vT) && S.hasRight(vS))
			result = uguali(T, T.right(vT), S, S.right(vS), result);

Con il secondo controllo perdi il risultato del primo controllo perche' result viene sovrascritto

[marcoeanna]

Originariamente inviato da sottovento

Purtroppo mi sono accorto che non e' cosi' semplice perche' quei package fanno riferimento ad altri package quali

position
tree
nodeList
exception


pertanto non si puo' compilare.

Comunque non credo che serva. E' meglio controllare questo pezzo di codice del metodo uguali() (il secondo):

		if(T.hasLeft(vT) && S.hasLeft(vS))
			result = uguali(T, T.left(vT), S, S.left(vS), result);


		if(T.hasRight(vT) && S.hasRight(vS))
			result = uguali(T, T.right(vT), S, S.right(vS), result);

Con il secondo controllo perdi il risultato del primo controllo perche' result viene sovrascritto

Ciao sottovento, prima di tutto grazie per esserti interessato a questo problema tornando al codice io credo che il problema sia altrove, ovvero qui in questa parte di codice:

if(vT.element().equals(vS.element()))
			result = true;
		else
			return false;

quando vengono confrontati gli elementi dei due nodi visitati, se non sono uguali deve ritornare false e abbandonare l'esecuzione. Ma a quanto pare ciò non succede. Credo sia questo il problema, tu che ne dici?

[sottovento]

Originariamente inviato da marcoeanna

Ciao sottovento, prima di tutto grazie per esserti interessato a questo problema tornando al codice io credo che il problema sia altrove, ovvero qui in questa parte di codice:

if(vT.element().equals(vS.element()))
			result = true;
		else
			return false;

quando vengono confrontati gli elementi dei due nodi visitati, se non sono uguali deve ritornare false e abbandonare l'esecuzione. Ma a quanto pare ciò non succede. Credo sia questo il problema, tu che ne dici?

Perche' non dovrebbe succedere? Ritieni che ci sia un problema nella comparazione?

L'algoritmo che hai impostato fa dei check successivi e ad ogni fallimento ritorna false, terminando l'algoritmo stesso. mettere result a true non ha un gran senso, potresti eliminare quella parte (invertendo l'if e ritornando false nel caso i due elementi non siano uguali).

Settare result a true conferma quanto ho scritto prima:

		if(T.hasLeft(vT) && S.hasLeft(vS))
			result = uguali(T, T.left(vT), S, S.left(vS), result);


		if(T.hasRight(vT) && S.hasRight(vS))
			result = uguali(T, T.right(vT), S, S.right(vS), result);

Il primo if con la chiamata ad uguali() non sortisce nessun effetto nel tuo codice, e' come se non esistesse. Fra l'altro e' anche quello che hai scritto tu descrivendo il problema

[marcoeanna]

L'algoritmo che hai impostato fa dei check successivi e ad ogni fallimento ritorna false, terminando l'algoritmo stesso. mettere result a true non ha un gran senso, potresti eliminare quella parte (invertendo l'if e ritornando false nel caso i due elementi non siano uguali).

Settare result a true conferma quanto ho scritto prima:

if(T.hasLeft(vT) && S.hasLeft(vS))
			result = uguali(T, T.left(vT), S, S.left(vS), result);


		if(T.hasRight(vT) && S.hasRight(vS))
			result = uguali(T, T.right(vT), S, S.right(vS), result);

Il primo if con la chiamata ad uguali() non sortisce nessun effetto nel tuo codice, e' come se non esistesse. Fra l'altro e' anche quello che hai scritto tu descrivendo il problema

scusami non ho capito bene quello che hai detto, mi potresti far vedere come modificheresti quella parte direttamente nel codice per favore?

[sottovento]

Scusa il ritardo nella risposta, sono impegnato in un trasloco dall'altra parte della citta'.

Farei due modifiche:
1 - nel metodo uguali() rimuoverei l'ultimo parametro (i.e. passi il result ma se ci fa caso potresti anche farne a meno;

2 - il secondo confronto (sulle parti destre dell'albero) lo farei solo se il confronto sulle parti sinistre dice che sono uguali. In tal modo tengo in considerazione il risultato del confronto a sx.
Per esempio:

if(T.hasLeft(vT) && S.hasLeft(vS))
     result = uguali(T, T.left(vT), S, S.left(vS));


if(result && T.hasRight(vT) && S.hasRight(vS))
     result = uguali(T, T.right(vT), S, S.right(vS));

[marcoeanna]

Originariamente inviato da sottovento

Scusa il ritardo nella risposta, sono impegnato in un trasloco dall'altra parte della citta'.

Farei due modifiche:
1 - nel metodo uguali() rimuoverei l'ultimo parametro (i.e. passi il result ma se ci fa caso potresti anche farne a meno;

2 - il secondo confronto (sulle parti destre dell'albero) lo farei solo se il confronto sulle parti sinistre dice che sono uguali. In tal modo tengo in considerazione il risultato del confronto a sx.
Per esempio:

if(T.hasLeft(vT) && S.hasLeft(vS))
     result = uguali(T, T.left(vT), S, S.left(vS));


if(result && T.hasRight(vT) && S.hasRight(vS))
     result = uguali(T, T.right(vT), S, S.right(vS));

grazie mille per avermi risolto questo problema, effettivamente facendo così è più sensata la cosa e funziona anche grazie ancora sei stato gentilissimo e buon trasloco.
spero di rileggerti le prossime volte se ce ne sarà bisogno