Ciao, per farti riconoscere devi fare il login. Non ti sei ancora iscritto? Che aspetti, registrati adesso!
Scritto da Emilian Bogdan a.k.a. hanterkyra il 09-12-2009 ore 21:00
Dato un albero binario proprio, scrivere un programma che genera la visita per livelli dell'albero.
potreste darmi delle drite su come initiare perche sono nuovoi del mestiere (per dire)
grazie mile
Intervento di Filippo P a.k.a. lieutenant del 11-12-2009 ore 21:22, Treviglio (BG)
Cavaliere
(143 interventi)
Iscritto il 11-01-2006
Cercando in internet sono sicuro che si possano trovare molti modelli di alberi e nodi (trees, nodes).
Java è un linguaggio a oggetti, per cui di sicuro ti conviene modellare un oggetto "nodo" con i suoi metodi.
In un albero binario, ogni nodo può avere un padre (l'unico nodo senza padre è la radice) e due figli (essendo un albero binario...). Inoltre, dato che devi progettare un algoritmo di visita "a livelli" può tornarti utile che ogni nodo abbia un metodo che restituisca il livello attuale del nodo.
Inoltre creerei un oggetto "livelli" capace di contenere un elenco di liste, ciascuna delle quali ospiterà i riferimenti ai soli nodi di un determinato livello. L'oggetto "livelli" dovrebbe essere statico o comunque istanziato da un oggetto che sia lo stesso atto a generare i nuovi nodi. Dovranno poi essere i nodi, all'atto dell'impostazione del padre, ad inserirsi nella lista giusta.
Quindi un oggetto "nodo" con metodi per:
- recuperare il "nodo" padre
- impostare il "nodo" padre
- recuperare il "nodo" figlio sinistro
- impostare il "nodo" figlio sinistro
- recuperare il "nodo" figlio destro
- impostare il "nodo" figlio destro
- recuperare il "nodo" fratello (nodo con lo stesso padre)
- recuperare il numero di livello attuale (calcolato come il livello del padre + 1, oppure 0 se non c'è un padre)
- recuperare un intero che definisca, per quel nodo, l'esatta posizione all'interno dell'albero (funzionerà su alberi con massimo 32 livelli, può essere utile per eventuali visite per livello ordinate da sinistra a destra o viceversa... meriterebbe qualche spiegazione in più ma penso anche che vada oltre gli scopi dell'esercitazione)
Un oggetto "factory" con metodi per:
- istanziare un nuovo nodo senza padre
- istanziare un nuovo nodo con padre
Un oggetto "livelli" con metodi per:
- aggiungere un "nodo" a uno specifico livello
- recuperare l'elenco dei nodi a uno specifico livello
- recuperare il livello massimo
L'oggetto "factory" sarà responsabile di passare agli oggetti "nodo" con padre che crea un'istanza di oggetto "livelli" (sempre la stessa, stabilita all'atto della creazione di un nodo senza padre). Gli oggetti "nodo" saranno responsabili di invocare i metodi dell'oggetto "livelli" a loro associato ed inserirsi nonchè di invocare il metodo per impostare il padre quando viene aggiunto un figlio (in questo modo si evita anche di creare grafi anzichè alberi).
Per visitare l'albero "per profondità" potrai visitare con un algoritmo ricorsivo (o un iterativo equivalente) tutti i nodi a partire dal padre.
Per visitare l'albero "per livelli", potrai utilizzare l'oggetto "livelli" in una normale funzione iterativa.
Java è un linguaggio a oggetti, per cui di sicuro ti conviene modellare un oggetto "nodo" con i suoi metodi.
In un albero binario, ogni nodo può avere un padre (l'unico nodo senza padre è la radice) e due figli (essendo un albero binario...). Inoltre, dato che devi progettare un algoritmo di visita "a livelli" può tornarti utile che ogni nodo abbia un metodo che restituisca il livello attuale del nodo.
Inoltre creerei un oggetto "livelli" capace di contenere un elenco di liste, ciascuna delle quali ospiterà i riferimenti ai soli nodi di un determinato livello. L'oggetto "livelli" dovrebbe essere statico o comunque istanziato da un oggetto che sia lo stesso atto a generare i nuovi nodi. Dovranno poi essere i nodi, all'atto dell'impostazione del padre, ad inserirsi nella lista giusta.
Quindi un oggetto "nodo" con metodi per:
- recuperare il "nodo" padre
- impostare il "nodo" padre
- recuperare il "nodo" figlio sinistro
- impostare il "nodo" figlio sinistro
- recuperare il "nodo" figlio destro
- impostare il "nodo" figlio destro
- recuperare il "nodo" fratello (nodo con lo stesso padre)
- recuperare il numero di livello attuale (calcolato come il livello del padre + 1, oppure 0 se non c'è un padre)
- recuperare un intero che definisca, per quel nodo, l'esatta posizione all'interno dell'albero (funzionerà su alberi con massimo 32 livelli, può essere utile per eventuali visite per livello ordinate da sinistra a destra o viceversa... meriterebbe qualche spiegazione in più ma penso anche che vada oltre gli scopi dell'esercitazione)
Un oggetto "factory" con metodi per:
- istanziare un nuovo nodo senza padre
- istanziare un nuovo nodo con padre
Un oggetto "livelli" con metodi per:
- aggiungere un "nodo" a uno specifico livello
- recuperare l'elenco dei nodi a uno specifico livello
- recuperare il livello massimo
L'oggetto "factory" sarà responsabile di passare agli oggetti "nodo" con padre che crea un'istanza di oggetto "livelli" (sempre la stessa, stabilita all'atto della creazione di un nodo senza padre). Gli oggetti "nodo" saranno responsabili di invocare i metodi dell'oggetto "livelli" a loro associato ed inserirsi nonchè di invocare il metodo per impostare il padre quando viene aggiunto un figlio (in questo modo si evita anche di creare grafi anzichè alberi).
Per visitare l'albero "per profondità" potrai visitare con un algoritmo ricorsivo (o un iterativo equivalente) tutti i nodi a partire dal padre.
Per visitare l'albero "per livelli", potrai utilizzare l'oggetto "livelli" in una normale funzione iterativa.
Intervento di Emilian Bogdan a.k.a. hanterkyra del 13-12-2009 ore 19:38, Treviso (TV)
Plebeo
(1 intervento)
Iscritto il 09-12-2009
grazie mile mi 6 statto di grande aiuto
Copyright Programmazione.it™ 1999-2013. Alcuni diritti riservati. Testata giornalistica iscritta col n. 569 presso il Tribunale di Milano in data 14/10/2002. Pagina generata in 0.262 secondi.