[JAVA] Algoritmo albero binario..!

[stratosfe]

Ragazzi ho provato a buttar giù un pò di codice x il metodo di visita dell albero ma nn riesco ad implementare il metodo ke ricevendo due Alberi binari restituisce true se tutti gli elementi dell'albero A sono presenti nell'Albero B...! potete dare un okkiata e darmi qualke consiglio con kodice?

Metodo di visita dell'Albero:
private void visita(AlberoB A,int livello,int i) {
if (i==livello) {
System.out.println(a.val());
return;
}
i++;
if (a.sin()!=null) {
visita(a.sin(),livello,i);
if (a.des()!=null) {
visita(a.des(),livello,i);
}
}

[Albi89]

Penso che la procedura sia abbastanza semplice.
Partendo da un algoritmo per la visita ordinata, per ogni elemento esegui una ricerca con una funzione che ritorna true se l'elemento è presente nel secondo albero.
Se non viene mai riportato false, la tua funzione ritornerà true, altrimenti al primo false saprai che il predicato originario, ossia la presenza nel secondo albero di tutti gli elementi del primo, è senza dubbio falso ;)

[stratosfe]

e kome faccio??! Il primo albero lo devo mettere in una LinkedList e scorrerlo kon un iteratore?? La mia difficoltà è questa..! nn puoi buttare un pò di codice su questa funzione di verifica?

[Albi89]

e kome faccio??! Il primo albero lo devo mettere in una LinkedList e scorrerlo kon un iteratore?? La mia difficoltà è questa..! nn puoi buttare un pò di codice su questa funzione di verifica?

Non conosco affatto il linguaggio Java, ma cercherò comunque di esprimere quello che è l'approccio che userei...

Anzitutto definire una struttura nodo, composta da un elemento, un puntatore al nodo di sinistra e un puntatore al nodo di destra (ovviamente nulli se non sono presenti nodi discendenti).

Poi, una funzione booleana in_albero che accetta come parametro un puntatore a struttura nodo: se il tuo albero è ordinato la funzione deve soltanto scorrere l'albero "svoltando" opportunamente a destra e a sinistra: quando e se incontra un puntatore nullo, significa che l'elemento non è presente.

Detto ciò, la nostra funzione di confronto deve semplicemente essere un ritocco a una classica funzione di visita ordinata, solitamente strutturata in maniera ricorsiva del tipo "Stampa a sinistra, mostra a schermo elemento, stampa a destra", dove stampa a... significa richiamare la funzione passando come parametro il puntatore al nodo di sinistra/destra.
La funzione opportunamento modificata accetta come parametro anche un secondo nodo principale e, al posto del "mostra a schermo elemento", esegue un in_albero (la funzione di ricerca di prima) passando come elemento l'elemento corrente del primo albero, e come albero il secondo albero in cui vogliamo verificare la presenza dell'elemento.

Penso che, conoscendo il linguaggio sicuramente meglio di me, non dovresti avere problemi a buttare giù il codice che ti serve ;)

[stratosfe]

Ok grazie mille!!! x fare questo metodo ho a disposizione le interfaccie int val() ke restituisce la radice dell albero; Albero sin() ke restituisce il sottoalbero di sinistra e Albero des(); gli alberi nn sono ordinati kmq..! Molte grazie..!! vediamo se riesko a farlo girare..!!

[stratosfe]

Un ultima kosa!! La struttura Nodo la posso eliminare visto ke l esercizio mi da già quei metodi dell interfaccia ke ti ho scritto prima?

[wingman87]

Ma il testo dell'esercizio qual è? Da qualche parte la classe Nodo dovrebbe essere definita (penso sia definita nell'esercizio).

[stratosfe]

Ekko la traccia :
Si consideri la seguente interfaccia che descrive alberi binari in cui la parte
informativa di ogni nodo sia un intero.
public interface AlberoBinario{
int val();
AlberoBinario sin();
AlberoBinario des();
}
Implementare il metodo
boolean maggiore(AlberoBinario a, AlberoBinario b);
che restituisce vero se e solo se tutti i valori contenuti nell’albero a sono contenuti
anche nell’albero b. (si ricorda che si possono implementare tutti i metodi di
appoggio che si ritiene utili per l’implementazione del metodo maggiore.

[wingman87]

Mmm quindi tu sai che un'implementazione di un albero binario ha sicuramente quei metodi e tu, sempre in quella implementazione, devi aggiungere il metodo maggiore. Giusto?
In quel caso puoi anche non tenere conto dell'esistenza dei nodi e fare tutto con quello che ti è stato fornito. Solo una cosa, visto che tutte le operazioni che dovrai eseguire nel metodo le farai sui due parametri puoi anche dichiarare il metodo static.

[stratosfe]

Si solo con quello ke mi è stato fornito..! Guarda io ti scrivo il codice ke ho generato io solo ke mi fa il confronto tra gli elementi dei due alberi nelle stesse posizioni..! io lo dovrei fare anke x posizioni diverse e nn mi viene..!! tu mi sai aiutare? intanto ti scrivo il codice :

static boolean maggiore(AlberoBinario a, AlberoBinario b) {
if (a!=null&&b!=null)
return true;
if (a.val()==b.val())
return true;
return maggiore(a.destro(),b.destro()) && maggiore(a.sinistro(),b.sinistro());
}

[sottovento]

Si solo con quello ke mi è stato fornito..! Guarda io ti scrivo il codice ke ho generato io solo ke mi fa il confronto tra gli elementi dei due alberi nelle stesse posizioni..! io lo dovrei fare anke x posizioni diverse e nn mi viene..!! tu mi sai aiutare? intanto ti scrivo il codice :

static boolean maggiore(AlberoBinario a, AlberoBinario b) {
if (a!=null&&b!=null)
return true;
if (a.val()==b.val())
return true;
return maggiore(a.destro(),b.destro()) && maggiore(a.sinistro(),b.sinistro());
}

Se posso permettermi... segui il consiglio che ti e' stato dato, sia dal testo sia da qualcun altro, qui nel forum: spezza il problema.
1 - scrivi una funzione che controlla se un dato elemento e' presente in un albero binario;
2 - utilizza la funzione precedente, scandendo tutti gli elementi dell'albero di partenza, per vedere se sono presenti in quello di arrivo. Se non ne trovi almeno uno, ritorni false altrimenti true.

Le due funzioni, cosi' separate, sono semplicissime da realizzare

[stratosfe]

Ma per vedere se l'elemento è presente in un albero come posso fare?? Devo passare uno dei due alberi ad una Lista?

[sottovento]

Ma per vedere se l'elemento è presente in un albero come posso fare?? Devo passare uno dei due alberi ad una Lista?

No, dai!

Scrivi un metodo chiamato
boolean isNodeInTree (int v, AlberoBinario tree)

il quale fa una ricerca dell'elemento v nell'albero tree.
La ricerca e' semplicemente una visita all'albero. Immagino che ti abbiano gia' spiegato tanti algoritmi per la visita di un albero. Usa quello che ti piace di piu' oppure, se l'albero e' un albero binario di ricerca, puoi sfruttare la ricerca dicotomica ed essere piu' veloce (il tuo testo non specifica se sei in questa condizione).

[stratosfe]

No nnè di ricerca..!! Posso usare la visita anticipata quindi..! la funzione ke mi hai scritto tu riceve come parametri l'intero v ke dovrebbe essere l'elemento di uno dei due alberi, giusto? ma se è kosi come faccio a passare l'intero se ho un albero?

[stratosfe]

La funzione isNodeTree l ho fatta kosi..

boolean isNodeTree (int v,AlberoBinario tree) {
if (tree==null)
return false;
if (tree.val()==v)
return true;
return isNodeTree(tree.destro(),v)|| isNodeTree(tree.sinistro(),v);

è giusto?

[wingman87]

La funzione isNodeTree l ho fatta kosi..

boolean isNodeTree (int v,AlberoBinario tree) {
if (tree==null)
return false;
if (tree.val()==v)
return true;
return isNodeTree(tree.destro(),v)|| isNodeTree(tree.sinistro(),v);

è giusto?
Sì è giusto. Hai fatto però un errore alla fine quando fai la chiamata ricorsiva, hai messo i parametri al contrario (ma te l'avrebbe detto anche il compilatore).
Anche questo metodo lo puoi dichiarare static.

[stratosfe]

Ok e fatto questo metodo ora come faccio a fare il metodo maggiore ke alla fine è quello ke mi serve? static boolean maggiore(AlberoBinario A,AlberoBinario B) {..} ..!
Devo fare la visita?

[wingman87]

Fai come ti hanno già detto: fai una visita di un albero (anticipata, posticipata... non importa) per ogni nodo che stai visitando richiami isNodeTree sull'altro albero, se questo torna false devi tornare false, altrimenti continui la visita. Se arrivi alla fine della visita torni true.

[stratosfe]

Quindi finendo st esercizio sarebbe kosi..!
static boolean presente (AlberoB albero,int v) {
if(albero==null)
return false;
if(albero.val()==v)
return true;
return presente(albero.destro(),v) || presente (albero.sinistro(),v);
}

static boolean maggiore (AlberoB A,AlberoB B) {
if (A==null && B==null)
return true;
return presente(A.sinistro(),B) || presente (A.destro(),B) || presente(A.val(),B);
return true;
}

è giusto? se nn lo è dove sbaglio?

[wingman87]

static boolean maggiore (AlberoB A,AlberoB B) {
if (A==null && B==null)
return true;
return presente(A.sinistro(),B) || presente (A.destro(),B) || presente(A.val(),B);
return true;
}

è giusto? se nn lo è dove sbaglio?
Usa il tag CODE per favore.
Questo codice non ha senso perché:
1) Dov'è che fai la visita?
2) L'ultimo return che hai messo è irraggiungibile
3) A presente come secondo parametro devi passare un int, non un AlberoB
4) Hai provato a compilarlo? Avresti evitato i punti 2 e 3

[stratosfe]

Usa il tag CODE per favore.
Questo codice non ha senso perché:
1) Dov'è che fai la visita?
2) L'ultimo return che hai messo è irraggiungibile
3) A presente come secondo parametro devi passare un int, non un AlberoB
4) Hai provato a compilarlo? Avresti evitato i punti 2 e 3


static boolean maggiore (AlberoB A,AlberoB B) {
if (A==null && B==null)
return true;
visitaPosticipata(A.sinistro());
return presente(B,A.sinistro());
visitaPosticipata(A.destro());
return presente(B,A.destro());
return presente(B,A.val());
}

Kosi adesso funziona?

[wingman87]

static boolean maggiore (AlberoB A,AlberoB B) {
if (A==null && B==null)
return true;
visitaPosticipata(A.sinistro());
return presente(B,A.sinistro());
visitaPosticipata(A.destro());
return presente(B,A.destro());
return presente(B,A.val());
}

Kosi adesso funziona?
Usa il tag CODE per favore, vedi come diventa tutto più leggibile?
Tutte le istruzioni che ti ho evidenziato sono irraggiungibili perché sono preceduti da un return.
Ti do una mano con un po' di codice:

static boolean maggiore (AlberoB A,AlberoB B) {
if(A==null)
return true; //Se sono arrivato in fondo all'albero va bene quindi torno true
if(!XXX)
return false; //Qual è l'unico caso in cui torno false?
return XXX && XXX; //E qui c'è la chiamata ricorsiva
}

Tenta di capire cosa ci va al posto delle XXX

[stratosfe]

static boolean maggiore (AlberoB A,AlberoB B) {
if(A==null)
return true; //Se sono arrivato in fondo all'albero va bene quindi torno true
if(!presente(B,a.val())
return false; //Qual è l'unico caso in cui torno false?
return maggiore(A.sinistro(),B) && maggiore(A.destro(),B); //E qui c'è la chiamata ricorsiva
}

Va bene così?:doh: