【譯】JavaScript數據結構（4）：樹

Keagan 發布于2019-08-20 18:22 / 2610人閱讀

摘要：遍歷樹是訪問樹的每個節點的正式方式。想象一下，我們要將包含奇數數據的任何節點記錄到控制臺，并使用遍歷樹中的每個節點。第三個參數，是這個方法中用來遍歷樹的類型。與類似，移除將遍歷樹以查找包含第二個參數的節點，現在為。

翻譯：瘋狂的技術宅
英文：https://code.tutsplus.com/art...
說明：本文翻譯自系列文章《Data Structures With JavaScript》，總共為四篇，原作者是在美國硅谷工作的工程師 Cho S. Kim。這是本系列的第四篇。

說明：本專欄文章首發于公眾號：jingchengyideng 。

樹是 web 開發中最常用的數據結構之一。這種說法對開發者和用戶都是正確的。每個編寫HTML的開發者，只要把網頁載入瀏覽器就會創建一個樹，樹通常被稱為文檔對象模型（DOM）。相應地，每個在互聯網上瀏覽信息的人，也都是以DOM樹的形式接受信息。每個編寫HTML并且將其加載到Web瀏覽器的Web開發人員都創建了一個樹，這被稱為文檔對象模型（DOM）。互聯網上的所有用戶，在獲取信息時，都是以樹的形式收——即DOM。

現在，高潮來了：你正在讀的本文在瀏覽器中就是以樹的形式進行渲染的。文字由

元素進行表示；

元素又嵌套在元素中；元素又嵌套在元素中。您正在閱讀的段落表示為

元素中的文本；

元素嵌套在元素中；元素嵌套在元素中。

這些嵌套數據和家族數類似。是父元素，是子元素，

又是的子元素如果這個比喻對你有點用的話，你將會發現在我們介紹樹的時候會用到更多的類比。

在本文中，我們將會通過兩種不同的遍歷方式來創建一個樹：深度優先(DFS)和廣度優先(BFS)。（如果你對遍歷這個詞感到比較陌生，不妨將他想象成訪問樹中的每一個節點。）這兩種類型的遍歷強調了與樹交互的不同方式， DFS和BFS分別用棧和隊列來訪問節點。這聽起來很酷！

樹（深度搜索和廣度搜索）

在計算機科學中，樹是一種用節點來模擬分層數據的數據結構。每個樹節點都包含他本身的數據及指向其他節點的指針。

節點和指針這些術語可能對一些讀者來說比較陌生，所以讓我們用類比來進一步描述他們。讓我們將樹與組織圖結構圖進行比較。這個結構圖有一個頂級位置（根節點），比如CEO。在這個節點下面還有一些其他的節點，比如副總裁(VP)。

為了表示這種關系，我們用箭頭從CEO指向VP。一個位置，比如CEO，是一個節點；我們創建的CEO到VP的關系是一個指針。在我們的組織結構圖中去創建更多的關系，我們只要重復這些步驟即可---我們讓一個節點指向另一個節點。

在概念層次上，我希望節點和指針有意義。在實際中，我們能從更科學的實例中獲取收益。讓我們來思考DOM。 DOM有元素作為其頂級位置（根節點）。這個節點指向元素和元素。這些步驟在DOM的所有節點中重復。

這種設計的一個優點是能夠嵌套節點：例如：一個

元素；此外，每個
元素能擁有兄弟
元素。這很怪異，但是確實真實有趣！
操作樹
由于每個樹都包含節點，其可以是來自樹的多帶帶構造器，我們將概述兩個構造函數的操作：Node和Tree
節點
data 存儲值。

parent 指向節點的父節點。

children 指向列表中的下一個節點。
樹
_root 指向一個樹的根節點。

traverseDF(callback) 對樹進行DFS遍歷。

traverseBF(callback) 對樹進行BFS遍歷。

contains(data, traversal) 搜索樹中的節點。

add(data, toData, traverse) 向樹中添加節點。

remove(child, parent) 移除樹中的節點。
實現樹
現在開始寫樹的代碼！
節點的屬性
在實現中，我們首先定義一個叫做Node的函數，然后構造一個Tree。
```
function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}
```
每一個Node的實例都包含三個屬性：data，parant，和children。第一個屬性保存與節點相關聯的數據。第二個屬性指向一個節點。第三個屬性指向許多子節點。
樹的屬性
現在讓我們來定義Tree的構造函數，其中包括Node構造函數的定義：
```
function Tree(data) {
    var node = new Node(data);
    this._root = node;
}
```
Tree包含兩行代碼。第一行創建了一個Node的新實例；第二行讓node等于樹的根節點。

Tree和Node的定義只需要幾行代碼。但是，通過這幾行足以幫助我們模擬分層數據。為了證明這一點，讓我們用一些示例數據去創建Tree的示例（和間接的Node）。
```
var tree = new Tree("CEO");
 
// {data: "CEO", parent: null, children: []}
tree._root;
```
幸好有parent和children的存在，我們可以為_root添加子節點和讓這些子節點的父節點等于_root。換一種說法，我們可以模擬分層數據的創建。
Tree的方法
接下來我們將要創建以下五種方法。
樹
traverseDF(callback)

traverseBF(callback)

contains(data, traversal)

add(child, parent)

remove(node, parent)

因為每種方法都需要遍歷一個樹，所以我們首先要實現一個方法去定義不同的樹遍歷。（遍歷樹是訪問樹的每個節點的正式方式。）
方法1/5: traverseDF(callback)
這種方法以深度優先方式遍歷樹。
```
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)有一個參數callback。如果對這個名字不明白，callback被假定是一個函數，將在后面被traverseDF(callback)調用。

traverseDF(callback)的函數體含有另一個叫做recurse的函數。這個函數是一個遞歸函數！換句話說，它是自我調用和自我終止。使用recurse的注釋中提到的步驟，我將描述遞歸用來recurse整個樹的一般過程。

這里是步驟：

立即使用樹的根節點作為其參數調用recurse。此時，currentNode指向當前節點。

進入for循環并且從第一個子節點開始，每一個子節點都迭代一次currentNode函數。

在for循環體內，使用currentNode的子元素調用遞歸。確切的子節點取決于當前for循環的當前迭代。

當currentNode不存在子節點時，我們退出for循環并callback我們在調用traverseDF（callback）期間傳遞的回調。

步驟2（自終止），3（自調用）和4（回調）重復，直到我們遍歷樹的每個節點。

遞歸是一個非常困難的話題，需要一個完整的文章來充分解釋它。由于遞歸的解釋不是本文的重點 —— 重點是實現一棵樹 —— 我建議任何讀者沒有很好地掌握遞歸做以下兩件事。

首先，實驗我們當前的traverseDF(callback)實現，并嘗試一定程度上理解它是如何工作的。第二，如果你想要我寫一篇關于遞歸的文章，那么請在本文的評論中請求它。

以下示例演示如何使用traverseDF(callback)遍歷樹。要遍歷樹，我將在下面的示例中創建一個。我現在使用的方法不是罪理想的，但它能很好的工作。一個更好的方法是使用add(value)，我們將在第4步和第5步中實現。
```
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
 
*/
```
現在，讓我們調用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)
這個方法使用深度優先搜索去遍歷樹

深度優先搜索和廣度優先搜索之間的差別涉及樹的節點訪問的序列。為了說明這一點，讓我們使用traverseDF(callback)創建的樹。
```
/* 
 tree
 
 one (depth: 0)
 ├── two (depth: 1)
 │   ├── five (depth: 2)
 │   └── six (depth: 2)
 ├── three (depth: 1)
 └── four (depth: 1)
     └── seven (depth: 2)
 */
```
現在，讓我們傳遞traverseBF(callback)和我們用于traverseDF（callback）的回調。
```
tree.traverseBF(function(node) {
    console.log(node.data)
});
 
/*
 
logs the following strings to the console
 
"one"
"two"
"three"
"four"
"five"
"six"
"seven"
 
*/
```
來自控制臺的日志和我們的樹的圖顯示了關于廣度優先搜索的模式。從根節點開始；然后行進一個深度并訪問該深度從左到右的每個節點。重復此過程，直到沒有更多的深度要移動。

由于我們有一個廣度優先搜索的概念模型，現在讓我們實現使我們的示例工作的代碼。
```
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)的定義包含了很多邏輯。因此，我會用下面的步驟解釋這些邏輯：

創建 Queue的實例。

調用traverseBF(callback)產生的節點添加到Queue的實例。

定義一個變量currentNode并且將其值初始化為剛才添加到隊列里的node

當currentNode指向一個節點時，執行wille循環里面的代碼。

用for循環去迭代currentNode的子節點。

在for循環體內，將每個子元素加入隊列。

獲取currentNode并將其作為callback的參數傳遞。

將currentNode重新分配給正從隊列中刪除的節點。

直到currentNode不再指向任何節點——也就是說樹中的每個節點都訪問過了——重復4-8步。
方法3/5 contains(callback, traversal)
讓我們定義一個方法，可以在樹中搜索一個特定的值。去使用我們創建的任意一種樹的遍歷方法，我們已經定義了contains(callback, traversal)接收兩個參數：搜索的數據和遍歷的類型。
```
Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};
```
在contains(callback, traversal)函數體內，我們用call方法去傳遞this和callback。第一個參數將traversal綁定到被調用的樹contains（callback，traversal）；第二個參數是在樹中每個節點上調用的函數。

想象一下，我們要將包含奇數數據的任何節點記錄到控制臺，并使用BFS遍歷樹中的每個節點。我們可以這么寫代碼：
```
// 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)
現在有了一個可以搜索樹中特定節點的方法。讓我們定義一個允許向指定節點添加節點的方法。
```
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)定義了三個參數。第一個參數data用來創建一個Node的新實例。第二個參數toData用來比較樹中的每個節點。第三個參數traversal，是這個方法中用來遍歷樹的類型。

在add(data, toData, traversal)函數體內，我們聲明了三個變量。第一個變量child代表初始化的Node實例。第二個變量parent初始化為null；但是將來會指向匹配toData值的樹中的任意節點。parent的重新分配發生在我們聲明的第三個變量，這就是callback。

callback是一個將toData和每一個節點的data屬性做比較的函數。如果if語句的值是true，那么parent將被賦值給if語句中匹配比較的節點。

每個節點的toData在contains(callback, traversal)中進行比較。遍歷類型和callback必須作為contains(callback, traversal)的參數進行傳遞。

最后，如果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)的更加復雜的例子：
```
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的實現，我們將添加一個叫做remove(data, fromData, traversal)的方法。跟從DOM里面移除節點類似，這個方法將移除一個節點和他的所有子級。
```
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)類似，移除將遍歷樹以查找包含第二個參數的節點，現在為fromData。如果這個節點被發現了，那么parent將指向它。

在這時候，我們到達了第一個if語句。如果parent不存在，將拋出錯誤。如果parent不存在，我們使用parent.children調用findIndex（）和我們要從parent節點的子節點中刪除的數據（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()里面，以下邏輯將發生。如果parent.children中的任意一個節點包含匹配data值的數據,那么變量index賦值為一個整數。如果沒有子級的數值屬性匹配data，那么index保留他的默認值undefined。在最后一行的findIndex()方法，我們返回一個index。

我們現在去remove(data, fromData, traversal) 如果index的值是undefined，將會拋出錯誤。如果index的值存在，我們用它來拼接我們想從parent的子節點中刪除的節點。同樣我們給刪除的子級賦值為childToRemove。

最后，我們返回childToRemove。
樹的的完整實現
到此為止Tree已經完全實現。回過頭看看，我們到底完成了多少工作：
```
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;
}
```
總結
樹可以用來模擬分層數據。我們周圍有許多類似這種類型的層次結構，例如網頁和族譜。當你發現自己需要使用層次結構來結構化數據時，可以考慮使用樹。

歡迎掃描二維碼關注公眾號，每天推送我翻譯的技術文章。

云服務器 GPU云服務器樹結構樹結構數據存儲 linux下編譯阿里 linux下編譯運行

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/84410.html

用JavaScript來學習樹「譯」

摘要：樹可謂是開發者最常碰到的數據結構之一了要知道整張網頁就是一棵樹啊所以我們就來學習樹這一數據結構吧在這篇文章中我們將創建一棵樹并且用兩種不同的方法來遍歷它深度優先遍歷和寬度廣度優先遍歷方法使用借助棧這一數據結構來訪問樹的每個節點則借助了隊樹可謂是web開發者最常碰到的數據結構之一了. 要知道, 整張網頁就是一棵DOM樹啊 (Document Object Model ). 所以我...

Youngdze 2019-08-22 11:05 評論0 收藏0
瀏覽器工作過程詳解（譯）（一）

摘要：值得注意的是，谷歌瀏覽器和大多數瀏覽器不同，每一個選項卡都是渲染引擎的一個實例，都擁有獨立的進程。組件之間的通信火狐和谷歌都發展了一個特殊的通信結構，后面我們將會單獨來講。渲染引擎我們所討論的幾款瀏覽器火狐谷歌都是基于兩種渲染引擎建立的。寫在前面這篇文章是一篇譯文，年代有點久，部分內容有過時，請讀者仔細閱讀，翻譯自How browser work，原文地址為點擊這里查看原文簡介 ...

陳江龍 2019-08-20 15:51 評論0 收藏0
【譯】瀏覽器渲染：repaint,reflow/relayout,restyle

摘要：屏幕的變化就被稱為或者是。而瀏覽器的目標之一就是減少以及的負面影響，其中的一個策略就是干脆不做，又或者說至少不是現在做。但有時腳本語句會破化瀏覽器優化，并使其刷新隊列以及執行所有批處理的改變。 **首先說翻譯這篇文章的目的其實是，之前回答的關于瀏覽器js渲染的問題被打臉了 ?_? ，不得不正視自己半路出家學前端的事實，所以這篇文章就算是自己的一個筆記吧，學而時習之，不亦樂乎，翻譯錯了，...

godlong_X 2019-08-29 11:17 評論0 收藏0
【譯】瀏覽器渲染：repaint,reflow/relayout,restyle

摘要：屏幕的變化就被稱為或者是。而瀏覽器的目標之一就是減少以及的負面影響，其中的一個策略就是干脆不做，又或者說至少不是現在做。但有時腳本語句會破化瀏覽器優化，并使其刷新隊列以及執行所有批處理的改變。 **首先說翻譯這篇文章的目的其實是，之前回答的關于瀏覽器js渲染的問題被打臉了 ?_? ，不得不正視自己半路出家學前端的事實，所以這篇文章就算是自己的一個筆記吧，學而時習之，不亦樂乎，翻譯錯了，...

mating 2019-08-20 11:03 評論0 收藏0
【譯】瀏覽器渲染：repaint,reflow/relayout,restyle

摘要：屏幕的變化就被稱為或者是。而瀏覽器的目標之一就是減少以及的負面影響，其中的一個策略就是干脆不做，又或者說至少不是現在做。但有時腳本語句會破化瀏覽器優化，并使其刷新隊列以及執行所有批處理的改變。 **首先說翻譯這篇文章的目的其實是，之前回答的關于瀏覽器js渲染的問題被打臉了 ?_? ，不得不正視自己半路出家學前端的事實，所以這篇文章就算是自己的一個筆記吧，學而時習之，不亦樂乎，翻譯錯了，...

legendmohe 2019-08-01 15:44 評論0 收藏0