Share
Ce veți creaCopacii sunt una dintre cele mai utilizate structuri de date în dezvoltarea web. Această afirmație este valabilă atât pentru dezvoltatori, cât și pentru utilizatori. Fiecare dezvoltator de web care a scris HTML și a încărcat-o într-un browser web a creat un copac, denumit Document Object Model (DOM). Fiecare utilizator al Internetului, care, la rândul său, a consumat informații pe internet, la primit sub forma unui copac - DOM.
Acum, iată punctul culminant: articolul pe care îl citiți în acest moment este redat în browserul dvs. ca un copac! Paragraful pe care îl citiți este reprezentat ca text în a element; elementul este imbricat în interior element; si elementul este imbricat în interior element.
Cuibul de date este similar cu un arbore genealogic. element este un părinte, element este un copil, și element este un copil al element. Dacă această analogie a unui copac ți se pare utilă, atunci vei găsi confortul în a ști că mai multe analogii vor fi folosite în timpul implementării unui copac.
În acest articol, vom crea un copac utilizând două metode diferite de traversare a copacilor: Căutarea în profunzime (DFS) și Căutarea în Bretă (BFS). (În cazul în care cuvântul traversal nu vă este cunoscut, considerați că înseamnă vizitarea fiecărui nod al copacului.) Ambele tipuri de traversări evidențiază modalități diferite de a interacționa cu un copac; ambele călătorii includ, în plus, utilizarea structurilor de date pe care le-am acoperit în această serie. DFS utilizează o stivă și BFS utilizează o coadă pentru a vizita nodurile. Asta e tare!
În domeniul informaticii, un arbore este o structură de date care simulează datele ierarhice cu noduri. Fiecare nod al unui arbore își păstrează propriile date și indicii către alte noduri.
Terminologia nodurilor și pointerilor poate fi nouă pentru unii cititori, așadar să le descriem mai departe cu o analogie. Să comparăm un copac cu o diagramă organizațională. Graficul are o poziție de nivel superior (nod rădăcină), cum ar fi CEO. Direct sub această poziție sunt alte poziții, cum ar fi vicepreședintele (VP).
Pentru a reprezenta această relație, folosim săgeți care indică de la CEO la un VP. O poziție, cum ar fi CEO-ul, este un nod; relația pe care o creăm de la un CEO la un VP este un indicator. Pentru a crea mai multe relații în schema organizațională, repetăm acest proces - avem un punct de nod în alt nod.
La nivel conceptual, sper că nodurile și indicii au sens. La nivel practic, putem beneficia de un exemplu mai tehnic. Să luăm în considerare DOM. Un DOM are un element ca poziție de nivel superior (nod rădăcină). Acest nod indică a element și a element. Acest proces este repetat pentru toate nodurile din DOM.
Una dintre frumusețile acestui design este capacitatea de a cuibui noduri: a elemente imbricate în interiorul acesteia; mai mult, fiecare element poate avea frate noduri. Este ciudat, dar amuzant și adevărat!
Deoarece fiecare arbore conține noduri, care pot fi un constructor separat dintr-un arbore, vom sublinia operațiile ambelor constructori: Nodul și Copac.
Accentsconagua
date stochează o valoare.mamă indică la părintele unui nod.copii puncte către următorul nod din listă._rădăcină indică nodul rădăcină al unui copac.traverseDF (callback) traversează nodurile unui copac cu DFS.traverseBF (callback) traversează nodurile unui copac cu BFS.conține (date, traversal) caută un nod dintr-un copac.adăugați (date, date, traversează) adaugă un nod unui copac.elimina (copil, părinte) elimină un nod într-un copac. Acum, să scriem codul pentru un copac!
Pentru implementarea noastră, vom defini mai întâi o funcție numită Nodul și apoi un constructor numit Copac.
funcția Nod (date) this.data = date; this.parent = null; this.children = [];
Fiecare instanță a nodului conține trei proprietăți: date, mamă, și copii. Prima proprietate deține datele asociate unui nod. A doua proprietate indică un nod. A treia proprietate indică mai multe noduri pentru copii.
Acum, să definim constructorul nostru Copac, care include Nodul constructor în definiția sa:
funcția Arbore (date) var node = nou Nod (date); this._root = nod;
Copac conține două linii de cod. Prima linie creează o nouă instanță de Nodul; a doua linie atribuie nodul ca rădăcină a unui copac.
Definițiile Copac și Nodul cere doar câteva linii de cod. Aceste linii, totuși, sunt suficiente pentru a ne ajuta să simulăm datele ierarhice. Pentru a dovedi acest punct, hai să folosim câteva exemple de date pentru a crea o instanță de Copac (și, indirect, Nodul).
var tree = copac nou (CEO); // date: "CEO", părinte: null, copii: [] tree._root;
Datorită existenței mamă și copii, putem adăuga noduri ca și copii ai lui _rădăcină și, de asemenea, alocați _rădăcină ca părinți ai acestor noduri. Cu alte cuvinte, putem simula crearea de date ierarhice.
Apoi, vom crea următoarele cinci metode:
Copac
traverseDF (callback)traverseBF (callback)conține (date, traversal)adăugați (copil, părinte)elimina (nod, părinte)Deoarece fiecare metodă a unui copac ne obligă să traversăm un copac, vom implementa mai întâi metode care definesc diferite tipuri de traversare a copacilor. (Traversarea unui copac este o modalitate formală de a spune vizitarea fiecărui nod al unui copac.)
1 din 5: traverseDF (callback)
Această metodă traversează un arbore cu căutare în profunzime.
Tree.prototype.traverseDF = funcția (callback) // aceasta este o funcție recurse și imediat invocată (funcția recurse (currentNode) // pasul 2 pentru (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) are un parametru numit suna inapoi. Dacă nu este clar din nume, suna inapoi se presupune a fi o funcție, care va fi numită mai târziu traverseDF (callback).
Corpul lui traverseDF (callback) include o altă funcție numită recurse. Această funcție este o funcție recursivă! Cu alte cuvinte, ea se invocă și se auto-învine. Utilizând pașii menționați în comentariile de la recurse, Voi descrie procesul general recurse utilizează pentru a traversa întregul copac.
Iată pașii:
recurse cu nodul rădăcină al unui arbore ca argument. În acest moment, currentNode indică spre nodul curent. pentru buclă și iterați o dată pentru fiecare copil din currentNode, începând cu primul copil. pentru buclă, invoca recurs cu un copil de currentNode. Copilul exact depinde de actuala repetare a lui pentru buclă. currentNode nu mai are copii, ieșim pentru buclă și invocați suna inapoi am trecut în timpul invocării traverseDF (callback). Etapele 2 (auto-terminare), 3 (auto-invocare) și 4 (apel invers) repetați până când traversăm fiecare nod al unui copac.
Recurgerea este un subiect foarte greu de învățat și necesită un întreg articol care să-i explice în mod adecvat. Deoarece explicația recursivității nu este punctul central al acestui articol - accentul este punerea în aplicare a unui copac - voi sugera că orice cititor care nu are o bună înțelegere a recursivității face următoarele două lucruri.
Mai întâi, experimentați cu implementarea noastră actuală de traverseDF (callback) și încercați să înțelegeți într-o anumită măsură cum funcționează. În al doilea rând, dacă vreți să scriu un articol despre recursivitate, vă rugăm să îl solicitați în comentariile acestui articol.
Următorul exemplu demonstrează modul în care ar fi traversat un copac traverseDF (callback). Pentru a traversa un copac, o voi crea în exemplul de mai jos. Abordarea pe care o voi folosi în acest moment nu este ideală, dar funcționează. O abordare mai bună ar fi utilizarea adaugă valoare), pe care o vom implementa la pasul 4 din 5.
var tree = copac nou ("unul"); tree._root.children.push (nou Nod ("două")); tree._root.children [0] .parent = copac; tree._root.children.push (nou Nod ("trei")); tree._root.children [1] .parent = copac; tree._root.children.push (nou Nod ("patru")); tree._root.children [2] .parent = copac; tree._root.children [0] .children.push (nou Nod ("cinci")); copac_root.children [0] .children [0] .parent = tree._root.children [0]; tree._root.children [0] .children.push (nou Nod ("șase")); tree._root.children [0] .children [1] .parent = tree._root.children [0]; tree._root.children [2] .children.push (nou Nod ("șapte")); tree._root.children [2] .children [0] .parent = tree._root.children [2]; / * creează acest arbore unu ─────────────────────────────────────────────────────────────────────────────────────────────────────────Acum, să invocăm traverseDF (callback).
tree.traverseDF (funcție (nod) console.log (node.data)); / * înregistrează următoarele șiruri de caractere la consola "cinci" șase "două" trei "șapte" patru "unul" * /
2 din 5: traverseBF (callback)
Această metodă utilizează o căutare la prima lățime pentru a traversa un copac.
Diferența dintre căutarea de adâncime și prima căutare de lățime-primă implică secvența pe care nodurile unui copac o vizitează. Pentru a ilustra acest punct, să folosim arborele din care am creat traverseDF (callback).
/ * un copac unul (adâncime: 0) ├───────────────────────────────────────────────────────────────────────────────────────────────────────────── patru (adâncime: 1) └──apte (adâncime: 2) * /
Acum, hai să trecem traverseBF (callback) același callback pe care l-am folosit traverseDF (callback).
tree.traverseBF (funcție (nod) console.log (node.data)); / * înregistrează următoarele șiruri de caractere la consola "unul" două "trei" patru "cinci" șase "șapte" * /
Buștenii din consola și diagrama arborelui nostru dezvăluie un model despre căutarea pe lățime. Începeți cu nodul rădăcină; apoi deplasați o adâncime și vizitați fiecare nod în acea adâncime de la stânga la dreapta. Repetați acest proces până când nu mai aveți adâncimi de parcurs.
De vreme ce avem un model conceptual de căutare la prima lățime, să punem acum în aplicare codul care ar face ca exemplul nostru să funcționeze.
Tree.prototype.traverseBF = funcția (callback) var queue = noua coadă (); queue.enqueue (this._root); curentTree = queue.dequeue (); în timp ce (currentTree) pentru (var i = 0, length = currentTree.children.length; i < length; i++) queue.enqueue(currentTree.children[i]); callback(currentTree); currentTree = queue.dequeue(); ;
Definiția noastră de traverseBF (callback) conține o mulțime de logică. Din acest motiv, voi explica logica în pași maniabili:
Coadă.traverseBF (callback) la instanța lui Coadă. currentNode și inițializați-l la nodul tocmai am adăugat la coada noastră. currentNode indică un nod, execută codul în interiorul lui in timp ce buclă. pentru buclă pentru a itera asupra copiilor din currentNode.pentru bucla, adăugați fiecare copil la coadă. currentNode și treci ca un argument al lui suna inapoi. currentNode la nodul care este eliminat din coadă. currentNode nu indică un nod - fiecare nod din copac a fost vizitat - repetați pașii 4 până la 8.3 din 5: conține (apel invers, traversal)
Să definim o metodă care ne va permite să căutăm o anumită valoare în arborele nostru. Pentru a utiliza oricare dintre metodele noastre de traversare a copacilor, am definit conține (apel invers, traversal) să accepte două argumente: datele de căutare și tipul traversalului.
Tree.prototype.contains = funcție (apel invers, traversal) traversal.call (acest lucru, apel invers); ;
În corpul lui conține (apel invers, traversal), folosim o metodă numită apel a trece acest și suna inapoi. Primul argument se leagă traversarea la pomul care a invocat conține (apel invers, traversal); al doilea argument este o funcție invocată pe fiecare nod din arborele nostru.
Imaginați-vă că vrem să conectăm la consola orice nod care conține date cu un număr impar și să traverseze fiecare nod din arborele nostru cu BFS. Acesta este codul pe care îl scriem:
// arborele este un exemplu de nod rădăcină tree.contains (funcția (node) if (node.data === 'două') console.log (node);, tree.traverseBF);
4 din 5: adăugați (date, date, traversal)
Acum avem o metodă de căutare a unui nod specific în arborele nostru. Să definim acum o metodă care ne va permite să adăugăm un nod unui anumit nod.
Tree.prototype.add = funcție (date, toData, traversal) var copil = nou Nod (date), parent = null, callback = funcția (node) if (node.data === toData) parent = node; ; acest lucru conține (apel invers, traversal); dacă (părinte) parent.children.push (copil); child.parent = părinte; altceva arunca o eroare nouă ("Nu se poate adăuga un nod la un părinte inexistent"); ;adăugați (date, date, traversal) definește trei parametri. Primul parametru, date, este folosit pentru a crea o nouă instanță de Nodul. Al doilea parametru, toData, este folosit pentru a compara cu fiecare nod dintr-un copac. Al treilea parametru, traversarea, este tipul de traversal arbore utilizat în această metodă.
În corpul lui adăugați (date, date, traversal), noi declarăm trei variabile. Prima variabilă, copil, este inițializată ca o nouă instanță de Nodul. A doua variabilă, mamă, este inițializată ca nul; dar va indica mai târziu la orice nod dintr-un arbore care se potrivește cu valoarea lui toData. Repartizarea mamă se întâmplă în a treia variabilă pe care o declarăm, adică suna inapoi.
suna inapoi este o funcție care se compară toData la fiecare nod date proprietate. În cazul în care dacă declarația se evaluează la Adevărat, atunci mamă este atribuită nodului care a corespuns comparației din dacă afirmație.
Comparația efectivă a fiecărui nod cu toData se întâmplă în conține (apel invers, traversal). Tipul de traverse și suna inapoi trebuie să fie transmisă ca argumente ale lui conține (apel invers, traversal).
În cele din urmă, dacă mamă există în copac, împingem copil în parent.children; noi atribuim și noi mamă la părintele lui copil. Altfel, aruncăm o eroare.
Să folosim adăugați (date, date, traversal) într-un exemplu:
var tree = copac nou (CEO); tree.add ("VP de fericire", "CEO", tree.traverseBF); / * copacul nostru "CEO" └─────────Iată un exemplu mai complex adăugați (addData, toData, traversal):
var tree = copac nou (CEO); tree.add ("VP de fericire", "CEO", tree.traverseBF); tree.add ("VP de finanțe", "CEO", tree.traverseBF); tree.add ("VP de tristețe", "CEO", tree.traverseBF); tree.add ("Directorul Puppies", "VP of Finance", tree.traverseBF); tree.add ("Managerul Puppies", "Directorul Puppies", tree.traverseBF); / * Copac 'CEO' ├── 'VP of Happiness' ├── 'VP de Finanțe' │ ├── 'Director al Cățeluși' │ └── 'Managerul Cățeluși' └── 'VP tristeții' * /5 din 5: eliminați (date, de la Data, traversal)
Pentru a finaliza implementarea noastră de Copac, vom adăuga o metodă numită eliminați (date, de la Data, traversal). Similar cu eliminarea unui nod din DOM, această metodă va elimina un nod și toți copiii acestuia.
Tree.prototype.remove = funcția (date, dinData, traversal) var tree = aceasta, parent = null, childToRemove = null, index; var callback = funcția (nodul) if (node.data === fromData) parent = node; ; acest lucru conține (apel invers, traversal); dacă (părinte) index = findIndex (parent.children, data); if (index === undefined) arunca o eroare nouă ("Nodul de eliminat nu există"); altfel childToRemove = parent.children.splice (index, 1); altfel arunca o eroare nouă ("Parent nu există."); return childToRemove; ;Similar cu adăugați (date, date, traversal), elimina traverses un copac pentru a găsi un nod care conține al doilea argument, care este acum fromData. Dacă se găsește acest nod, atunci mamă arată spre el.
În acest moment, ajungem la primul nostru dacă afirmație. Dacă mamă nu există, aruncăm o eroare. Dacă mamă există, invocăm findIndex () cu parent.children și datele pe care dorim să le eliminăm din nodurile copiilor din mamă. (findIndex () este o metodă de ajutor pe care am definit-o mai jos.)
funcția findIndex (arr, date) var index; pentru (var i = 0; i < arr.length; i++) if (arr[i].data === data) index = i; return index;
Interior findIndex (), apare următoarea logică. Dacă unul din noduri din parent.children conține date care se potrivesc date, variabila index i se atribuie un număr întreg. Dacă nu se potrivește niciunul dintre proprietățile de date ale copiilor date, atunci index își păstrează valoarea implicită nedefinit. Pe ultima linie din findIndex (), ne intoarcem index.
Acum ne întoarcem eliminați (date, de la Data, traversal). Dacă index este nedefinit, o eroare este aruncată. Dacă index este definit, îl folosim pentru a uni nodul pe care dorim să îl eliminăm de la copiii lui mamă; îi atribuim și copilul eliminat childToRemove.
În cele din urmă, ne întoarcem childToRemove.
Implementarea noastră de Copac este complet. Aruncă o privire - am realizat foarte mult:
funcția Nod (date) this.data = date; this.parent = null; this.children = []; funcția Tree (date) var node = nou Nod (date); this._root = nod; Tree.prototype.traverseDF = functie (callback) // aceasta este o functie recurse si imediat invocatoare (function recurse (currentNode) // pasul 2 pentru (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; Copacii simulează date ierarhice. O mare parte din lumea din jurul nostru se aseamănă cu acest tip de ierarhie, cum ar fi paginile web și familiile noastre. Ori de câte ori vă aflați în nevoie de structurare a datelor cu ierarhie, luați în considerare utilizarea unui copac.
