Share
Hva du skal skapeTrær er en av de mest brukte datastrukturene i webutvikling. Denne utsagnet gjelder både for utviklere og brukere. Hver webutvikler som har skrevet HTML og lastet den inn i en nettleser, har opprettet et tre, som refereres til som dokumentobjektmodellen (DOM). Hver bruker av Internett som i sin tur har konsumert informasjon på Internett, har mottatt den i form av et tre - DOM.
Nå er det klimaks: Artikkelen du leser for øyeblikket, blir gjengitt i nettleseren din som et tre! Avsnittet du leser er representert som tekst i a element; de elementet er nestet inne i a element; og elementet er nestet inne i en element.
Nestingen av data ligner et slektstre. De element er en forelder, den element er et barn, og element er et barn av element. Hvis denne analogien til et tre virker nyttig for deg, vil du finne trøst i å vite at flere analogier vil bli brukt under implementeringen av et tre.
I denne artikkelen vil vi opprette et tre med to forskjellige metoder for tre-traversal: Dybde-første søk (DFS) og bredde-første søk (BFS). (Hvis ordet traversal er ukjent for deg, anser det å bety å besøke hver knutepunkt.) Begge disse typer traverser markerer forskjellige måter å interagere med et tre på; begge reiser innbefatter også bruken av datastrukturer som vi har dekket i denne serien. DFS bruker en stabel og BFS bruker en kø for å besøke noder. Det er kult!
I datavitenskap er et tre en datastruktur som simulerer hierarkiske data med noder. Hver node av et tre har sine egne data og pekere til andre noder.
Terminene til noder og pekere kan være nye for noen lesere, så la oss beskrive dem videre med en analogi. La oss sammenligne et tre til et organisasjonsskjema. Diagrammet har en toppnivåposisjon (root node), for eksempel konsernsjef. Rett under denne stillingen er andre stillinger, som visepresident (VP).
For å representere dette forholdet bruker vi piler som peker fra konsernsjefen til en VP. En stilling, som administrerende direktør, er en knutepunkt; forholdet vi lager fra en administrerende direktør til en VP er en peker. For å skape flere relasjoner i vårt organisasjonsdiagram, gjentar vi bare denne prosessen - vi har et knutepunkt til en annen knutepunkt.
På et konseptnivå, håper jeg at noder og pekere gir mening. På praktisk nivå kan vi dra nytte av å bruke et mer teknisk eksempel. La oss vurdere DOM. En DOM har en element som sin toppnivåposisjon (root node). Denne noden peker på a element og a element. Denne prosessen gjentas for alle noder i DOM.
En av skjønnhetene i dette designet er evnen til å neste noder: a elementer nestet inne i det; dessuten hver elementet kan ha søsken noder. Det er rart, men likevel morsomt og sant!
Siden hvert tre inneholder noder, som kan være en separat konstruktør fra et tre, vil vi skissere operasjonene til begge konstruktørene: node og Tre.
Accentsconagua
data lagrer en verdi.forelder peker til en nodes foreldre.barn peker til neste knutepunkt i listen._rot peker på rotknuten til et tre.traverseDF (tilbakeringing) traverser noder av et tre med DFS.traverseBF (tilbakeringing) traverser noder av et tre med BFS.inneholder (data, traversal) søker etter en node i et tre.legg til (data, toData, krysse) legger til en node til et tre.fjern (barn, foreldre) fjerner en knutepunkt i et tre. La oss nå skrive koden for et tre!
For implementeringen skal vi først definere en funksjon som heter node og deretter en konstruktør oppkalt Tre.
funksjonsnode (data) this.data = data; this.parent = null; this.children = [];
Hver forekomst av Node inneholder tre egenskaper: data, forelder, og barn. Den første egenskapen inneholder data knyttet til en node. Den andre egenskapen peker på en knute. Den tredje eiendommen peker på mange barn noder.
La oss nå definere vår konstruktør for Tre, som inkluderer node konstruktør i sin definisjon:
funksjon Tree (data) var node = ny Node (data); this._root = node;
Tre inneholder to linjer med kode. Den første linjen oppretter en ny forekomst av node; den andre linjen tildeler node som roten til et tre.
Definisjonene av Tre og node krever bare noen få linjer med kode. Disse linjene er imidlertid nok til å hjelpe oss med å simulere hierarkiske data. For å bevise dette punktet, la oss bruke noen eksempler på data for å lage en forekomst av Tre (og indirekte, node).
var tree = nytt tre ('CEO'); // data: 'CEO', foreldre: null, barn: [] tree._root;Takket være eksistensen av forelder og barn, Vi kan legge til noder som barn av _rot og tilordne også _rot som foreldrene til disse noderne. Med andre ord kan vi simulere opprettelsen av hierarkiske data.
Deretter skal vi opprette følgende fem metoder:
Tre
traverseDF (tilbakeringing)traverseBF (tilbakeringing)inneholder (data, traversal)legg til (barn, foreldre)fjern (node, foreldre)Siden hver metode av et tre krever at vi krysser et tre, vil vi først implementere metoder som definerer ulike typer treetransversal. (Å krysse et tre er en formell måte å si på å besøke hver knutepunkt.)
1 av 5: traverseDF (tilbakeringing)
Denne metoden går gjennom et tre med dybde-første søk.
Tree.prototype.traverseDF = funksjon (tilbakeringing) // dette er en tilbakekallingsfunksjon og umiddelbart innkallingsfunksjon (funksjonsfornyer (currentNode) // trinn 2 for (var i = 0, lengde = nåværende Node.children.length; i < length; i++) // step 3 recurse(currentNode.children[i]); // step 4 callback(currentNode); // step 1 )(this._root); ;
traverseDF (tilbakeringing) har en parameter som heter Ring tilbake. Hvis det er uklart fra navnet, Ring tilbake antas å være en funksjon, som vil bli kalt senere inn traverseDF (tilbakeringing).
Kroppen av traverseDF (tilbakeringing) inkluderer en annen funksjon som heter recurse. Denne funksjonen er en rekursiv funksjon! Med andre ord er det selvoppkalt og selvoppsigende. Bruk trinnene nevnt i kommentarene til recurse, Jeg skal beskrive den generelle prosessen som recurse bruker til å krysse hele treet.
Her er trinnene:
recurse med rotenoden til et tre som argument. I dette øyeblikk, currentNode peker til gjeldende knutepunkt. til loop og iterate en gang for hvert barn av currentNode, begynner med det første barnet. til loop, påkalle rekryter med et barn av currentNode. Det eksakte barnet avhenger av gjeldende iterasjon av til sløyfe. currentNode Vi har ikke lenger barn, vi forlater til loop og påkalle Ring tilbake vi passerte under påkallingen av traverseDF (tilbakeringing). Trinn 2 (selvoppsigende), 3 (selvoppringing) og 4 (tilbakeringing) gjenta til vi krysser hvert knutepunkt.
Rekursjon er et veldig vanskelig tema å undervise og krever en hel artikkel for å tilstrekkelig forklare det. Siden forklaringen på rekursjon ikke er fokus i denne artikkelen, er fokuset på å implementere et tre. Jeg foreslår at noen lesere mangler en god forståelse av rekursjon gjør følgende to ting.
Forsøk først med vår nåværende implementering av traverseDF (tilbakeringing) og prøv å forstå i en grad hvordan det fungerer. For det andre, hvis du vil at jeg skal skrive en artikkel om rekursjon, vennligst be om det i kommentarene i denne artikkelen.
Følgende eksempel viser hvordan et tre ville bli krysset med traverseDF (tilbakeringing). Å krysse et tre, jeg lager en i eksempelet nedenfor. Tilnærmingen som jeg vil bruke i øyeblikket er ikke ideell, men det fungerer. En bedre tilnærming ville være å bruke Legg til verdi), som vi vil implementere i trinn 4 av 5.
var tree = nytt tre ('en'); tree._root.children.push (ny node ('two')); tree._root.children [0] .parent = tree; tree._root.children.push (ny knutepunkt ('tre')); tree._root.children [1] .parent = tree; tree._root.children.push (ny knutepunkt ('fire')); tree._root.children [2] .parent = tree; tree._root.children [0] .children.push (ny knutepunkt ('fem')); tree._root.children [0] .children [0] .parent = tree._root.children [0]; tree._root.children [0] .children.push (ny node ('six')); tree._root.children [0] .children [1] .parent = tree._root.children [0]; tree._root.children [2] .children.push (ny node ('seven')); tree._root.children [2] .children [0] .parent = tree._root.children [2]; / * lager dette treet en ├── two │ ├── five │ └─ - six ├── three └── four └── seven * /Nå, la oss påkalle traverseDF (tilbakeringing).
tree.traverseDF (funksjon (node) console.log (node.data)); / * logger følgende strenger til konsollen "fem" seks "to" tre "sju" fire "en" * /
2 av 5: traverseBF (tilbakeringing)
Denne metoden bruker bredde-første søk for å krysse et tre.
Forskjellen mellom dybde-første søk og bredde-første søk innebærer sekvensen som nodene til et trebesøk. For å illustrere dette punktet, la oss bruke treet vi opprettet fra traverseDF (tilbakeringing).
/ * tre en (dybde: 0) ├── to (dybde: 1) │ ├── fem (dybde: 2) │ └─ - seks (dybde: 2) ├── tre (dybde: 1) └── fire (dybde: 1) └─ - syv (dybde: 2) * /
La oss nå passere traverseBF (tilbakeringing) samme tilbakeringingen vi brukte til traverseDF (tilbakeringing).
tree.traverseBF (funksjon (node) console.log (node.data)); / * logger følgende strenger til konsollen "en" to "tre" fire "fem" seks "sju" * /
Loggene fra konsollen og diagrammet til vårt tre viser et mønster om bredde-første søk. Start med rotnoden; Reis deretter en dybde og besøk hver knutepunkt i det dybde fra venstre til høyre. Gjenta denne prosessen til det ikke er flere dybder å reise.
Siden vi har en konseptuell modell for bredde-første søk, la oss nå implementere koden som ville gjøre vårt eksempel arbeid.
Tree.prototype.traverseBF = funksjon (tilbakeringing) var kø = ny kø (); queue.enqueue (this._root); currentTree = queue.dequeue (); mens (currentTree) for (var i = 0, lengde = currentTree.children.length; i < length; i++) queue.enqueue(currentTree.children[i]); callback(currentTree); currentTree = queue.dequeue(); ;
Vår definisjon av traverseBF (tilbakeringing) inneholder mye logikk. Av denne grunn vil jeg forklare logikken i håndterbare trinn:
Kø.traverseBF (tilbakeringing) til forekomsten av Kø. currentNode og initialiser den til node vi har nettopp lagt til i køen vår. currentNode peker på en knutepunkt, kjør koden inni samtidig som sløyfe. til loop for å iterere på barna av currentNode.til sløyfe, legg til hvert barn i køen. currentNode og send det som et argument av Ring tilbake. currentNode til noden blir fjernet fra køen. currentNode peker ikke på en knute - hver knutepunkt i treet har blitt besøkt - gjenta trinn 4 til 8.3 av 5: inneholder (tilbakekalling, traversal)
La oss definere en metode som lar oss søke etter en bestemt verdi i treet vårt. For å bruke noen av våre metoder for trekryp, har jeg definert inneholder (tilbakekalling, traversal) å akseptere to argumenter: dataene som skal søkes og typen av traversal.
Tree.prototype.contains = funksjon (tilbakering, traversal) traversal.call (dette, tilbakeringing); ;
I kroppen av inneholder (tilbakekalling, traversal), Vi bruker en metode som heter anrop å passere dette og Ring tilbake. Det første argumentet binder traversering til treet som påkalte inneholder (tilbakekalling, traversal); Det andre argumentet er en funksjon som påberopes på hver knutepunkt i vårt tre.
Tenk deg at vi ønsker å logge inn på konsollen noen noder som inneholder data med et oddetall og krysse hver knutepunkt i vårt tre med BFS. Dette er koden vi vil skrive:
// tree er et eksempel på en root node tree.contains (funksjon (node) if (node.data === 'two') console.log (node);, tree.traverseBF);
4 av 5: legg til (data, toData, traversal)
Vi har nå en metode for å søke etter en bestemt node i vårt tre. La oss nå definere en metode som gjør det mulig for oss å legge til en node til en bestemt node.
Tree.prototype.add = funksjon (data, toData, traversal) var barn = ny Node (data), foreldre = null, tilbakeringing = funksjon (node) if (node.data === toData) parent = node; ; this.contains (tilbakekalling, traversal); hvis (foreldre) parent.children.push (barn); child.parent = foreldre; ellers Kast ny feil ('Kan ikke legge til nod til en ikke-eksisterende foreldre.'); ;legg til (data, toData, traversal) definerer tre parametere. Den første parameteren, data, brukes til å opprette en ny forekomst av node. Den andre parameteren, toData, brukes til å sammenligne mot hver knutepunkt i et tre. Den tredje parameteren, traversering, er typen av tre-traversal brukt i denne metoden.
I kroppen av legg til (data, toData, traversal), Vi erklærer tre variabler. Den første variabelen, barn, er initialisert som en ny forekomst av node. Den andre variabelen, forelder, er initialisert som null; men det vil senere peke til hvilken som helst node i et tre som samsvarer med verdien av toData. Omplasseringen av forelder skjer i den tredje variabelen vi erklærer, som er Ring tilbake.
Ring tilbake er en funksjon som sammenligner toData til hver knute data eiendom. Hvis hvis setningen evaluerer til ekte, deretter forelder er tilordnet noden som matchet sammenligningen i hvis uttalelse.
Den faktiske sammenligningen av hver knute til toData forekommer i inneholder (tilbakekalling, traversal). Typen av traversal og Ring tilbake må bestås som argumenter for inneholder (tilbakekalling, traversal).
Til slutt, hvis forelder eksisterer i treet, vi presser barn inn i parent.children; Vi tildeler også forelder til foreldrene til barn. Ellers kaster vi en feil.
La oss bruke legg til (data, toData, traversal) i et eksempel:
var tree = nytt tre ('CEO'); tree.add ('VP of Happiness', 'CEO', tree.traverseBF); / * Vårt tre 'CEO' └── 'VP of Happiness' * /Her er et mer komplekst eksempel på legg til (addData, toData, traversal):
var tree = nytt tre ('CEO'); tree.add ('VP of Happiness', 'CEO', tree.traverseBF); tree.add ('VP of Finance', 'CEO', tree.traverseBF); tree.add ('Varsel av sorg', 'CEO', tree.traverseBF); tree.add ('Valpedirektør', 'VP of Finance', tree.traverseBF); tree.add ('Puppy Manager', 'Director of Puuppies', tree.traverseBF); / * Tree 'CEO' ─ - 'VP of Happiness' ├── 'VP of Finance' │ ├── 'Direktør for valper' │ └── 'Manager of Puppy's' └── 'VP of Sadness' * /5 av 5: fjern (data, fromData, traversal)
For å fullføre vår implementering av Tre, Vi vil legge til en metode som heter fjern (data, fromData, traversal). På samme måte som å fjerne en node fra DOM, fjerner denne metoden en knute og alle sine barn.
Tree.prototype.remove = funksjon (data, fraData, traversal) var tree = dette, foreldre = null, childToRemove = null, index; var tilbakering = funksjon (node) if (node.data === fraData) parent = node; ; this.contains (tilbakekalling, traversal); hvis (foreldre) index = findIndex (foreldre.barn, data); hvis (indeks === undefined) kaste ny feil ('Node å fjerne eksisterer ikke.'); ellers childToRemove = parent.children.splice (indeks, 1); ellers kaste ny feil ('Foreldre eksisterer ikke.'); returner childToRemove; ;Lik legg til (data, toData, traversal), fjern traverses et tre for å finne en node som inneholder det andre argumentet, som er nå fromData. Hvis denne noden er funnet, så forelder peker på det.
For øyeblikket når vi vår første hvis uttalelse. Hvis forelder eksisterer ikke, vi kaster en feil. Hvis forelder eksisterer, påberoper vi oss findIndex () med parent.children og dataene vi ønsker å fjerne fra barnens noder av forelder. (findIndex () er en hjelpemetode som jeg definerte nedenfor.)
funksjon findIndex (arr, data) var index; for (var i = 0; i < arr.length; i++) if (arr[i].data === data) index = i; return index;
Innsiden findIndex (), Følgende logikk oppstår. Hvis noen av noder i parent.children inneholder data som samsvarer data, variabelen index er tilordnet et heltall. Hvis ingen av barnas dataegenskaper samsvarer data, deretter index beholder standardverdien av udefinert. På siste linje av findIndex (), vi returnerer index.
Vi kommer nå tilbake til fjern (data, fromData, traversal). Hvis index er udefinert, en feil blir kastet. Hvis index er definert, bruker vi den til å splitte noden vi vil fjerne fra barna av forelder; Vi tildeler også det fjernede barnet til childToRemove.
Til slutt kommer vi tilbake childToRemove.
Vår implementering av Tre er ferdig. Ta en titt - vi har oppnådd mye:
funksjonsnode (data) this.data = data; this.parent = null; this.children = []; funksjon Tree (data) var node = ny Node (data); this._root = node; Tree.prototype.traverseDF = funksjon (tilbakeringing) // dette er en resurse og umiddelbart innkallingsfunksjon (funksjonsfornyer (currentNode) // trinn 2 for (var i = 0, lengde = 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; Trær simulerer hierarkiske data. Mye av verden rundt oss ligner denne typen hierarki, som nettsider og våre familier. Hver gang du befinner deg i behov av å strukturere data med hierarki, bør du vurdere å bruke et tre.
