Stampare Nodi Albero Binario

[soeca]

Ragazzi sto studiando gli alberi binari di ricerca e sto affrontando un esercizio dove: dato un albero, devo stamparmi tutti i nodi di ogni livello!!Mi spiego meglio: QUI trovate un esempio di albero binario completo...ciò che voglio fare è ottenere in output: 8,4,12,2,6,10,14,1,3,5,7,9,11,13,15 .... non sto' riuscendo a capire come affrontare l'esercizio....io ho scritto del codice per tentare di risolvere il problema però non funziona per niente....ecco ciò che ho scritto:

public void leggi()
 _ { _ _
 _ _ _ StringBuilder str=new StringBuilder(2000);
 _ _ _ Nodo tmp=root;
 _ _ _ str.append(tmp.getNome()+"\n"+tmp.getLeft().getNome()+"\n");
 _ _ _ tmp=tmp.getLeft();
 _ _ _ while(true)
 _ _ _ {
 _ _ _ _ _ if(tmp.getLeft()!=null && tmp.getRight()!=null) //se i figli esistono entrambi
 _ _ _ _ _ {
 _ _ _ _ _ _ _ str.append(tmp.getLeft().getNome()+"\n"+tmp.getRight().getNome()+"\n");
 _ _ _ _ _ _ _ tmp=tmp.getLeft();
 _ _ _ _ _ }
 _ _ _ _ _ else if(tmp.getLeft()!=null && tmp.getRight()==null)//se trovo il figlio sinistro
 _ _ _ _ _ {
 _ _ _ _ _ _ _ str.append(tmp.getLeft().getNome());
 _ _ _ _ _ _ _ tmp=tmp.getLeft();
 _ _ _ _ _ }
 _ _ _ _ _ else if(tmp.getLeft()==null && tmp.getRight()!=null) //se trovo il figlio destro e non il sinistro
 _ _ _ _ _ {
 _ _ _ _ _ _ _ str.append(tmp.getRight().getNome());
 _ _ _ _ _ _ _ tmp=tmp.getLeft();
 _ _ _ _ _ }
 _ _ _ _ _ else if(tmp.getLeft()==null && tmp.getRight()==null) //se non c'è alcun figlio finisci il ciclo
 _ _ _ _ _ {
 _ _ _ _ _ _ _ return ;
 _ _ _ _ _ }
 _ _ _ }
 _ _}

ancora non ho avviato il programma però svolgendo su carta quanto ho scritto....praticamente ho notato che stamperebbe: 8,4,2,6,1,3 che ovviamente è sbagliato....non sto' proprio riuscendo a trovare una soluzione(mi scuso se magari per alcuni il mio problema è banale però ammetto di essere abbastanza neofita nel campo della programmazione!!) Grazie a tutti!

[unomichisiada]

Originariamente inviato da soeca
Ragazzi sto studiando gli alberi binari di ricerca e sto affrontando un esercizio dove: dato un albero, devo stamparmi tutti i nodi di ogni livello!!Mi spiego meglio: QUI trovate un esempio di albero binario completo...ciò che voglio fare è ottenere in output: 8,4,12,2,6,10,14,1,3,5,7,9,11,13,15 .... non sto' riuscendo a capire come affrontare l'esercizio....io ho scritto del codice per tentare di risolvere il problema però non funziona per niente....ecco ciò che ho scritto:

public void leggi()
 _ { _ _
 _ _ _ StringBuilder str=new StringBuilder(2000);
 _ _ _ Nodo tmp=root;
 _ _ _ str.append(tmp.getNome()+"\n"+tmp.getLeft().getNome()+"\n");
 _ _ _ tmp=tmp.getLeft();
 _ _ _ while(true)
 _ _ _ {
 _ _ _ _ _ if(tmp.getLeft()!=null && tmp.getRight()!=null) //se i figli esistono entrambi
 _ _ _ _ _ {
 _ _ _ _ _ _ _ str.append(tmp.getLeft().getNome()+"\n"+tmp.getRight().getNome()+"\n");
 _ _ _ _ _ _ _ tmp=tmp.getLeft();
 _ _ _ _ _ }
 _ _ _ _ _ else if(tmp.getLeft()!=null && tmp.getRight()==null)//se trovo il figlio sinistro
 _ _ _ _ _ {
 _ _ _ _ _ _ _ str.append(tmp.getLeft().getNome());
 _ _ _ _ _ _ _ tmp=tmp.getLeft();
 _ _ _ _ _ }
 _ _ _ _ _ else if(tmp.getLeft()==null && tmp.getRight()!=null) //se trovo il figlio destro e non il sinistro
 _ _ _ _ _ {
 _ _ _ _ _ _ _ str.append(tmp.getRight().getNome());
 _ _ _ _ _ _ _ tmp=tmp.getLeft();
 _ _ _ _ _ }
 _ _ _ _ _ else if(tmp.getLeft()==null && tmp.getRight()==null) //se non c'è alcun figlio finisci il ciclo
 _ _ _ _ _ {
 _ _ _ _ _ _ _ return ;
 _ _ _ _ _ }
 _ _ _ }
 _ _}

ancora non ho avviato il programma però svolgendo su carta quanto ho scritto....praticamente ho notato che stamperebbe: 8,4,2,6,1,3 che ovviamente è sbagliato....non sto' proprio riuscendo a trovare una soluzione(mi scuso se magari per alcuni il mio problema è banale però ammetto di essere abbastanza neofita nel campo della programmazione!!) Grazie a tutti!

Per fare una visita iterativa per livello devi usare un'altra struttuara dati d'appoggio, in genere si usa una coda. Ciao

[soeca]

mmmm.....la coda dovrei implementarla usando degli array ma la cosa FONDAMENTALE (ma che per distrazione non ho messo ieri!) di questo esercizio è che non posso usare array e verrà valutata inoltre la velocità di esecuzione finale...usando un'altra struttura d'appoggio di tipo coda non rischio di perdere del tempo e peggiorare la complessità del mio programma??

[VincenzoTheBest]

Originariamente inviato da soeca
mmmm.....la coda dovrei implementarla usando degli array ma la cosa FONDAMENTALE (ma che per distrazione non ho messo ieri!) di questo esercizio è che non posso usare array e verrà valutata inoltre la velocità di esecuzione finale...usando un'altra struttura d'appoggio di tipo coda non rischio di perdere del tempo e peggiorare la complessità del mio programma??

Puoi usare una istanza di LinkedList. Tale classe offre la possibilità di usare le sue istanze (anche) come se fossero code e/o pile.

Per quanto riguarda la complessità, tutto dipende da come imposti l'algoritmo.

[unomichisiada]

Originariamente inviato da soeca
mmmm.....la coda dovrei implementarla usando degli array ma la cosa FONDAMENTALE (ma che per distrazione non ho messo ieri!) di questo esercizio è che non posso usare array e verrà valutata inoltre la velocità di esecuzione finale...usando un'altra struttura d'appoggio di tipo coda non rischio di perdere del tempo e peggiorare la complessità del mio programma??

La coda la puoi implementare tu con una lista oppure usare qualcosa già pronto come ti è stato suggerito. In ogni modo per una versione iterativa non ci sono alternative, o usi una coda o usi uno stack (nel qual caso la visita sarà in senso inverso rispetto ai livelli). Teoricamente è possibile anche farne una versione ricorsiva (che usa quindi lo stack di sistema) ma non è banale, anche io ci dovrei pensare un po su.

[unomichisiada]

Originariamente inviato da unomichisiada
La coda la puoi implementare tu con una lista oppure usare qualcosa già pronto come ti è stato suggerito. In ogni modo per una versione iterativa non ci sono alternative, o usi una coda o usi uno stack (nel qual caso la visita sarà in senso inverso rispetto ai livelli). Teoricamente è possibile anche farne una versione ricorsiva (che usa quindi lo stack di sistema) ma non è banale, anche io ci dovrei pensare un po su.

Mi correggo, ricordavo male, una visita level order utilizzando uno stack o la ricorsione sembra non essere fattibile o se lo è la difficoltà è notevole, non ci perderei del tempo, resta solo la coda e l'iterazione.