[java] alberi isomorfi

[tonionto]

Ciao,ho un problema con una classe di java..devo implementare un algoritmo che mi verifichi se 2 alberi che do in ingresso sono isomorfi,ma non so più da che parte prendere..qualche idea??

io pensavo con un algoritmo ricorsivo,ma mi sono incasinato e non mi capisco più..

[andbin]

Originariamente inviato da tonionto
mi verifichi se 2 alberi che do in ingresso sono isomorfi

Andando per ragionamento, sono "isomorfi" se hanno la stessa identica "struttura" (forma) cioè se due nodi di uno e dell'altro albero allo stesso livello hanno lo stesso numero di figli. È così?? Spero di averlo detto bene e giusto.

Originariamente inviato da tonionto
io pensavo con un algoritmo ricorsivo

Sì. appunto ricorsivo. Poi comunque bisogna vedere a livello pratico se l'albero è binario (e hai figli es. "left" e "right") o n-ario.

Comunque è semplice: prendi un nodo dell'uno e dell'altro albero. Hanno lo stesso numero di figli? Allora "entri" in ogni figlio per entrambi e la cosa si ripete in ricorsione.

[tonionto]

I due alberi che ho in ingresso sono 2 alberi binari..diciamo che pensavo di fare un algoritmo del tipo:
"""""

boolean isomorfo(Node t1, Node t2) {
return (t1 == NULL && t2 == NULL) || (t1 != NULL && t2 != NULL) && ( isomorfo(t1.left(),t2.left()) && isomorfo(t1.right(),t2.right()) );
}

"""""
potrebbe essere??il problema mio è il resto del programma,come passare a "isomorfo" i dua alberi che ho in ingresso..diciamo che è un pò che non bazzico con java,e mi son arrugginito..

grazie mille del'aiuto..

[andbin]

Originariamente inviato da tonionto
boolean isomorfo(Node t1, Node t2) {
return (t1 == NULL && t2 == NULL) || (t1 != NULL && t2 != NULL) && ( isomorfo(t1.left(),t2.left()) && isomorfo(t1.right(),t2.right()) );
}

Direi proprio di no ... almeno a vederlo così. Non fai tutti i possibili casi.

Originariamente inviato da tonionto
come passare a "isomorfo" i dua alberi che ho in ingresso..

Non so per l'albero in sé hai un tipo apposito es. Albero che magari ha un getRadice() (che ritorna il Node radice ... mi pare intuitivo) oppure se il tuo albero è proprio solo un albero di nodi di cui tu tieni direttamente il Node radice.
Ma sicuramente hai capito ... cambia poco!!! No?

[tonionto]

Non fa tutti i casi?sennò come potrei fare?scusami,ma con gli algoritmi ricorsivi faccio sempre casino..

[andbin]

Originariamente inviato da tonionto
Non fa tutti i casi?

Non l'avevo guardato approfonditamente io .... no, mi pare corretto.