Problema con albero binario..!!

[stratosfe]

Devo implementare un metodo booleano che passandogli due Alberi binari ( A e B) come parametri, deve verificare se gli elemeni contenuti nell'albero A sono contenuti anke nell Albero B..! Ho a disposizione tre interfacce, int val(), AlberoBinario sin(), AlberoBinario des(); Ho provato a memorizzare i valori dell albero A e dell albero B in due LinkedList e poi scorrerle kon l'iteratore ma nn so kome fare a memorizzare gli elementi x konfrontarli tra di loro..!! Chi mi aiuta??:muro: :muro:

[wingman87]

Devi specificare il linguaggio nel titolo

[stratosfe]

Linguaggio java..!

[wingman87]

L'avevo immaginato, ma io mi riferivo a questo: LINK (http://www.hwupgrade.it/forum/showthread.php?t=1649196)

Ad ogni modo non ti serve scorrere entrambe le liste, basta scorrerne una e richiamare sull'altra questo metodo: LINK (http://java.sun.com/j2se/1.5.0/docs/api/java/util/LinkedList.html#contains(java.lang.Object))

[stratosfe]

ok! Grazie! quindi ad ogni elemento ke scorro sulla prima lista rikiamo il metodo contains x vedere se è presente nell'altra lista..! Un ultima domanda, come visita degli alberi posso fare l anticipata?

[gugoXX]

Al posto che trasformare l'albero A in una lista, la cui Contains viene risolta in O(N), perche' non fai una bella Contains sull'albero, la cui complessita' e' O(Log N).
Cosi' fai anche contento il professore, altrimenti perche' avrebbe detto: Avete 2 alberi binari? Avrebbe potuto dire: Avete 2 liste... (sempre se si tratta di un esercizio)

Se pero' dovessi proprio trasformarlo in qualcosa perche' l'albero non mi piace, invece della lista io sceglierei una hastable, la cui complessita' della contains e' O(1).

[stratosfe]

si infatti è un esercizio..! Dice anke di usare metodi di appoggio se sono necessari..! quindi lascio gli alberi in quel modo e li scorro kon la visita anticipata..? Ma quest esercizio può essere fatto in modo ricorsivo?

[wingman87]

Al posto che trasformare l'albero A in una lista, la cui Contains viene risolta in O(N), perche' non fai una bella Contains sull'albero, la cui complessita' e' O(Log N).
Non vorrei dire caxxate, tu ne sai molto più di me, ma quello che hai detto non vale solo nel caso di un albero binario ordinato?

si infatti è un esercizio..! Dice anke di usare metodi di appoggio se sono necessari..! quindi lascio gli alberi in quel modo e li scorro kon la visita anticipata..? Ma quest esercizio può essere fatto in modo ricorsivo?
Puoi scrivere un tuo personale contains e definirlo nell'albero (come mi sembra abbia suggerito gugoXX). Poi puoi visitare l'albero come vuoi, certamente con la ricorsione è più comodo.

[stratosfe]

No contains posso fare anke a meno di ridefinirlo, basta fare la kiamata..! ricorsivamente posso fare solo la visita, altro nn lo posso fare..! L elemento nn deve essere nella stessa posizione x forza, può essere x esempio ke sia nell albero A in prima posizione e nell albero B in ultima posizione...!

[gugoXX]

Non vorrei dire caxxate, tu ne sai molto più di me, ma quello che hai detto non vale solo nel caso di un albero binario ordinato?
hai perfettamente ragione. Me l'ero immaginato ordinato, dato che solitamente gli esercizi vengono fuori per gli alberi red-black o quelli ordinati.
Se non e' ordinato e' perfettamente inutile come albero, tanto vale trasformarlo in lista (o meglio ancora la hastable) per questo problema
Se invece fosse ordinato direi invece meglio la visita ricorsiva direttamente sull'albero

[wingman87]

No contains posso fare anke a meno di ridefinirlo, basta fare la kiamata..!
Veramente io parlavo di definire un metodo contains all'interno della classe Albero, una cosa di questo tipo:

class Albero{
public boolean contains(TipoOggetto elem){
...
}
}
In questo modo mentre fai la visita ricorsiva ti porti dietro un riferimento al secondo albero e per ogni elemento richiami il contains. Se ti viene restituito false termini la visita e ritorni false, altrimenti vai avanti fino alla fine di tutta la visita e torni true.

[cionci]

Thread chiuso
|
V