摘要:遍歷樹是訪問樹的每個節(jié)點的正式方式。想象一下,我們要將包含奇數(shù)數(shù)據(jù)的任何節(jié)點記錄到控制臺,并使用遍歷樹中的每個節(jié)點。第三個參數(shù),是這個方法中用來遍歷樹的類型。與類似,移除將遍歷樹以查找包含第二個參數(shù)的節(jié)點,現(xiàn)在為。
翻譯:瘋狂的技術(shù)宅
英文:https://code.tutsplus.com/art...
說明:本文翻譯自系列文章《Data Structures With JavaScript》,總共為四篇,原作者是在美國硅谷工作的工程師 Cho S. Kim。這是本系列的第四篇。
說明:本專欄文章首發(fā)于公眾號:jingchengyideng 。
樹是 web 開發(fā)中最常用的數(shù)據(jù)結(jié)構(gòu)之一。 這種說法對開發(fā)者和用戶都是正確的。每個編寫HTML的開發(fā)者,只要把網(wǎng)頁載入瀏覽器就會創(chuàng)建一個樹,樹通常被稱為文檔對象模型(DOM)。相應(yīng)地,每個在互聯(lián)網(wǎng)上瀏覽信息的人,也都是以DOM樹的形式接受信息。 每個編寫HTML并且將其加載到Web瀏覽器的Web開發(fā)人員都創(chuàng)建了一個樹,這被稱為文檔對象模型(DOM)。互聯(lián)網(wǎng)上的所有用戶,在獲取信息時,都是以樹的形式收——即DOM。
現(xiàn)在,高潮來了:你正在讀的本文在瀏覽器中就是以樹的形式進(jìn)行渲染的。文字由
元素進(jìn)行表示;
元素又嵌套在元素中;元素又嵌套在元素中。 您正在閱讀的段落表示為
元素中的文本;
元素嵌套在元素中;元素嵌套在元素中。
這些嵌套數(shù)據(jù)和家族數(shù)類似。
又是的子元素 如果這個比喻對你有點用的話,你將會發(fā)現(xiàn)在我們介紹樹的時候會用到更多的類比。
在本文中,我們將會通過兩種不同的遍歷方式來創(chuàng)建一個樹:深度優(yōu)先(DFS)和廣度優(yōu)先(BFS)。 (如果你對遍歷這個詞感到比較陌生,不妨將他想象成訪問樹中的每一個節(jié)點。) 這兩種類型的遍歷強調(diào)了與樹交互的不同方式, DFS和BFS分別用棧和隊列來訪問節(jié)點。 這聽起來很酷!
樹(深度搜索和廣度搜索)在計算機科學(xué)中,樹是一種用節(jié)點來模擬分層數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。每個樹節(jié)點都包含他本身的數(shù)據(jù)及指向其他節(jié)點的指針。
節(jié)點和指針這些術(shù)語可能對一些讀者來說比較陌生,所以讓我們用類比來進(jìn)一步描述他們。 讓我們將樹與組織圖結(jié)構(gòu)圖進(jìn)行比較。 這個結(jié)構(gòu)圖有一個頂級位置(根節(jié)點),比如CEO。 在這個節(jié)點下面還有一些其他的節(jié)點,比如副總裁(VP)。
為了表示這種關(guān)系,我們用箭頭從CEO指向VP。 一個位置,比如CEO,是一個節(jié)點;我們創(chuàng)建的CEO到VP的關(guān)系是一個指針。 在我們的組織結(jié)構(gòu)圖中去創(chuàng)建更多的關(guān)系,我們只要重復(fù)這些步驟即可---我們讓一個節(jié)點指向另一個節(jié)點。
在概念層次上,我希望節(jié)點和指針有意義。 在實際中,我們能從更科學(xué)的實例中獲取收益。 讓我們來思考DOM。 DOM有元素作為其頂級位置(根節(jié)點)。 這個節(jié)點指向元素和元素。 這些步驟在DOM的所有節(jié)點中重復(fù)。
這種設(shè)計的一個優(yōu)點是能夠嵌套節(jié)點:例如:一個元素能夠包含很多個元素;此外,每個元素能擁有兄弟元素。這很怪異,但是確實真實有趣!
由于每個樹都包含節(jié)點,其可以是來自樹的多帶帶構(gòu)造器,我們將概述兩個構(gòu)造函數(shù)的操作:Node和Tree
節(jié)點data 存儲值。
parent 指向節(jié)點的父節(jié)點。
children 指向列表中的下一個節(jié)點。
樹_root 指向一個樹的根節(jié)點。
traverseDF(callback) 對樹進(jìn)行DFS遍歷。
traverseBF(callback) 對樹進(jìn)行BFS遍歷。
contains(data, traversal) 搜索樹中的節(jié)點。
add(data, toData, traverse) 向樹中添加節(jié)點。
remove(child, parent) 移除樹中的節(jié)點。
實現(xiàn)樹現(xiàn)在開始寫樹的代碼!
節(jié)點的屬性在實現(xiàn)中,我們首先定義一個叫做Node的函數(shù),然后構(gòu)造一個Tree。
function Node(data) { this.data = data; this.parent = null; this.children = []; }
每一個Node的實例都包含三個屬性:data,parant,和children。 第一個屬性保存與節(jié)點相關(guān)聯(lián)的數(shù)據(jù)。 第二個屬性指向一個節(jié)點。 第三個屬性指向許多子節(jié)點。
樹的屬性現(xiàn)在讓我們來定義Tree的構(gòu)造函數(shù),其中包括Node構(gòu)造函數(shù)的定義:
function Tree(data) { var node = new Node(data); this._root = node; }
Tree包含兩行代碼。 第一行創(chuàng)建了一個Node的新實例;第二行讓node等于樹的根節(jié)點。
Tree和Node的定義只需要幾行代碼。 但是,通過這幾行足以幫助我們模擬分層數(shù)據(jù)。 為了證明這一點,讓我們用一些示例數(shù)據(jù)去創(chuàng)建Tree的示例(和間接的Node)。
var tree = new Tree("CEO"); // {data: "CEO", parent: null, children: []} tree._root;
幸好有parent和children的存在,我們可以為_root添加子節(jié)點和讓這些子節(jié)點的父節(jié)點等于_root。 換一種說法,我們可以模擬分層數(shù)據(jù)的創(chuàng)建。
Tree的方法接下來我們將要創(chuàng)建以下五種方法。
樹traverseDF(callback)
traverseBF(callback)
contains(data, traversal)
add(child, parent)
remove(node, parent)
因為每種方法都需要遍歷一個樹,所以我們首先要實現(xiàn)一個方法去定義不同的樹遍歷。 (遍歷樹是訪問樹的每個節(jié)點的正式方式。)
方法1/5: traverseDF(callback)這種方法以深度優(yōu)先方式遍歷樹。
Tree.prototype.traverseDF = function(callback) { // this is a recurse and immediately-invoking function (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)有一個參數(shù)callback。 如果對這個名字不明白,callback被假定是一個函數(shù),將在后面被traverseDF(callback)調(diào)用。
traverseDF(callback)的函數(shù)體含有另一個叫做recurse的函數(shù)。 這個函數(shù)是一個遞歸函數(shù)! 換句話說,它是自我調(diào)用和自我終止。 使用recurse的注釋中提到的步驟,我將描述遞歸用來recurse整個樹的一般過程。
這里是步驟:
立即使用樹的根節(jié)點作為其參數(shù)調(diào)用recurse。 此時,currentNode指向當(dāng)前節(jié)點。
進(jìn)入for循環(huán)并且從第一個子節(jié)點開始,每一個子節(jié)點都迭代一次currentNode函數(shù)。
在for循環(huán)體內(nèi),使用currentNode的子元素調(diào)用遞歸。 確切的子節(jié)點取決于當(dāng)前for循環(huán)的當(dāng)前迭代。
當(dāng)currentNode不存在子節(jié)點時,我們退出for循環(huán)并callback我們在調(diào)用traverseDF(callback)期間傳遞的回調(diào)。
步驟2(自終止),3(自調(diào)用)和4(回調(diào))重復(fù),直到我們遍歷樹的每個節(jié)點。
遞歸是一個非常困難的話題,需要一個完整的文章來充分解釋它。由于遞歸的解釋不是本文的重點 —— 重點是實現(xiàn)一棵樹 —— 我建議任何讀者沒有很好地掌握遞歸做以下兩件事。
首先,實驗我們當(dāng)前的traverseDF(callback)實現(xiàn),并嘗試一定程度上理解它是如何工作的。 第二,如果你想要我寫一篇關(guān)于遞歸的文章,那么請在本文的評論中請求它。
以下示例演示如何使用traverseDF(callback)遍歷樹。要遍歷樹,我將在下面的示例中創(chuàng)建一個。我現(xiàn)在使用的方法不是罪理想的,但它能很好的工作。 一個更好的方法是使用add(value),我們將在第4步和第5步中實現(xiàn)。
var tree = new Tree("one"); 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]; /* creates this tree one ├── two │ ├── five │ └── six ├── three └── four └── seven */
現(xiàn)在,讓我們調(diào)用traverseDF(callback)。
tree.traverseDF(function(node) { console.log(node.data) }); /* logs the following strings to the console "five" "six" "two" "three" "seven" "four" "one" */方法2/5: traverseBF(callback)
這個方法使用深度優(yōu)先搜索去遍歷樹
深度優(yōu)先搜索和廣度優(yōu)先搜索之間的差別涉及樹的節(jié)點訪問的序列。 為了說明這一點,讓我們使用traverseDF(callback)創(chuàng)建的樹。
/* tree one (depth: 0) ├── two (depth: 1) │ ├── five (depth: 2) │ └── six (depth: 2) ├── three (depth: 1) └── four (depth: 1) └── seven (depth: 2) */
現(xiàn)在,讓我們傳遞traverseBF(callback)和我們用于traverseDF(callback)的回調(diào)。
tree.traverseBF(function(node) { console.log(node.data) }); /* logs the following strings to the console "one" "two" "three" "four" "five" "six" "seven" */
來自控制臺的日志和我們的樹的圖顯示了關(guān)于廣度優(yōu)先搜索的模式。從根節(jié)點開始;然后行進(jìn)一個深度并訪問該深度從左到右的每個節(jié)點。重復(fù)此過程,直到?jīng)]有更多的深度要移動。
由于我們有一個廣度優(yōu)先搜索的概念模型,現(xiàn)在讓我們實現(xiàn)使我們的示例工作的代碼。
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(); } };
我們對traverseBF(callback)的定義包含了很多邏輯。 因此,我會用下面的步驟解釋這些邏輯:
創(chuàng)建 Queue的實例。
調(diào)用traverseBF(callback)產(chǎn)生的節(jié)點添加到Queue的實例。
定義一個變量currentNode并且將其值初始化為剛才添加到隊列里的node
當(dāng)currentNode指向一個節(jié)點時,執(zhí)行wille循環(huán)里面的代碼。
用for循環(huán)去迭代currentNode的子節(jié)點。
在for循環(huán)體內(nèi),將每個子元素加入隊列。
獲取currentNode并將其作為callback的參數(shù)傳遞。
將currentNode重新分配給正從隊列中刪除的節(jié)點。
直到currentNode不再指向任何節(jié)點——也就是說樹中的每個節(jié)點都訪問過了——重復(fù)4-8步。
方法3/5 contains(callback, traversal)讓我們定義一個方法,可以在樹中搜索一個特定的值。去使用我們創(chuàng)建的任意一種樹的遍歷方法,我們已經(jīng)定義了contains(callback, traversal)接收兩個參數(shù):搜索的數(shù)據(jù)和遍歷的類型。
Tree.prototype.contains = function(callback, traversal) { traversal.call(this, callback); };
在contains(callback, traversal)函數(shù)體內(nèi),我們用call方法去傳遞this和callback。 第一個參數(shù)將traversal綁定到被調(diào)用的樹contains(callback,traversal);第二個參數(shù)是在樹中每個節(jié)點上調(diào)用的函數(shù)。
想象一下,我們要將包含奇數(shù)數(shù)據(jù)的任何節(jié)點記錄到控制臺,并使用BFS遍歷樹中的每個節(jié)點。 我們可以這么寫代碼:
// tree is an example of a root node tree.contains(function(node){ if (node.data === "two") { console.log(node); } }, tree.traverseBF); add(data, toData, traversal)方法4/5: add(data, toData, traversal)
現(xiàn)在有了一個可以搜索樹中特定節(jié)點的方法。 讓我們定義一個允許向指定節(jié)點添加節(jié)點的方法。
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."); } };
add(data, toData, traversal)定義了三個參數(shù)。 第一個參數(shù)data用來創(chuàng)建一個Node的新實例。 第二個參數(shù)toData用來比較樹中的每個節(jié)點。 第三個參數(shù)traversal,是這個方法中用來遍歷樹的類型。
在add(data, toData, traversal)函數(shù)體內(nèi),我們聲明了三個變量。 第一個變量child代表初始化的Node實例。 第二個變量parent初始化為null;但是將來會指向匹配toData值的樹中的任意節(jié)點。parent的重新分配發(fā)生在我們聲明的第三個變量,這就是callback。
callback是一個將toData和每一個節(jié)點的data屬性做比較的函數(shù)。 如果if語句的值是true,那么parent將被賦值給if語句中匹配比較的節(jié)點。
每個節(jié)點的toData在contains(callback, traversal)中進(jìn)行比較。遍歷類型和callback必須作為contains(callback, traversal)的參數(shù)進(jìn)行傳遞。
最后,如果parent不存在于樹中,我們將child推入parent.children; 同時也要將parent賦值給child的父級。否則,將拋出錯誤。
讓我們用add(data, toData, traversal)做個例子:
var tree = new Tree("CEO"); tree.add("VP of Happiness", "CEO", tree.traverseBF); /* our tree "CEO" └── "VP of Happiness" */
這里是add(addData, toData, traversal)的更加復(fù)雜的例子:
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/5:remove(data, fromData, traversal)
為了完成Tree的實現(xiàn),我們將添加一個叫做remove(data, fromData, traversal)的方法。 跟從DOM里面移除節(jié)點類似,這個方法將移除一個節(jié)點和他的所有子級。
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; };
與add(data, toData, traversal)類似,移除將遍歷樹以查找包含第二個參數(shù)的節(jié)點,現(xiàn)在為fromData。 如果這個節(jié)點被發(fā)現(xiàn)了,那么parent將指向它。
在這時候,我們到達(dá)了第一個if語句。 如果parent不存在,將拋出錯誤。 如果parent不存在,我們使用parent.children調(diào)用findIndex()和我們要從parent節(jié)點的子節(jié)點中刪除的數(shù)據(jù) (findIndex()是一個幫助方法,我將在下面定義。)
function findIndex(arr, data) { var index; for (var i = 0; i < arr.length; i++) { if (arr[i].data === data) { index = i; } } return index; }
在findIndex()里面,以下邏輯將發(fā)生。 如果parent.children中的任意一個節(jié)點包含匹配data值的數(shù)據(jù),那么變量index賦值為一個整數(shù)。 如果沒有子級的數(shù)值屬性匹配data,那么index保留他的默認(rèn)值undefined。 在最后一行的findIndex()方法,我們返回一個index。
我們現(xiàn)在去remove(data, fromData, traversal) 如果index的值是undefined,將會拋出錯誤。 如果index的值存在,我們用它來拼接我們想從parent的子節(jié)點中刪除的節(jié)點。同樣我們給刪除的子級賦值為childToRemove。
最后,我們返回childToRemove。
樹的的完整實現(xiàn)到此為止Tree已經(jīng)完全實現(xiàn)?;剡^頭看看,我們到底完成了多少工作:
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) { // this is a recurse and immediately-invoking function (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; }總結(jié)
樹可以用來模擬分層數(shù)據(jù)。我們周圍有許多類似這種類型的層次結(jié)構(gòu),例如網(wǎng)頁和族譜。當(dāng)你發(fā)現(xiàn)自己需要使用層次結(jié)構(gòu)來結(jié)構(gòu)化數(shù)據(jù)時,可以考慮使用樹。
歡迎掃描二維碼關(guān)注公眾號,每天推送我翻譯的技術(shù)文章。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/84410.html
摘要:樹可謂是開發(fā)者最常碰到的數(shù)據(jù)結(jié)構(gòu)之一了要知道整張網(wǎng)頁就是一棵樹啊所以我們就來學(xué)習(xí)樹這一數(shù)據(jù)結(jié)構(gòu)吧在這篇文章中我們將創(chuàng)建一棵樹并且用兩種不同的方法來遍歷它深度優(yōu)先遍歷和寬度廣度優(yōu)先遍歷方法使用借助棧這一數(shù)據(jù)結(jié)構(gòu)來訪問樹的每個節(jié)點則借助了隊 樹可謂是web開發(fā)者最常碰到的數(shù)據(jù)結(jié)構(gòu)之一了. 要知道, 整張網(wǎng)頁就是一棵DOM樹啊 (Document Object Model ). 所以我...
摘要:值得注意的是,谷歌瀏覽器和大多數(shù)瀏覽器不同,每一個選項卡都是渲染引擎的一個實例,都擁有獨立的進(jìn)程。組件之間的通信火狐和谷歌都發(fā)展了一個特殊的通信結(jié)構(gòu),后面我們將會單獨來講。渲染引擎我們所討論的幾款瀏覽器火狐谷歌都是基于兩種渲染引擎建立的。 寫在前面 這篇文章是一篇譯文,年代有點久,部分內(nèi)容有過時,請讀者仔細(xì)閱讀,翻譯自How browser work,原文地址為點擊這里查看原文 簡介 ...
摘要:屏幕的變化就被稱為或者是。而瀏覽器的目標(biāo)之一就是減少以及的負(fù)面影響,其中的一個策略就是干脆不做,又或者說至少不是現(xiàn)在做。但有時腳本語句會破化瀏覽器優(yōu)化,并使其刷新隊列以及執(zhí)行所有批處理的改變。 **首先說翻譯這篇文章的目的其實是,之前回答的關(guān)于瀏覽器js渲染的問題被打臉了 ?_? ,不得不正視自己半路出家學(xué)前端的事實,所以這篇文章就算是自己的一個筆記吧,學(xué)而時習(xí)之,不亦樂乎,翻譯錯了,...
摘要:屏幕的變化就被稱為或者是。而瀏覽器的目標(biāo)之一就是減少以及的負(fù)面影響,其中的一個策略就是干脆不做,又或者說至少不是現(xiàn)在做。但有時腳本語句會破化瀏覽器優(yōu)化,并使其刷新隊列以及執(zhí)行所有批處理的改變。 **首先說翻譯這篇文章的目的其實是,之前回答的關(guān)于瀏覽器js渲染的問題被打臉了 ?_? ,不得不正視自己半路出家學(xué)前端的事實,所以這篇文章就算是自己的一個筆記吧,學(xué)而時習(xí)之,不亦樂乎,翻譯錯了,...
摘要:屏幕的變化就被稱為或者是。而瀏覽器的目標(biāo)之一就是減少以及的負(fù)面影響,其中的一個策略就是干脆不做,又或者說至少不是現(xiàn)在做。但有時腳本語句會破化瀏覽器優(yōu)化,并使其刷新隊列以及執(zhí)行所有批處理的改變。 **首先說翻譯這篇文章的目的其實是,之前回答的關(guān)于瀏覽器js渲染的問題被打臉了 ?_? ,不得不正視自己半路出家學(xué)前端的事實,所以這篇文章就算是自己的一個筆記吧,學(xué)而時習(xí)之,不亦樂乎,翻譯錯了,...
閱讀 1891·2021-09-24 09:48
閱讀 3236·2021-08-26 14:14
閱讀 1692·2021-08-20 09:36
閱讀 1480·2019-08-30 15:55
閱讀 3642·2019-08-26 17:15
閱讀 1438·2019-08-26 12:09
閱讀 618·2019-08-26 11:59
閱讀 3335·2019-08-26 11:57