Share
Cosa starai creandoGli alberi sono una delle strutture dati più comunemente usate nello sviluppo web. Questa affermazione è valida sia per gli sviluppatori che per gli utenti. Ogni sviluppatore web che ha scritto HTML e caricato in un browser Web ha creato un albero, che viene definito DOM (Document Object Model). Ogni utente di Internet che ha, a sua volta, consumato informazioni su Internet l'ha ricevuto sotto forma di albero: il DOM.
Ora, ecco l'apice: l'articolo che stai leggendo in questo momento è reso nel tuo browser come un albero! Il paragrafo che stai leggendo è rappresentato come testo in a elemento; il l'elemento è annidato all'interno di a elemento; e il l'elemento è annidato all'interno di un elemento.
L'annidamento dei dati è simile a un albero genealogico. Il elemento è un genitore, il elemento è un bambino, e il elemento è un figlio di elemento. Se questa analogia di un albero ti sembra utile, allora troverai conforto nel sapere che più analogie saranno utilizzate durante la nostra implementazione di un albero.
In questo articolo creeremo un albero utilizzando due diversi metodi di attraversamento degli alberi: Depth-First Search (DFS) e Breadth-First Search (BFS). (Se la parola traversal non ti è familiare, considera che significhi visitare ogni nodo dell'albero.) Entrambi questi tipi di attraversamenti evidenziano diversi modi di interagire con un albero; entrambi i viaggi, inoltre, incorporano l'uso delle strutture dati che abbiamo trattato in questa serie. DFS utilizza uno stack e BFS utilizza una coda per visitare i nodi. Questo è figo!
In informatica, un albero è una struttura dati che simula i dati gerarchici con i nodi. Ogni nodo di un albero contiene i propri dati e i puntatori ad altri nodi.
La terminologia dei nodi e dei puntatori può essere nuova per alcuni lettori, quindi descriviamoli ulteriormente con un'analogia. Confrontiamo un albero con un organigramma. Il grafico ha una posizione di primo livello (nodo radice), come il CEO. Direttamente sotto questa posizione ci sono altre posizioni, come il vicepresidente (VP).
Per rappresentare questa relazione, utilizziamo le frecce che indicano dal CEO a un VP. Una posizione, come l'amministratore delegato, è un nodo; il rapporto che creiamo da un CEO a un VP è un puntatore. Per creare più relazioni nel nostro organigramma, ripetiamo semplicemente questo processo: abbiamo un punto nodo su un altro nodo.
A livello concettuale, spero che nodi e indicatori abbiano senso. A livello pratico, possiamo beneficiare di un esempio più tecnico. Consideriamo il DOM. Un DOM ha un elemento come posizione di primo livello (nodo radice). Questo nodo punta a a elemento e a elemento. Questo processo viene ripetuto per tutti i nodi nel DOM.
Una delle bellezze di questo design è la possibilità di annidare i nodi: a elementi annidati al suo interno; inoltre, ciascuno elemento può avere fratello i nodi. È strano, eppure divertente e vero!
Poiché ogni albero contiene nodi, che possono essere un costruttore separato da un albero, verranno delineate le operazioni di entrambi i costruttori: Nodo e Albero.
Accentsconagua
dati memorizza un valore.genitore punta al genitore di un nodo.bambini punta al nodo successivo nell'elenco._radice punta al nodo radice di un albero.traverseDF (callback) attraversa i nodi di un albero con DFS.traverseBF (callback) attraversa i nodi di un albero con BFS.contiene (dati, attraversamento) cerca un nodo in un albero.aggiungi (dati, toData, traversa) aggiunge un nodo ad un albero.rimuovere (figlio, genitore) rimuove un nodo in un albero. Ora scriviamo il codice per un albero!
Per la nostra implementazione, definiremo innanzitutto una funzione denominata Nodo e poi un costruttore chiamato Albero.
function Node (data) this.data = data; this.parent = null; this.children = [];
Ogni istanza del nodo contiene tre proprietà: dati, genitore, e bambini. La prima proprietà contiene i dati associati a un nodo. La seconda proprietà punta a un nodo. La terza proprietà punta a molti nodi figli.
Ora, definiamo il nostro costruttore per Albero, che include il Nodo costruttore nella sua definizione:
function Tree (data) var node = new Node (data); this._root = node;
Albero contiene due righe di codice. La prima riga crea una nuova istanza di Nodo; la seconda linea assegna nodo come la radice di un albero.
Le definizioni di Albero e Nodo richiede solo poche righe di codice. Queste linee, tuttavia, sono sufficienti per aiutarci a simulare i dati gerarchici. Per dimostrare questo punto, usiamo alcuni dati di esempio per creare un'istanza di Albero (e, indirettamente, Nodo).
var tree = new Tree ('CEO'); // data: 'CEO', parent: null, children: [] tree._root;Grazie all'esistenza di genitore e bambini, possiamo aggiungere nodi come figli di _radice e anche assegnare _radice come i genitori di quei nodi. In altre parole, possiamo simulare la creazione di dati gerarchici.
Successivamente, creeremo i seguenti cinque metodi:
Albero
traverseDF (callback)traverseBF (callback)contiene (dati, attraversamento)aggiungi (figlio, genitore)rimuovere (nodo, genitore)Poiché ogni metodo di un albero ci impone di attraversare un albero, implementeremo innanzitutto metodi che definiscono diversi tipi di attraversamento di alberi. (Attraversare un albero è un modo formale per dire di visitare ogni nodo di un albero.)
1 di 5: traverseDF (callback)
Questo metodo attraversa un albero con la ricerca in profondità.
Tree.prototype.traverseDF = function (callback) // questa è una funzione recurse e di richiamo immediato (function recurse (currentNode) // step 2 for (var i = 0, length = currentNode.children.length; i < length; i++) // step 3 recurse(currentNode.children[i]); // step 4 callback(currentNode); // step 1 )(this._root); ;
traverseDF (callback) ha un parametro chiamato richiama. Se non è chiaro il nome, richiama si presume che sia una funzione, che verrà chiamata in seguito traverseDF (callback).
Il corpo di traverseDF (callback) include un'altra funzione chiamata ricorso. Questa funzione è una funzione ricorsiva! In altre parole, è autoinviante e auto-terminante. Utilizzando i passaggi indicati nei commenti di ricorso, Descriverò il processo generale ricorso usa per attraversare l'intero albero.
Ecco i passaggi:
ricorso con il nodo radice di un albero come argomento. In questo momento, nodoCorrente punta al nodo corrente. per loop e iterare una volta per ogni figlio di nodoCorrente, iniziando dal primo figlio. per loop, invocare recurse con un figlio di nodoCorrente. Il bambino esatto dipende dall'iterazione corrente di per ciclo continuo. nodoCorrente non ha più figli, usciamo dal per loop e invoca il richiama siamo passati durante l'invocazione di traverseDF (callback). Passaggi 2 (auto-terminante), 3 (auto-invocando) e 4 (richiamata) ripetizione fino a quando attraversiamo ogni nodo di un albero.
La ricorsione è un argomento molto difficile da insegnare e richiede un intero articolo per spiegarlo adeguatamente. Dal momento che la spiegazione della ricorsione non è il punto focale di questo articolo - l'obiettivo è l'implementazione di un albero - suggerirò che qualsiasi lettore privo di una buona conoscenza della ricorsione faccia le seguenti due cose.
Primo, sperimenta la nostra attuale implementazione di traverseDF (callback) e prova a capire fino a che punto funziona. Secondo, se vuoi che scriva un articolo sulla ricorsione, ti preghiamo di richiederlo nei commenti di questo articolo.
L'esempio seguente dimostra come un albero verrebbe attraversato traverseDF (callback). Per attraversare un albero, ne creerò uno nell'esempio qui sotto. L'approccio che userò in questo momento non è l'ideale, ma funziona. Un approccio migliore sarebbe quello di utilizzare aggiungere valore), che implementeremo nel passaggio 4 di 5.
var tree = new Tree ('uno'); tree._root.children.push (new Node ('two')); tree._root.children [0] .parent = tree; tree._root.children.push (new Node ('three')); tree._root.children [1] .parent = tree; tree._root.children.push (new Node ('four')); tree._root.children [2] .parent = tree; tree._root.children [0] .children.push (new Node ('five')); tree._root.children [0] .children [0] .parent = tree._root.children [0]; tree._root.children [0] .children.push (new Node ('six')); tree._root.children [0] .children [1] .parent = tree._root.children [0]; tree._root.children [2] .children.push (new Node ('seven')); tree._root.children [2] .children [0] .parent = tree._root.children [2]; / * crea questo albero uno ├── due │ ├── cinque │ └── sei ├── tre └── quattro └── sette * /Ora, invochiamo traverseDF (callback).
tree.traverseDF (function (node) console.log (node.data)); / * registra le seguenti stringhe nella console "cinque" sei "due" tre "sette" quattro "uno" * /
2 di 5: traverseBF (callback)
Questo metodo utilizza la ricerca in larghezza per attraversare un albero.
La differenza tra ricerca in profondità e ricerca in ampiezza implica la sequenza in cui i nodi di una visita ad albero. Per illustrare questo punto, usiamo l'albero da cui abbiamo creato traverseDF (callback).
/ * albero uno (profondità: 0) ├── due (profondità: 1) │ ├── cinque (profondità: 2) │ └── sei (profondità: 2) ├── tre (profondità: 1) └── quattro (profondità: 1) └── sette (profondità: 2) * /
Ora, passiamo traverseBF (callback) la stessa callback per la quale abbiamo usato traverseDF (callback).
tree.traverseBF (function (node) console.log (node.data)); / * registra le seguenti stringhe sulla console "una" due "tre" quattro "cinque" sei "sette" * /
I registri dalla console e il diagramma del nostro albero rivelano uno schema sulla ricerca in ampiezza. Inizia con il nodo radice; quindi percorri una profondità e visita ogni nodo in quella profondità da sinistra a destra. Ripeti questo processo finché non ci sono più profondità da percorrere.
Dal momento che abbiamo un modello concettuale di ricerca in ampiezza, implementiamo ora il codice che farebbe funzionare il nostro esempio.
Tree.prototype.traverseBF = function (callback) var queue = new Queue (); queue.enqueue (this._root); currentTree = queue.dequeue (); while (currentTree) for (var i = 0, length = currentTree.children.length; i < length; i++) queue.enqueue(currentTree.children[i]); callback(currentTree); currentTree = queue.dequeue(); ;
La nostra definizione di traverseBF (callback) contiene molta logica Per questo motivo, spiegherò la logica in passi gestibili:
Coda.traverseBF (callback) per l'istanza di Coda. nodoCorrente e inizializzarlo al nodo abbiamo appena aggiunto alla nostra coda. nodoCorrente punta a un nodo, esegue il codice all'interno di mentre ciclo continuo. per loop per iterare sui bambini di nodoCorrente.per loop, aggiungi ogni bambino alla coda. nodoCorrente e passarlo come argomento di richiama. nodoCorrente al nodo che viene rimosso dalla coda. nodoCorrente non punta a un nodo: ogni nodo dell'albero è stato visitato, ripetere i passaggi da 4 a 8.3 di 5: contiene (richiamata, attraversamento)
Definiamo un metodo che ci consenta di cercare un valore particolare nel nostro albero. Ho usato uno dei nostri metodi di attraversamento degli alberi contiene (richiamata, attraversamento) accettare due argomenti: i dati da cercare e il tipo di attraversamento.
Tree.prototype.contains = function (callback, traversal) traversal.call (this, callback); ;
Nel corpo di contiene (richiamata, attraversamento), usiamo un metodo chiamato chiamata passare Questo e richiama. Il primo argomento si lega traversal all'albero che ha invocato contiene (richiamata, attraversamento); il secondo argomento è una funzione invocata su ogni nodo nel nostro albero.
Immagina di voler accedere alla console tutti i nodi che contengono dati con un numero dispari e attraversare tutti i nodi del nostro albero con BFS. Questo è il codice che scriveremmo:
// tree è un esempio di un nodo root tree.contains (function (node) if (node.data === 'two') console.log (nodo);, tree.traverseBF);
4 di 5: aggiungi (dati, dati, attraversamenti)
Ora abbiamo un metodo per cercare un nodo specifico nel nostro albero. Definiamo ora un metodo che ci consentirà di aggiungere un nodo a un nodo specifico.
Tree.prototype.add = function (data, toData, traversal) var child = new Node (data), parent = null, callback = function (node) if (node.data === toData) parent = node; ; this.taintains (callback, traversal); se (genitore) genitore.children.push (figlio); child.parent = parent; else throw new Error ('Impossibile aggiungere nodo a un parent non esistente.'); ;aggiungi (dati, dati, attraversamenti) definisce tre parametri. Il primo parametro, dati, è usato per creare una nuova istanza di Nodo. Il secondo parametro, toData, è usato per confrontare ogni nodo in un albero. Il terzo parametro, traversal, è il tipo di attraversamento dell'albero utilizzato in questo metodo.
Nel corpo di aggiungi (dati, dati, attraversamenti), dichiariamo tre variabili. La prima variabile, bambino, è inizializzato come una nuova istanza di Nodo. La seconda variabile, genitore, è inizializzato come nullo; ma in seguito indicherà qualsiasi nodo in un albero che corrisponda al valore di toData. La riassegnazione di genitore succede nella terza variabile che dichiariamo, che è richiama.
richiama è una funzione che confronta toData a ogni nodo dati proprietà. Se la Se la dichiarazione valuta a vero, poi genitore è assegnato al nodo che corrisponde al confronto nel Se dichiarazione.
Il confronto effettivo di ogni nodo in toData Si verifica contiene (richiamata, attraversamento). Il tipo di attraversamento e richiama deve essere passato come argomento di contiene (richiamata, attraversamento).
Infine, se genitore esiste nell'albero, spingiamo bambino in parent.children; assegniamo anche genitore al genitore di bambino. Altrimenti, abbiamo generato un errore.
Usiamo aggiungi (dati, dati, attraversamenti) in un esempio:
var tree = new Tree ('CEO'); tree.add ('VP of Happiness', 'CEO', tree.traverseBF); / * il nostro albero 'CEO' └── 'VP of Happiness' * /Ecco un esempio più complesso di aggiungi (aggiungi dati, a dati, attraversa):
var tree = new Tree ('CEO'); tree.add ('VP of Happiness', 'CEO', tree.traverseBF); tree.add ('VP of Finance', 'CEO', tree.traverseBF); tree.add ('VP of Sadness', 'CEO', tree.traverseBF); tree.add ('Director of Puppies', 'VP of Finance', tree.traverseBF); tree.add ('Manager of Puppies', 'Director of Puppies', tree.traverseBF); / * tree "CEO" ├── "VP of Happiness" ├── "VP of Finance" │ ├── "Director of Puppies" │ └── "Manager of Puppies" └── "VP of Sadness" * /5 di 5: rimuovere (dati, fromData, traversal)
Per completare la nostra implementazione di Albero, aggiungeremo un metodo chiamato rimuovere (dati, fromData, traversal). Simile alla rimozione di un nodo dal DOM, questo metodo rimuoverà un nodo e tutti i suoi figli.
Tree.prototype.remove = function (data, fromData, traversal) var tree = this, parent = null, childToRemove = null, index; var callback = function (node) if (node.data === fromData) parent = node; ; this.taintains (callback, traversal); if (parent) index = findIndex (parent.children, data); if (index === undefined) throw new Error ('Nodo da rimuovere non esiste.'); else childToRemove = parent.children.splice (index, 1); else throw new Error ('Parent non esiste.'); return childToRemove; ;Simile a aggiungi (dati, dati, attraversamenti), rimuovere attraversa un albero per trovare un nodo che contiene il secondo argomento, che è ora fromData. Se questo nodo viene trovato, allora genitore indica ad esso.
In questo momento, raggiungiamo il nostro primo Se dichiarazione. Se genitore non esiste, lanciamo un errore Se genitore esiste, invochiamo FindIndex () con parent.children e i dati che vogliamo rimuovere dai nodi figli di genitore. (FindIndex () è un metodo di supporto che ho definito di seguito.)
function findIndex (arr, data) var index; per (var i = 0; i < arr.length; i++) if (arr[i].data === data) index = i; return index;
Dentro FindIndex (), si verifica la seguente logica. Se uno dei nodi in parent.children contenere dati corrispondenti dati, la variabile indice è assegnato un intero. Se nessuna delle proprietà dei dati dei bambini corrisponde dati, poi indice mantiene il suo valore predefinito di non definito. Sull'ultima riga di FindIndex (), torniamo indice.
Ora torniamo a rimuovere (dati, fromData, traversal). Se indice è non definito, viene generato un errore. Se indice è definito, lo usiamo per unire il nodo che vogliamo rimuovere dai figli di genitore; assegniamo anche il bambino rimosso a childToRemove.
Alla fine, torniamo childToRemove.
La nostra implementazione di Albero è completo. Dai un'occhiata, abbiamo realizzato molto:
function Node (data) this.data = data; this.parent = null; this.children = []; function Tree (data) var node = new Node (data); this._root = node; Tree.prototype.traverseDF = function (callback) // questa è una funzione recurse e di richiamo immediato (function recurse (currentNode) // step 2 for (var i = 0, length = currentNode.children.length; i < length; i++) // step 3 recurse(currentNode.children[i]); // step 4 callback(currentNode); // step 1 )(this._root); ; Tree.prototype.traverseBF = function(callback) var queue = new Queue(); queue.enqueue(this._root); currentTree = queue.dequeue(); while(currentTree) for (var i = 0, length = currentTree.children.length; i < length; i++) queue.enqueue(currentTree.children[i]); callback(currentTree); currentTree = queue.dequeue(); ; Tree.prototype.contains = function(callback, traversal) traversal.call(this, callback); ; Tree.prototype.add = function(data, toData, traversal) var child = new Node(data), parent = null, callback = function(node) if (node.data === toData) parent = node; ; this.contains(callback, traversal); if (parent) parent.children.push(child); child.parent = parent; else throw new Error('Cannot add node to a non-existent parent.'); ; Tree.prototype.remove = function(data, fromData, traversal) var tree = this, parent = null, childToRemove = null, index; var callback = function(node) if (node.data === fromData) parent = node; ; this.contains(callback, traversal); if (parent) index = findIndex(parent.children, data); if (index === undefined) throw new Error('Node to remove does not exist.'); else childToRemove = parent.children.splice(index, 1); else throw new Error('Parent does not exist.'); return childToRemove; ; function findIndex(arr, data) var index; for (var i = 0; i < arr.length; i++) if (arr[i].data === data) index = i; return index; Gli alberi simulano i dati gerarchici. Gran parte del mondo che ci circonda assomiglia a questo tipo di gerarchia, come le pagine Web e le nostre famiglie. Ogni volta che ti trovi a dover strutturare i dati con la gerarchia, considera l'utilizzo di un albero.
