|
|
|
|
Strumenti |
27-06-2017, 11:38 | #1 |
Junior Member
Iscritto dal: Jun 2017
Messaggi: 6
|
[JAVA] Verificare se due alberi binari sono uguali
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? Codice:
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; } } |
27-06-2017, 14:20 | #2 |
Senior Member
Iscritto dal: Nov 2005
Città: Texas
Messaggi: 1722
|
Sarebbe interessante provarlo; puoi postare le parti mancanti? (vale a dire i package binaryTree e position?)
__________________
In God we trust; all others bring data |
27-06-2017, 14:40 | #3 |
Junior Member
Iscritto dal: Jun 2017
Messaggi: 6
|
ecco il pacchetto binaryTree
|
27-06-2017, 14:41 | #4 |
Junior Member
Iscritto dal: Jun 2017
Messaggi: 6
|
ecco il pacchetto position
|
27-06-2017, 15:26 | #5 |
Senior Member
Iscritto dal: Nov 2005
Città: Texas
Messaggi: 1722
|
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): Codice:
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);
__________________
In God we trust; all others bring data |
27-06-2017, 16:13 | #6 | |
Junior Member
Iscritto dal: Jun 2017
Messaggi: 6
|
Quote:
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: Codice:
if(vT.element().equals(vS.element())) result = true; else return false; |
|
27-06-2017, 16:31 | #7 | |
Senior Member
Iscritto dal: Nov 2005
Città: Texas
Messaggi: 1722
|
Quote:
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: Codice:
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);
__________________
In God we trust; all others bring data |
|
28-06-2017, 09:03 | #8 | |
Junior Member
Iscritto dal: Jun 2017
Messaggi: 6
|
Quote:
|
|
29-06-2017, 15:35 | #9 |
Senior Member
Iscritto dal: Nov 2005
Città: Texas
Messaggi: 1722
|
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: Codice:
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));
__________________
In God we trust; all others bring data |
29-06-2017, 16:07 | #10 | |
Junior Member
Iscritto dal: Jun 2017
Messaggi: 6
|
Quote:
spero di rileggerti le prossime volte se ce ne sarà bisogno |
|
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 12:13.