JavaScript數(shù)據(jù)結(jié)構(gòu)：樹

LeoHsiun 發(fā)布于2019-08-20 17:50 / 1192人閱讀

摘要：第二步自終止，第三步自調(diào)用，第四步回調(diào)函數(shù)會重復(fù)進行，直到我們遍歷到樹的所有節(jié)點。執(zhí)行回調(diào)函數(shù)，傳入賦值為第二層第二個子節(jié)點。

本文譯自Cho S. Kim的文章：Data Structures With JavaScript: Tree

“樹”，是web開發(fā)中最常用的數(shù)據(jù)結(jié)構(gòu)之一。這句話對開發(fā)者和用戶來講，都適用：開發(fā)人員通過HTML創(chuàng)造了一個DOM，用戶則通過DOM消費網(wǎng)絡(luò)信息。

進一步講，您正在閱讀的本文也是以樹的形式在瀏覽器中渲染的。文章中的段落由

標(biāo)簽中的文字所代表；

標(biāo)簽嵌套在元素中，而元素則是的子元素。

數(shù)據(jù)的嵌套類似一個家譜：元素是一個爹爹，元素是一個孩兒，

元素則是元素的孩兒。如果你感覺這種類比容易理解，那么在接下來實現(xiàn)一棵樹的過程中，更多的類比對你來說應(yīng)該也不成問題。

在本文中，我們將創(chuàng)建一顆有兩種遍歷方式的樹：Depth-First-Search(DFS)深度優(yōu)先搜索，和Breadth-First-Search(BFS)寬度優(yōu)先搜索（遍歷是指訪問樹的每一個節(jié)點）。這兩種遍歷方式各自強調(diào)了對一顆樹操作的不同姿勢；而且他們用到了我們之前提過的（ 沒翻，去找原文 ）數(shù)據(jù)結(jié)構(gòu)：DFS用到了棧，BFS用到了隊列。

樹（DFS 和 BFS）

樹，是一種使用節(jié)點來模擬分等級（層次）數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。節(jié)點存儲數(shù)據(jù)，并指向其他節(jié)點（每個節(jié)點都存儲有自身數(shù)據(jù)，和指向其它節(jié)點的指針）。部分讀者可能對節(jié)點、指針等術(shù)語不太熟悉，所以我們這里做一個類比：把一棵樹比作一個組織結(jié)構(gòu)。這個組織結(jié)構(gòu)有一個最高負責(zé)人（根節(jié)點），比如說總經(jīng)理。緊跟著就是在其之下的職位，比如說一個副總。

我們用一個從老總指向副總的箭頭來表示這種關(guān)系。老總 → 副總。一個職位（老總），就是一個節(jié)點；老總和副總之間的關(guān)系（箭頭），就是指針。在組織結(jié)構(gòu)圖中創(chuàng)建更多的類似關(guān)系，只需要重復(fù)上面的步驟，一個節(jié)點指向另外一個節(jié)點。

在概念上，我希望節(jié)點和指針能夠講得通。在實踐上，我們再可以舉一個DOM的栗子。一個DOM的根節(jié)點就是，它指向了和。然后重復(fù)下去生成一顆DOM樹。

這么搞最贊的一點就是它具有嵌套節(jié)點的能力：一個

節(jié)點，每個
也可以有兄弟

節(jié)點。（作者發(fā)出了奇怪的贊美）

對樹進行操作

樹跟節(jié)點可以用兩個多帶帶的構(gòu)造器來描述：Node和Tree。

Node

data存儲一個值

parent指向這個節(jié)點的父節(jié)點

children指向表中的下一個節(jié)點（這個可能有一堆，那么可能是一個數(shù)組）

Tree

_root指向這個樹的根節(jié)點

traverseDF(callback)使用DFS遍歷樹的節(jié)點

traverseBF(callback)使用BFS遍歷樹的節(jié)點

contains(data,traversal)在樹里面搜索一個節(jié)點

add(data,toData,traverse)向樹添加一個節(jié)點

remove(child,parent)刪除樹的一個節(jié)點

實現(xiàn)一棵樹

下面開始寫代碼！

節(jié)點Node的屬性

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

每個Node的實例都包含三個屬性，data，parent和children。第一個屬性保存跟這個節(jié)點有關(guān)的數(shù)據(jù)，比如“村長”。第二個屬性指向一個節(jié)點（在js中，就是等于號，比如this.parent = someOtherNode 這個就實現(xiàn)指針了好吧。什么值傳遞就不細展開了。其他算法中的指針實現(xiàn)也類似。）。

function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree包含兩行代碼，第一行創(chuàng)建了一個Node的實例node，第二行把這個node賦值給了this._root。就是對一個樹進行了初始化，給了它一個根節(jié)點。
Tree和Node的定義只需要很少的代碼，但是這些代碼已經(jīng)足夠我們模擬一個有層次的數(shù)據(jù)結(jié)構(gòu)。為了說明這一點，我們可以通過用一點測試數(shù)據(jù)來創(chuàng)建Tree的實例（間接也創(chuàng)建了Node的實例）：

var tree = new Tree("CEO");


tree._root;
// 返回{data: "CEO", parent: null, children: []}

有parent和children的存在，我們可以把節(jié)點添加為_root的子節(jié)點，同時把這些子節(jié)點的父節(jié)點賦值為_root。

樹的方法

接下來，我們給樹添加下面這5個方法：

Tree

traverseDF(callback)

traverseBF(callback)

contains(data,traversal)

add(child,parent)

remove(node,parent)

這些方法都需要對樹進行遍歷，我們首先來實現(xiàn)遍歷方法（們）。

第一個: traverseDF(callback)

對樹進行深度優(yōu)先遍歷：

Tree.prototype.traverseDF = function(callback) {

    // 一個遞歸，立即執(zhí)行函數(shù)
    (function recurse(currentNode) {
        // 第二步
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // 第三步
            recurse(currentNode.children[i]);
        }

        // 第四步
        callback(currentNode);

        // 首先執(zhí)行
    })(this._root);

};

traverseDF(callback)有一個callback參數(shù)，顧名思義，callback是一個稍后會在traverseDF(callback)內(nèi)調(diào)用的函數(shù)。

traverseDF(callback)內(nèi)包含了一個叫做recurse的函數(shù)。recurse的意思是遞歸，這是一個遞歸函數(shù)，用人話說就是這個函數(shù)會調(diào)用自己，然后（特定條件下）自動結(jié)束。注意上面代碼注釋中的第*步，我會用他們來描述一下recurse函數(shù)是怎么遍歷到整棵樹的：

首先執(zhí)行： recurse，以樹的根節(jié)點作為參數(shù)。此時，currentNode指向這個根節(jié)點。

第二步：進入到一個for循環(huán)，對currentNode（比如說根節(jié)點）的每一個子節(jié)點進行迭代，從第一個開始。

第三步：在for循環(huán)體內(nèi)，調(diào)用recurse，傳參currentNode的某一個子節(jié)點。具體哪一個子節(jié)點取決于for循環(huán)的迭代情況。

第四步：當(dāng)currentNode沒有更多的子節(jié)點，退出for循環(huán)，并調(diào)用在調(diào)用traverseDf(callback)時傳遞進來的callback函數(shù)。

第二步（自終止），第三步（自調(diào)用），第四步（回調(diào)函數(shù)） 會重復(fù)進行，直到我們遍歷到樹的所有節(jié)點。

完整的講述遞歸需要一整面文章，這超出了本文的范圍。讀者可以用上面的traverseDF(callback)來實驗（在瀏覽器里面打個斷點看看是怎么執(zhí)行的），來嘗試理解它是怎么工作的。

下面這段例子用來說明一個樹是如何被traverseDF(callback)遍歷的。
首先我們創(chuàng)建一顆樹用來遍歷，下面這種方法并不好，但是可以起到說明的效果。理想的方式是使用后面在第四部分要實現(xiàn)的add(value)。

/*

建立一顆結(jié)構(gòu)如下的樹

one
├── two
│   ├── five
│   └── six
├── three
└── four
    └── seven

*/

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];

然后我們調(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"

*/

第二個: traverseBF(callback)

這個方法用來進行寬度優(yōu)先遍歷。
深度優(yōu)先和寬度優(yōu)先的遍歷順序是不一樣的，我們使用在traverseBF(callback)中用過的樹來證明這一點：

/*

 tree

 one (depth: 0)
 ├── two (depth: 1)
 │   ├── five (depth: 2)
 │   └── six (depth: 2)
 ├── three (depth: 1)
 └── four (depth: 1)
     └── seven (depth: 2)

 */

然后傳入相同的回調(diào)函數(shù)：

tree.traverseBF(function(node) {
    console.log(node.data)
});

/*

logs the following strings to the console

"one"
"two"
"three"
"four"
"five"
"six"
"seven"

*/

上面的log和樹的結(jié)構(gòu)已經(jīng)說明了寬度優(yōu)先遍歷的模式。從根節(jié)點開始，然后向下一層，從左向右遍歷所有這一層的節(jié)點。重復(fù)進行知道到達最底層。

現(xiàn)在我們有了概念，那么來實現(xiàn)代碼：

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();

    queue.enqueue(this._root);

    currentNode = queue.dequeue();

    while(currentNode){
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            queue.enqueue(currentNode.children[i]);
        }

        callback(currentNode);
        currentNode = queue.dequeue();
    }
};

traverseBF(callback)的定義包含了很多邏輯，作者在這里解釋了一堆。我感覺對理解代碼并沒有幫助。
嘗試解釋一下，根節(jié)點算第一層：

從根節(jié)點開始，這個時候currentNode是根節(jié)點；

第一次while遍歷currentNode的所有子節(jié)點，推進隊列。（這個時候第二層已經(jīng)遍歷到了，并且會在while循環(huán)中依次執(zhí)行，先進先出）

執(zhí)行回調(diào)函數(shù)，傳入currentNode；

currentNode賦值為第二層第一個子節(jié)點。

第二次while：對currentNode，第二層第一個子節(jié)點的所有子節(jié)點遍歷，推入隊列。注意這里是第三層的第一部分。

執(zhí)行回調(diào)函數(shù)，傳入currentNode；

currentNode賦值為第二層第二個子節(jié)點。

第三次while：對currentNode，第二層第二個子節(jié)點的所有子節(jié)點遍歷，推入隊列。注意這里是第三層的第二部分。

執(zhí)行回調(diào)函數(shù)，傳入currentNode；

currentNode賦值為第二層第三個子節(jié)點。

最后幾次while

：這個時候已經(jīng)沒有下一層了，不會進入for循環(huán)，就是依次把隊列里剩的節(jié)點傳到回調(diào)函數(shù)里面執(zhí)行就對了。

這樣就很清楚了。

第三個: contains(callback,traversal)

這個方法用來在樹里搜索一個特定的值。為了使用我們之前定義的兩種遍歷方式，contains(callback,traversal)可以接受兩個參數(shù)，要找的值，和要進行的遍歷方式。

Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};

call方法的第一個參數(shù)把traversal綁定在調(diào)用contains(callback,traversal)的那棵樹上面，第二個參數(shù)是一個在每個節(jié)點上面調(diào)用的函數(shù)。
下面這個函數(shù)大家自己理解，我感覺原作者解釋反了。

// 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)

現(xiàn)在我們會找了，再來個添加的方法吧。

Tree.prototype.add = function(data, toData, traversal) {
    //實例一個node
    var child = new Node(data),
        parent = null,
        //找爹函數(shù)
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        };
        //按某種方式執(zhí)行找爹函數(shù)
    this.contains(callback, traversal);
    //找到了嗎
    if (parent) {
      //找到了，領(lǐng)走，認爹
        parent.children.push(child);
        child.parent = parent;
    } else {
      //沒找到，報錯：沒這個爹
        throw new Error("Cannot add node to a non-existent parent.");
    }
};

注釋就很清楚了。

var tree = new Tree("CEO");

tree.add("VP of Happiness", "CEO", tree.traverseBF);

/*

our tree

"CEO"
└── "VP of Happiness"

*/

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"

 */

第五個: remove(data, fromData, traversal)

類似的，刪除方法：

Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;
        //因為是刪除某個數(shù)據(jù)下的某個值，所以先定義找爹
    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;
    //遍歷某個data爹的娃，如果全等，那么返回這個娃的排行，否則返回的index等于undefined
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}

在全文的最后，作者放出了全家福：

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云服務(wù)器云服務(wù)器樹結(jié)構(gòu) 樹結(jié)構(gòu)數(shù)據(jù)存儲數(shù)據(jù)庫樹 JSON樹結(jié)構(gòu)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/83910.html

發(fā)表評論

登陸后可評論

0條評論

LeoHsiun

男|高級講師

我要關(guān)注我要私信

TA的文章

大數(shù)據(jù)開發(fā)，想寫代碼不給我寫，到底是人性的扭曲，還是道德的淪喪？

閱讀 1285·2021-11-24 09:39
市面上什么樣的視頻直播軟件好？重點關(guān)注這三點！

閱讀 2206·2021-11-22 13:54
利用文件專家軟件無線傳輸電子書至Kindle（無需USB連接且解決無法識別問題）

閱讀 2254·2021-09-08 10:45
georgedatacenter促銷：美國、荷蘭VPS/1核1G/35GB SSD/1TB流量/1G

閱讀 1522·2021-08-09 13:43
規(guī)范開發(fā)工具

閱讀 3039·2019-08-30 15:52
CSS中的百分比

閱讀 3165·2019-08-29 15:38
window對象

閱讀 2901·2019-08-26 13:44
Vue基礎(chǔ)之內(nèi)部指令（上）

閱讀 3111·2019-08-26 13:30

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JavaScript數(shù)據(jù)結(jié)構(gòu)：樹

Node

Tree

節(jié)點Node的屬性

樹的方法

Tree

第一個: traverseDF(callback)

第二個: traverseBF(callback)

第三個: contains(callback,traversal)

第四個: add(data, toData, traversal)

第五個: remove(data, fromData, traversal)

相關(guān)文章

***Javascript中的樹結(jié)構(gòu)***

**學(xué)習(xí)*javascript**數(shù)據(jù)結(jié)構(gòu)*(四)——樹**

**學(xué)習(xí)*JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法（四）：二叉搜索樹**

JavaScript是如何工作的:渲染引擎和優(yōu)化其性能的技巧

數(shù)據(jù)結(jié)構(gòu)與算法JavaScript （不定時更新）

發(fā)表評論

0條評論

LeoHsiun

男|高級講師

TA的文章

大數(shù)據(jù)開發(fā)，想寫代碼不給我寫，到底是人性的扭曲，還是道德的淪喪？

市面上什么樣的視頻直播軟件好？重點關(guān)注這三點！

利用文件專家軟件無線傳輸電子書至Kindle（無需USB連接且解決無法識別問題）

georgedatacenter促銷：美國、荷蘭VPS/1核1G/35GB SSD/1TB流量/1G

規(guī)范開發(fā)工具

CSS中的百分比

window對象

Vue基礎(chǔ)之內(nèi)部指令（上）

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JavaScript數(shù)據(jù)結(jié)構(gòu)：樹

Node

Tree

節(jié)點Node的屬性

樹的方法

Tree

第一個: traverseDF(callback)

第二個: traverseBF(callback)

第三個: contains(callback,traversal)

第四個: add(data, toData, traversal)

第五個: remove(data, fromData, traversal)

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！