Attraversamento del preordine binario dell'albero in Java
Questo è in realtà un albero binario. Un albero binario è un albero in cui ogni nodo ha al massimo due nodi per bambini. Se un nodo ha un solo nodo figlio, quel nodo dovrebbe essere fatto il nodo sinistro. Se ha entrambi i bambini, allora c'è un nodo sinistro e un nodo destro.
Vocabolario degli alberi
La spiegazione del traversario degli alberi viene eseguita usando il vocabolario degli alberi.
Nodo radice: Ogni nodo in un albero ha un genitore tranne il nodo radice.
Nodi fogliare: I nodi finali sono nodi fogliari. Un nodo foglia non ha un bambino.
Chiave: Questo è il valore di un nodo. Può essere un valore di tipo di dati primitivo o un carattere. Può anche essere un operatore, E.G., + ot - .
Livelli: Un albero è organizzato in livelli, con il nodo radicale al primo livello. I nodi possono essere immaginati a livelli orizzontali. L'albero di cui sopra ha quattro livelli.
Nodo genitore: Il nodo radice è l'unico nodo che non ha un genitore. Qualsiasi altro nodo ha un nodo genitore.
Nodi tra fratelli: I bambini di un particolare nodo sono nodi tra fratelli.
Sentiero: Un percorso è una stringa di nodi e i loro singoli rami.
Nodo antenato: Tutti i nodi più alti collegati a un figlio, incluso il genitore e il nodo radice, sono nodi antenati.
Nodo discendente: Tutti i nodi inferiori, collegati a un particolare nodo, fino alle foglie connesse, sono nodi discendenti. Il nodo in questione non fa parte dei nodi discendenti. Il nodo in questione non deve essere il nodo radice.
Sottosuolo: Un nodo più tutti i suoi discendenti, fino alle foglie correlate, formano una sottostruttura. Il nodo iniziale è incluso e non deve essere la radice; Altrimenti, sarebbe l'intero albero.
Grado: Il nodo di un albero binario può avere uno o due bambini. Se un nodo ha un figlio, si dice che la sua laurea sia. Se ha due figli, si dice che la sua laurea sia due.
Questo articolo spiega come attraversare un albero binario in modo pre-ordine, usando il linguaggio Java.
Contenuto dell'articolo
- Modello di attraversamento
- L'approccio di attraversamento illustrato
- Lezioni Java
- Il metodo principale ()
- Conclusione
Modello di attraversamento
Ordini
Il più piccolo sub-albero tipico di un albero binario è costituito da un nodo genitore e due nodi per bambini. I nodi dei bambini sono fratelli costituiti dal nodo figlio sinistro e dal nodo figlio destro. Un nodo figlio destro può essere assente.
Ordine prestabilito
Il nodo genitore viene visitato per primo con questo ordine, quindi il nodo sinistro e quindi il nodo destro. Se il nodo sinistro ha il suo sottosuolo, allora tutti i nodi del sottostruttura verranno visitati prima di visitare il nodo destro. Se il nodo giusto ha la sua sottostruttura, allora tutto il suo sottosuolo verrà visitato infine. Nel visitare una sottostruttura, lo schema pre-ordine di genitore-sinistra-destra viene seguito per ogni triangolo di tre nodi. Se un nodo ha un solo figlio, il che significa che non esiste un vero triangolo, l'unico bambino dovrebbe essere considerato il nodo sinistro mentre il nodo destro è assente.
POSTERDER
Il nodo sinistro viene visitato per primo con questo ordine, quindi il nodo destro e quindi il nodo genitore. Se il nodo sinistro ha il suo sottosuolo, allora tutti i nodi del sottostruttura verranno visitati prima di visitare il nodo destro. Se il nodo giusto ha la sua sottostruttura, allora tutto il suo sottosuolo verrà visitato in secondo luogo prima che il genitore venga visitato. Nel visitare una sottostruttura, lo schema post-ordine del genitore a sinistra-destra viene seguito per ogni triangolo di tre nodi.
Al fine
Il nodo sinistro viene visitato per primo con questo ordine, quindi il nodo genitore e quindi il nodo destro. Se il nodo sinistro ha il suo sottostruttura, allora tutti i nodi del sottostruttura verranno visitati prima di visitare il nodo genitore. Se il nodo giusto ha la sua sottostruttura, allora tutto il suo sottosuolo verrà visitato infine. Nel visitare una sottostruttura, lo schema in-ordine del parente di sinistra viene seguito per ogni triangolo di tre nodi.
In questo articolo, è illustrato solo lo schema di preordine.
Ricorsione o iterazione
Lo schema di preordine può essere implementato utilizzando la ricorsione o l'iterazione. In questo articolo, l'unica ricorsione è illustrata.
L'approccio di attraversamento illustrato
In questo articolo, vengono utilizzati lo schema di pre-ordine e la ricorsione. Verrà utilizzato il diagramma sopra. Il diagramma è stato ri-estarso qui per un facile riferimento:
In questa sezione, questo diagramma viene utilizzato per mostrare la sequenza di valori (lettere) che vengono visualizzati (accessibili), utilizzando lo schema di preordine e la ricorsione. Le lettere A, B, C, ecc., sono i valori (chiavi) dei diversi nodi.
L'accesso di preordine all'albero inizia dalla radice. Quindi A è l'accesso per primo. A ha due figli: B (a sinistra) e C (a destra). Il preordine è genitore-sinistra-destra. Quindi B si accede dopo. Se B non avesse mai avuto figli, allora sarebbe stato accessibile a C. Poiché B ha figli: D (a sinistra) ed E (a destra), il bambino sinistro deve essere accessibile dopo. Ricordiamo che il preordine è genitore-sinistra-destro. Dopo B, è stato accessibile al genitore, il figlio sinistro, D, è necessario accedere successivamente, in conformità con il genitore-leftcild-rightchild.
Il triangolo per il nodo genitore, B, è BDE. In questo triangolo, è stato appena accessibile il nodo genitore, seguito dal nodo del bambino sinistro. L'accesso a tutti i nodi del triangolo deve essere completato per primo. Quindi, il nodo successivo a cui accedere è il figlio giusto del nodo B, che è E.
Ora, il triangolo BDE è una sottostruttura, guidata dal nodo B. A questo punto, il nodo B e il suo triangolo sono completamente accessibili. Il nodo B è il figlio sinistro del nodo A. L'accesso del nodo B e della sua sottostruttura sono appena stati completati. Seguendo il genitore-sinistra-destra, dopo il figlio sinistro, è stato accessibile il nodo B, è necessario accedere al figlio destro del genitore A, c,.
Il triangolo che C conduce è CFG. C è il genitore, F è il bambino sinistro e G è il bambino giusto. Quindi, non appena è stato accessibile C, è necessario accedere a F secondo la regola del genitore-sinistra-destra. F ha anche un figlio, h. Quindi, non appena F è stato accessibile, il suo bambino sinistro, H, è necessario accedere alla regola genitore-sinistra-destra.
Successivamente, F e la sua sottostruttura sarebbero stati accessibili completamente. A quel punto, non ci sarebbe dubbio di accedere di nuovo a F. F è il figlio sinistro di C, che ha un bambino destro, G. Dopo che il bambino sinistro, F è stato accessibile completamente, il bambino destro, G, deve quindi accedere dalla regola genitore-sinistra-destra.
E così la sequenza di accesso è: abdecfhg.
Lezioni Java
L'albero viene ri-esploso qui per un facile riferimento:
Nodo
lettera) del nodo. Dovrebbe anche avere altre due proprietà denominate sinistra e destra. Alla proprietà sinistra verrà assegnato un nodo figlio se il nodo ha un figlio sinistro. Alla proprietà giusta verrà assegnato il nodo figlio "A" se il nodo ha un bambino giusto "a".
La classe nodo necessita di un costruttore che creerà l'oggetto nodo e assegnerà un valore alla chiave. Il codice per la classe è:
nodo di classe
CHIAVE CHAR;
Nodo a sinistra, a destra;
nodo pubblico (valore char)
tasto = valore;
sinistra = a destra = null;
Quando viene appena creato un nodo, non ha un bambino. Ecco perché le proprietà sinistro e destro sono assegnate null. Nel metodo principale (), se un particolare nodo ha un figlio sinistro, il bambino verrà creato e assegnato alla proprietà sinistra del nodo particolare. Se un particolare nodo ha un figlio giusto, il bambino verrà creato e assegnato alla proprietà giusta del nodo particolare.
La classe dell'albero
Il codice per la classe dell'albero è:
class binarytree
Radice di nodo;
BinaryTree ()
root = null;
La classe dell'albero indica la radice. Ha una proprietà chiamata root, che è per il nodo radice. Ha un costruttore senza alcun parametro. Questo costruttore assegna null alla radice. Quando viene appena creato un albero, non ha nodo ed è per questo che la radice della proprietà è nulla. Il primo nodo creato sarà il nodo radice e verrà assegnato a questa proprietà, root. Da lì, l'albero crescerà nel metodo principale () (vedi sotto).
La classe BinaryTree ha i metodi, preorder () e main () di seguito.
Il metodo del preordine
Questo è il nucleo del programma, sebbene il metodo principale () sia importante. Il metodo preordine implementa la regola genitore-leftchild-rightchild. Questa è una funzione ricorsiva, il cui codice è:
void preorder (nodo nodo)
if (node == null)
ritorno;
// Accedi al nodo genitore
Sistema.fuori.Stampa (nodo.tasto + "->");
// Accedi al bambino sinistro
preordine (nodo.Sinistra);
// Accedi al bambino giusto
preordine (nodo.Giusto);
Alla fine del traversario dell'albero, nessun nodo attraverserà, quindi il valore di qualsiasi nodo sarà nullo. Questo spiega la prima dichiarazione nella funzione preordine. La seconda istruzione stampa la chiave del nodo corrente. La terza affermazione ricorda la stessa funzione di preordine con il nodo figlio sinistro. La prossima e ultima affermazione ricorda la funzione di preordine con il nodo figlio giusto. In questo modo, l'intero albero viene attraversato.
Nella visualizzazione della sequenza, a-> b-> d, dopo che è stato accessibile B, “Preordine (nodo.a destra) ”è chiamato per il nodo C ma riservato. Dopo che è stato accessibile D, “Preordine (nodo.a destra) "è chiamato per il nodo e. La chiamata per il nodo C, che era riservato, viene eseguita dopo. Questa spiegazione si applica al ramo giusto dell'intero albero.
E quindi la sequenza di output dovrebbe essere: a-> b-> d-> e-> c-> f-> h-> g .
Il metodo principale ()
Il metodo principale crea l'albero assegnando nuovi nodi con le loro chiavi alla proprietà sinistra o destra di un nodo genitore. Innanzitutto, viene creato un albero vuoto. Alla fine del metodo principale (), il metodo preordine viene chiamato una volta. Dal momento che è una funzione ricorsiva, continuerà a chiamarsi fino a quando l'intero albero non sarà attraversato. Il codice è:
public static void main (string [] args)
// Crea oggetto albero senza nodo
BinaryTree Tree = new BinaryTree ();
// Crea nodi per l'albero
albero.root = new node ('a');
albero.radice.a sinistra = nuovo nodo ('b');
albero.radice.a destra = nuovo nodo ('c');
albero.radice.Sinistra.a sinistra = nuovo nodo ('d');
albero.radice.Sinistra.diritto = nuovo nodo ('e');
albero.radice.Giusto.a sinistra = nuovo nodo ('f');
albero.radice.Giusto.a destra = nuovo nodo ('g');
albero.radice.Giusto.Sinistra.a sinistra = nuovo nodo ('h');
// Attraversamento dell'albero di preordine
Sistema.fuori.println ("preordine traversa");
albero.preordine (albero.radice);
Sistema.fuori.println ();
Tutti i codici di cui sopra possono essere assemblati in un programma per il test.
L'output è:
A-> b-> d-> e-> c-> f-> h-> g->
L'ultimo -> può essere ignorato.
Conclusione
Il preordinamento binario dell'albero in Java, che utilizza ricorsione, ha due classi. Ha la classe nodo e la classe BinaryTree. La classe nodo ha una proprietà per la chiave. Ha anche due proprietà del nodo per il nodo figlio sinistro e il nodo figlio destro. La classe BinaryTree ha due metodi: il metodo preordine () e il metodo principale (). Il metodo preorder () implementa ricorsivamente lo schema genitore-leftchild-rightchild. Il metodo principale () costruisce l'albero assegnando nuovi nodi con le loro chiavi come figli sinistra e destra ai nodi genitori.
Il problema con l'algoritmo ricorsivo per il preordine è che se l'albero è troppo grande, la memoria può diventare breve. Per risolvere questo problema, usa l'algoritmo iterativo - vedi più tardi.