Tutorial della struttura dei dati degli alberi per principianti

introduzione

Un albero nel software è come un albero biologico, ma con le seguenti differenze:

• È disegnato a testa in giù.
• Ha solo una radice e nessun gambo.
• I rami emergono dalla radice.
• Un punto in cui un ramo decolla da un altro ramo o la radice è chiamato nodo.
• Ogni nodo ha un valore.

I rami dell'albero del software sono rappresentati da linee rette. Un buon esempio di un albero software che potresti aver usato è l'albero di directory del disco rigido del tuo computer.

Esistono diversi tipi di alberi. C'è l'albero generale da cui derivano altri alberi. Altri alberi sono derivati ​​introducendo vincoli nell'albero generale. Ad esempio, potresti voler un albero in cui non più di due rami emana da un nodo; Un tale albero sarebbe chiamato un albero binario. Questo articolo descrive l'albero generale e come accedere a tutti i suoi nodi.

Il collegamento ipertestuale per scaricare il codice è riportato in fondo a questo articolo.

Per comprendere i campioni di codice in questo articolo, è necessario avere conoscenze di base in JavaScript (ECMAScript). Se non hai questa conoscenza, allora puoi ottenerlo da http: // www.network a Broad.com/Chrysanthusforcha-1/ECMAScript-2015-Course.htm

Il diagramma dell'albero generale

'A' è il nodo radice; È il nodo di primo livello. B, C, D sono sulla seconda riga; Questi sono nodi di secondo livello. E, F, G, H, I, J, K sono sulla terza riga e sono nodi di terzo livello. Una quarta riga avrebbe prodotto nodi di quarto livello, e così via.

Proprietà degli alberi

- Tutti i rami per tutti i livelli di nodi, hanno una sorgente, che è il nodo radice.

- Un albero ha n - 1 rami, dove n è il numero totale di nodi. Il diagramma sopra per l'albero generale ha 11 nodi e 10 rami.

- A differenza degli umani, dove ogni bambino ha due genitori, con l'albero del software, ogni bambino ha un solo genitore. Il nodo radice è il più grande genitore antenato. Un genitore può avere più di un figlio. Ogni nodo, tranne il nodo radice, è un bambino.

Vocabolario degli alberi

• Nodo radice: Questo è il nodo più alto nell'albero e non ha un genitore. Ogni altro nodo ha un genitore.
• Nodi fogliare: Un nodo foglia è un nodo che non ha un bambino. Di solito sono sul fondo dell'albero e talvolta sono ai lati sinistro e/o destro dell'albero.
• Chiave: Questo è il valore di un albero. Può essere un numero; Può essere una stringa; Può anche essere un operatore come + o - o x.
• Livelli: Il nodo radice è al primo livello. I suoi figli sono al secondo livello; I bambini dei nodi di secondo livello sono al terzo livello e così via.
• Nodo genitore: Ogni nodo, tranne il nodo radice, ha un nodo genitore collegato da un ramo. Qualsiasi nodo, tranne il nodo radice, è un nodo figlio.
• Nodi tra fratelli: I nodi tra fratelli sono nodi che hanno lo stesso genitore.
• Sentiero: I rami (linee rette) che collegano un nodo a un altro, attraverso altri nodi, formano un percorso. I rami possono o meno essere frecce.
• 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 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.
• Sottosquadro: 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 numero di bambini che un nodo ha è chiamato grado del nodo.

Attraversando tutti i nodi di un albero

È possibile accedere a tutti i nodi di un albero per leggere o modificare qualsiasi valore del nodo. Tuttavia, questo non è fatto arbitrariamente. Esistono tre modi per farlo, tutti i quali coinvolgono la prima attraversamento come segue:

1) in ordine: In parole povere, in questo schema, la sottostruttura sinistra è attraversata per prima; Quindi, si accede al nodo radice; Quindi, la sottostruttura destra viene attraversata. Questo schema è simboleggiato come a sinistra-> radice-> a destra. La Fig 1 viene ri-esplosa qui per un facile riferimento:

Supponendo che ci siano due fratelli per nodo; Quindi a sinistra-> root-> a destra significa prima accedere al nodo più basso e sinistro, quindi il genitore del nodo, quindi il fratello destro. Quando ci sono più di due fratelli, prendi il primo come sinistro e il resto dei nodi destro, come a destra. Per l'albero generale sopra, si accede alla sottostruttura in basso a sinistra per avere, [EBF]. Questa è una sottostruttura. Il genitore di questa sottostruttura è un; Quindi, A è successivamente accessibile ad avere [EBF] a. Successivamente, la sottostruttura [gchi] è accessibile per avere una sottostruttura più grande, [[ebf] a [gchi]]. Puoi vedere il profilo a sinistra-> root-> destro che si ritrae. Questa grande sottostruttura di sinistra avrà la sottostruttura, [JDK] alla sua destra per completare la attraversamento per ottenere, [[EBF] A [GCHI]] [JDK].

2) preordine: In parole povere, in questo schema si accede prima al nodo radice, quindi la sottostruttura sinistra viene attraversata in seguito, quindi la sottostruttura destra viene attraversata. Questo schema è simboleggiato come radice-> sinistra-> a destra. La Fig 1 viene ri-esplicata qui per un facile riferimento.

Supponendo che ci siano due fratelli per nodo; quindi root-> sinistra-> a destra significa prima accedere alla radice, quindi il bambino immediato sinistro, quindi il bambino immediato destro. Quando ci sono più di due fratelli, prendi il primo come sinistro e il resto dei nodi destro, come a destra. Il figlio più a sinistra del bambino sinistro è il prossimo a cui si accede. Per l'albero generale sopra, la sottostruttura della radice è [ABCD]. A sinistra di questa sottostruttura, hai la sottostruttura, [ef], dando la sequenza di accesso, [ABCD] [EF]. A destra di questa sottostruttura più grande, hai due sottostrutimenti, [Ghi] e [JK], dando la sequenza completa, [ABCD] [EF] [GHI] [JK]. Puoi vedere la radice-> sinistra-> profilo destro che si ritrae.

3) post-ordine: In parole povere, in questo schema, la sottostruttura sinistra viene attraversata per prima, quindi la sottostruttura destra viene attraversata, quindi si accede alla radice. Questo schema è simboleggiato come a sinistra-> destra-> root. La Fig 1 viene ri-esplicata qui per un facile riferimento.

Per questo albero i sottospelle sono, [efb], [ghic], [jkd] e [a] che formano la sequenza, [efb], [ghic], [jkd] [a]. Puoi vedere il profilo a sinistra-> destro-> root che si ritrae.

Creare l'albero

L'albero sopra verrà creato usando ECMascript, che è come l'ultima versione di JavaScript. Ogni nodo è un array. Il primo elemento di ciascun array di nodi è il genitore del nodo, un altro array. Il resto degli elementi del nodo sono i bambini del nodo, a partire dal bambino più a sinistra. C'è una mappa ECMAScript che mette in relazione ogni array con la sua stringa corrispondente (lettera). Il primo segmento di codice è:

O = nuovo array ();
A = nuovo array ();
B = nuovo array ();
C = nuovo array ();
D = nuovo array ();
//foglie
E = nuovo array (b); F = nuovo array (b); G = nuovo array (c); H = nuovo array (c);
I = nuovo array (c); J = nuovo array (d); K = nuovo array (d);
// Aggiunta del contenuto
O [0] = indefinito; O [1] = a;
A [0] = o; A [1] = b; A [2] = c; A [3] = d;
B [0] = a; B [1] = E; B [2] = f;
C [0] = A; C [1] = G; C [2] = H; C [3] = i;
D [0] = a; D [1] = j; D [2] = k;
// mappatura degli oggetti in lettere
coppie = [[a, 'a'], [b, 'b'], [c, 'c'], [d, 'd'], [e, 'e'], [f, 'f'] , [G, 'G'],
[H, 'H'], [I, 'I'], [J, 'J'], [K, 'K']];
mapobj = nuova mappa (coppie);

In ECMAScript, è possibile accedere a una funzione definita più in basso nel programma. Tuttavia, con le variabili, non puoi farlo. Non è possibile accedere a una variabile definita più in basso nel programma. Questo è il motivo per cui le variabili sopra sono state sviluppate come mostrato.

Inoltre, si noti che sopra il nodo radice A, c'è un altro nodo O (non zero). Il primo elemento di questo array (nodo) è indefinito, il che significa che il proprio genitore è indefinito. Il nodo extra O è stato aggiunto per semplificare il codice di attraversamento.

C'è anche una mappa. La mappa mette in relazione ogni array di nomi di una lettere, al nome della stringa corrispondente di una lettera.

Funzione ricorsiva

Per accedere a tutti gli elementi di un albero, hai bisogno di una funzione ricorsiva. Una funzione ricorsiva è una funzione che continua a chiamarsi fino a quando non viene soddisfatta una condizione.

Visitare un nodo non significa necessariamente accedere al nodo. Per accedere a un nodo significa che il suo valore viene letto o modificato. Nei campioni di codice di questo articolo, accedere a un nodo significa leggere e visualizzare il valore (chiave) del nodo. Nei campioni di codice, un nodo può essere visitato più di una volta, ma il suo valore è accessibile una sola volta.

Algoritmo e programmazione

C'è un programma per ciascuna delle tre tecniche di attraversamento.

Algoritmo in ordine e programmazione

Qui, il nodo più basso e più a sinistra viene visitato per primo. I sottostrutimenti [EBF], [[EBF] A [GCHI]] e [JDK] sono sviluppati per dare la sequenza completa, [[EBF] A [GCHI]] [JDK].

Esistono due funzioni ricorsive per questo programma, in cui ognuno chiama l'altro. Quello principale si chiama FN (nodo). Il programma (codice) è breve. Scarica il file combinato di seguito per la codifica dei dettagli.

I tre programmi hanno la stessa configurazione di Array Tree (NODE).

Algoritmo pre-ordine e programmazione

Qui c'è solo una funzione ricorsiva. Si chiama, fn (nodo). Qui, i sottostrutimenti [ABCD], [EF], [Ghi] e [JK] sono sviluppati per dare la sequenza completa, [ABCD] [EF] [Ghi] [JK]. Anche il programma per questo è breve.

I tre programmi hanno la stessa configurazione di Array Tree (NODE).

Algoritmo post-ordine e programmazione

Qui, il nodo più basso e più a sinistra viene visitato per primo. I sottostrutimenti [EFB], [Ghic], [JKD] e [A] sono sviluppati per dare la sequenza completa, [EFB], [Ghic], [JKD] [A] .

Esistono due funzioni ricorsive per questo programma, in cui ognuno chiama l'altro. Quello principale si chiama FN (nodo). Anche il programma per questo è breve. Scarica il file combinato di seguito per la codifica dettagliata.

I tre programmi hanno la stessa configurazione di Array Tree (NODE).

Tipi di alberi

Gli alberi di programmazione del computer sono, in effetti, strutture di dati non lineari. Le strutture di dati lineari sono elenchi, array, stack, code, stack, ecc. Un albero con n nodi ha rami N-1. Quando il numero di rami è uguale o maggiore del numero di nodi, si ottiene un grafico. Un grafico non è proprio un albero.

Ci sono alberi software, che descrivono layout, come l'albero della directory nel disco rigido di un computer. Molti alberi non descrivono affatto i layout esistenti. In effetti, descrivono gli algoritmi. Ad esempio, l'algoritmo matematico (x + y) x (x -y) è descritto da un albero in cui x è il nodo radice, quindi + e - sono nodi figli immediati della radice. xey sono nodi per bambini di +. X e Y sono di nuovo bambini nodi di -. Un tale albero è noto come un albero di espressione.

Molti diversi tipi di alberi possono essere classificati in titoli diversi; come albero binario, albero b, albero di espressione, ecc. Tutti sono derivati ​​dall'albero generale.

Alcune delle categorie degli alberi sono divise in ulteriori categorie. L'albero binario, ad esempio, ha almeno l'albero di ricerca binaria, l'albero AVL e l'albero cartesiano.

Download

Per questo articolo sono stati forniti tre programmi. Esiste un programma per la tecnica in-ordine (algoritmo), un altro per la tecnica di pre-ordine e un altro per la tecnica post-ordine. Tutti sono stati messi in un file zip, chiamato Traversing. Il file zip può essere scaricato su: github.

Conclusione

Un albero di software è come un albero normale nel parco o nella foresta. Tuttavia, l'albero di programmazione del computer è capovolto. Esistono diversi tipi di alberi. Altri alberi sono derivati ​​introducendo vincoli nell'albero generale. È possibile accedere a tutti i nodi di un albero utilizzando un algoritmo in ordine, preordine o post-ordine. Un albero di software può essere prodotto da qualsiasi lingua di computer. Ecmascript è stato scelto qui perché è il linguaggio del computer più semplice. Il prossimo tipo di albero che dovresti studiare è l'albero binario poiché è la struttura dei dati degli alberi più popolare.