Esercitazione sulla struttura dei dati ad albero per principianti

introduzione

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

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

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

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

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

Per comprendere gli esempi di codice in questo articolo, è necessario disporre di conoscenze di base in JavaScript (ECMAScript). Se non si dispone di tale conoscenza, è possibile ottenerla da http://www.rete ampia.com/ChrysanthusForcha-1/ECMAScript-2015-Course.htm

Il diagramma ad 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à dell'albero

- Tutti i rami per tutti i livelli di nodi hanno un'unica fonte, 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, eccetto il nodo radice, è figlio.

Vocabolario dell'albero

• Nodo radice: Questo è il nodo più alto nell'albero e non ha genitori. Ogni altro nodo ha un genitore.
• Nodi foglia: Un nodo foglia è un nodo che non ha figli. Di solito si trovano nella parte inferiore dell'albero e talvolta si trovano 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 figli dei nodi di secondo livello sono al terzo livello, e così via.
• Nodo genitore: Ogni nodo, eccetto il nodo radice, ha un nodo genitore connesso ad esso da un ramo. Qualsiasi nodo, eccetto il nodo radice, è un nodo figlio.
• Nodi fratelli: I nodi di pari livello sono nodi che hanno lo stesso genitore.
• Sentiero: I rami (linee rette) che collegano un nodo all'altro, attraverso altri nodi, formano un percorso. I rami possono o non possono essere frecce.
• Nodo antenato: Tutti i nodi superiori connessi a un figlio, inclusi 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.
• Sottoalbero: Un nodo più tutti i suoi discendenti fino alle relative foglie, formano un sottoalbero. Il nodo iniziale è incluso e non deve essere la radice; altrimenti sarebbe l'intero albero.
• Grado: Il numero di figli di un nodo è detto grado del nodo.

Attraversare 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 viene fatto arbitrariamente. Ci sono tre modi per farlo, ognuno dei quali implica l'attraversamento in profondità come segue:

1) In ordine: In poche parole, in questo schema, viene attraversato per primo il sottoalbero sinistro; quindi si accede al nodo radice; quindi, viene attraversato il sottoalbero destro. Questo schema è simboleggiato come left->root->right. La Fig 1 viene visualizzata nuovamente qui per un facile riferimento:

Supponendo che ci siano due fratelli per nodo; quindi left->root->right significa che accedi prima al nodo più basso e più a sinistra, poi al genitore del nodo e poi al fratello destro. Quando ci sono più di due fratelli, prendi il primo come nodo sinistro e il resto dei nodi destro, come nodo destro. Per l'albero generale sopra, si accede al sottoalbero in basso a sinistra per avere, [EBF]. Questo è un sottoalbero. Il genitore di questo sottoalbero è A; quindi, si accede successivamente ad A per avere [EBF]A. Successivamente, si accede al sottoalbero [GCHI] per avere un sottoalbero più grande, [[EBF]A[GCHI]]. Puoi vedere il profilo sinistro->root->destro che ritrae se stesso. Questo grande sottoalbero a sinistra avrà il sottoalbero, [JDK] alla sua destra per completare l'attraversamento per ottenere, [[EBF]A[GCHI]] [JDK].

2) Pre-ordine: In poche parole, in questo schema si accede per primo al nodo radice, quindi viene attraversato il sottoalbero sinistro e quindi viene attraversato il sottoalbero destro. Questo schema è simboleggiato come radice->sinistra->destra. La Fig 1 viene visualizzata nuovamente qui per un facile riferimento.

Supponendo che ci siano due fratelli per nodo; quindi root->sinistra->destra significa che accedi prima alla radice, poi al figlio immediato sinistro e poi al figlio immediato destro. Quando ci sono più di due fratelli, prendi il primo come nodo sinistro e il resto dei nodi destro, come nodo destro. Il figlio più a sinistra del figlio a sinistra è il successivo a cui accedere. Per l'albero generale sopra, il sottoalbero radice è [ABCD]. A sinistra di questo sottoalbero, hai il sottoalbero, [EF], che fornisce la sequenza di accesso, [ABCD][EF]. A destra di questo sottoalbero più grande, ci sono due sottoalberi, [GHI] e [JK], che danno la sequenza completa, [ABCD][EF][GHI][JK]. Puoi vedere il profilo root->sinistra->destra che ritrae se stesso.

3) Post-Ordine: In poche parole, in questo schema, viene attraversato per primo il sottoalbero sinistro, quindi viene attraversato il sottoalbero destro e quindi si accede alla radice. Questo schema è simboleggiato come sinistra->destra->radice. La Fig 1 viene visualizzata nuovamente qui per un facile riferimento.

Per questo albero i sottoalberi sono, [EFB], [GHIC], [JKD] e [A] che formano la sequenza, [EFB], [GHIC], [JKD][A]. Puoi vedere il profilo sinistro->destro->root che ritrae se stesso.

Creare l'albero

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