摘要：樹可謂是開發(fā)者最常碰到的數(shù)據(jù)結(jié)構(gòu)之一了要知道整張網(wǎng)頁(yè)就是一棵樹啊所以我們就來(lái)學(xué)習(xí)樹這一數(shù)據(jù)結(jié)構(gòu)吧在這篇文章中我們將創(chuàng)建一棵樹并且用兩種不同的方法來(lái)遍歷它深度優(yōu)先遍歷和寬度廣度優(yōu)先遍歷方法使用借助棧這一數(shù)據(jù)結(jié)構(gòu)來(lái)訪問(wèn)樹的每個(gè)節(jié)點(diǎn)則借助了隊(duì)

樹可謂是web開發(fā)者最常碰到的數(shù)據(jù)結(jié)構(gòu)之一了. 要知道, 整張網(wǎng)頁(yè)就是一棵DOM樹啊 (Document Object Model ). 所以我們就來(lái)學(xué)習(xí)樹這一數(shù)據(jù)結(jié)構(gòu)吧 !

在這篇文章中, 我們將創(chuàng)建一棵樹并且用兩種不同的方法來(lái)遍歷它: Depth-First Search ( DFS, 深度優(yōu)先遍歷 ), 和 Breadth-First Search ( BFS, 寬度/廣度優(yōu)先遍歷 ). DFS方法使用借助棧 ( stack ) 這一數(shù)據(jù)結(jié)構(gòu)來(lái)訪問(wèn)樹的每個(gè)節(jié)點(diǎn), BFS則借助了隊(duì)列 ( queue ).

在計(jì)算機(jī)科學(xué)里, 樹是一種分層的數(shù)據(jù)結(jié)構(gòu), 用節(jié)點(diǎn)來(lái)描述數(shù)據(jù). 每個(gè)節(jié)點(diǎn)都保存有自己的數(shù)據(jù)和指向其他節(jié)點(diǎn)的指針.

用我們熟悉的DOM來(lái)解釋一下節(jié)點(diǎn) ( node ) 和 指針 ( pointer ) . 在一張網(wǎng)頁(yè)的DOM里, 標(biāo)簽被稱為根節(jié)點(diǎn)/根元素 ( root node ), 那么, 代表html 的這個(gè)節(jié)點(diǎn)就有指向它的子節(jié)點(diǎn)們的指針. 具體到下面的代碼:

var rootNode = document.getElementsByTagName("html")[0];
//  rootNode.childNodes可以粗暴地認(rèn)為就是指針啦
var childNodes = rootNode.childNodes;
console.log(childNodes);

嗯, 所以一張網(wǎng)頁(yè)就是節(jié)點(diǎn)有它的子節(jié)點(diǎn)們, 每個(gè)子節(jié)點(diǎn)又有可能有各自的子節(jié)點(diǎn), 這樣一直嵌套下去, 就構(gòu)成了一棵DOM樹.

因?yàn)槊靠脴涠及?jié)點(diǎn), 所以我們有理由抽象出兩個(gè)構(gòu)造函數(shù): Node 和 Tree. 下面列出的是他們的屬性和方法. 掃一眼就好, 到具體實(shí)現(xiàn)可以再回來(lái)看有什么.

data 屬性用來(lái)保存節(jié)點(diǎn)自身的值, 簡(jiǎn)單起見, 先假設(shè)它保存的是一個(gè)基本類型的值, 如字符串one

parent 指向它的父節(jié)點(diǎn)

children 指向它的子節(jié)點(diǎn)們所組成的數(shù)組

_root 代表一棵樹的根節(jié)點(diǎn)

traverseDF(callback) 用DFS遍歷一棵樹

traverseBF(callback) 用BFS遍歷一棵樹

contains(callback, traversal) 用DFS或BFS 在樹里遍歷搜索一個(gè)節(jié)點(diǎn)

add(data, toData, traverse) 往樹里添加一個(gè)節(jié)點(diǎn)

remove(child, parent) 從樹里移除一個(gè)節(jié)點(diǎn)

來(lái)開始寫代碼吧 !

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

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

Tree 構(gòu)造函數(shù)里只有兩行代碼, 第一行先是創(chuàng)建了一個(gè)節(jié)點(diǎn), 第二行是把這個(gè)節(jié)點(diǎn)設(shè)為樹的根節(jié)點(diǎn).

雖然Node 和 Tree 的代碼只有那么幾行, 但是這就足以讓我們描述一棵樹了. 不信 ? 用下面的代碼創(chuàng)建一棵樹看看:

var tree = new Tree ("CEO");  // 根節(jié)點(diǎn)就像是CEO老總
console.log(tree._root);  // Node {data: "CEO", parent: null, children: Array(0)}

幸好有parent 和 children 這兩個(gè)屬性的存在, 我們可以children 給根節(jié)點(diǎn)_root 添加子節(jié)點(diǎn), 也可以用parent 把其他節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置成_root . 反正你開心就好.

方法上面已經(jīng)列舉過(guò)啦.

Tree.prototype.traverseDF = function (callback) {
    (function recurse(currentNode) {
        // step2 遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)們
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // step3, 遞歸調(diào)用遍歷每個(gè)子節(jié)點(diǎn)的子節(jié)點(diǎn)們
            recurse(currentNode.children[i]);
        }

        // step4 可以在這里寫你處理每一個(gè)節(jié)點(diǎn)的回調(diào)函數(shù)
        callback(currentNode);

        // step1, 把根節(jié)點(diǎn)傳進(jìn)來(lái)
    })(this._root);
};

traverseDF(callback) 有一個(gè)callback 參數(shù), 是一個(gè)函數(shù), 等到你需要調(diào)用的時(shí)候調(diào)用. 除此之外, 還有一個(gè)叫recurse 的遞歸函數(shù). 說(shuō)一下詳細(xì)的步驟吧:

首先, 利用立即執(zhí)行函數(shù)表達(dá)式把根節(jié)點(diǎn)傳進(jìn)recurse 函數(shù), 此時(shí), currentNode 就是根節(jié)點(diǎn)

進(jìn)入for 循環(huán)后, 依次遍歷當(dāng)前節(jié)點(diǎn)的每一個(gè)子節(jié)點(diǎn)

在for 循環(huán)體里, 遞歸地調(diào)用recurse 函數(shù)再遍歷子節(jié)點(diǎn)的子節(jié)點(diǎn)

當(dāng)currentNode 不再有子節(jié)點(diǎn)了, 就會(huì)退出for 循環(huán), 然后調(diào)用callback 回調(diào)函數(shù)后, 就一層層地返回了

開頭我們說(shuō)DFS 方法借助了棧來(lái)實(shí)現(xiàn), 是的, 我們確實(shí)借用了棧, 就是recurse遞歸函數(shù)的函數(shù)調(diào)用棧. 任何函數(shù)的調(diào)用都會(huì)涉及到進(jìn)棧和出棧.

遞歸是一個(gè)編程上很重要的思想, 要想講清楚也不是一時(shí)半會(huì)的事. 在這里我們把重點(diǎn)放到樹上, 對(duì)遞歸不太理解的童鞋們可以自行搜索一下, 但在這里建議大家把這個(gè)traverseDF 的代碼敲一下, 相信你起碼能理解其中的一些奧妙.

接下來(lái)的例子只用上面提及到的代碼創(chuàng)建了一棵樹, 并用traverseDF 遍歷, 雖然不夠優(yōu)雅, 但好歹能正常工作. 在后面實(shí)現(xiàn) add(value) 這個(gè)方法后, 我們的實(shí)現(xiàn)看起來(lái)就不會(huì)那么傻逼了

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"
 
*/

接下來(lái)來(lái)看看寬度優(yōu)先遍歷BFS吧 !

DFS和BFS 的不同, 在于遍歷順序的不同. 為了體現(xiàn)這點(diǎn), 我們?cè)俅问褂弥癉FS用過(guò)的那棵樹, 這樣就好比較異同了

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

先假裝我們已經(jīng)實(shí)現(xiàn)了traverseBF(callback) , 并且使用了和traverseDF(callback) 相同的回調(diào)函數(shù), 看看輸出的結(jié)果, 畢竟有時(shí)候從結(jié)果推過(guò)程很重要

tree.traverseBF(function(node) {
    console.log(node.data)
});
 
/*
 
logs the following strings to the console
 
"one"
"two"
"three"
"four"
"five"
"six"
"seven"
 
*/

哦吼, 就是先從depth = 0, depth = 1...這樣按照每一層去遍歷嘛. 既然我們已經(jīng)有了個(gè)大致的概念, 那就又來(lái)愉快地敲代碼吧:

Tree.prototype.traverseBF = function (callback) {
    var queue = [];

    queue.push(this._root);

    var currentNode = queue.shift();

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

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

// 注: 此處原文的隊(duì)列作者用了 `var queue = new Queue();`, 可能是他之前封裝的構(gòu)造函數(shù)
// 我們這里用數(shù)組來(lái)就好, push()表示進(jìn)隊(duì)列, shift()表示出隊(duì)列

這里的概念稍微有點(diǎn)多, 讓我們先來(lái)梳理一下:

創(chuàng)建一個(gè)空數(shù)組, 表示隊(duì)列queue

把根節(jié)點(diǎn)_root 壓入隊(duì)列

聲明currentNode 變量, 并用根節(jié)點(diǎn)_root 初始化

當(dāng)currentNode 表示一個(gè)節(jié)點(diǎn), 轉(zhuǎn)換成布爾值不為false 時(shí), 進(jìn)入while 循環(huán)

用for 循環(huán)來(lái)取得currentNode 的每一個(gè)子節(jié)點(diǎn), 并把他們逐個(gè)壓入queue

對(duì)currentNode 調(diào)用回調(diào)函數(shù) callback

queue 的隊(duì)頭出隊(duì)列, 將其賦值給currentNode

就這樣一直重復(fù), 直到?jīng)]有隊(duì)列中沒(méi)有節(jié)點(diǎn)賦值給currentNode , 程序結(jié)束

你可能會(huì)對(duì)上述步驟2, 3的對(duì)應(yīng)兩行代碼有些疑惑:

queue.push(this._root);
var currentNode = queue.shift();
// 先進(jìn)隊(duì)列又出隊(duì)列好像顯得有些多次一舉? 
// 實(shí)際上直接 var currentNode = this._root也是可以的
// 但在這里還是建議像這樣寫, 以保持和while循環(huán)體內(nèi)代碼格式的統(tǒng)一

到了這里, 是不是感覺(jué)到棧和隊(duì)列的神奇之處? 后進(jìn)先出 ( LIFO, Last In First Out) 和 先進(jìn)先出 ( FIFO, First In First Out ) 就讓能讓我們的訪問(wèn)順序截然不同

下面我們來(lái)定義contains 方法:

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

它是這樣被調(diào)用的:

tree.contains(function (node) {
    if (node.data === "two") {
        console.log(node);
    }
}, tree.traverseBF);

可以看到, contains 方法實(shí)際上只是對(duì)樹的遍歷方法包裹多了一層而已:

traversal 讓你決定定是遍歷方法是DFS, 還是BFS

callback 讓你指定的就是之前我們定義traverseDF(callback) 或者 traverseBF(callback) 里的callback 函數(shù)

函數(shù)體內(nèi) traversal.call(this, callback) , this 綁定到當(dāng)前函數(shù)的執(zhí)行環(huán)境對(duì)象, 在這里來(lái)說(shuō)tree.contains()... 的話, tree 就是 this

這和你直接調(diào)用traverseDF(callback) 或者 traverseBF(callback) 并沒(méi)有什么不同, 只是提供了一個(gè)更一致的對(duì)外接口

經(jīng)過(guò)前面的步驟我們已經(jīng)知道如何在一棵樹搜索一個(gè)節(jié)點(diǎn)了, 那么我們就可以給某個(gè)特定的節(jié)點(diǎn)來(lái)添加子節(jié)點(diǎn)啦

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.");
    }
};

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", "VP of Finance", tree.traverseBF);

/*

 tree

 "CEO"
 ├── "VP of Happiness"
 ├── "VP of Finance"
 │   ├── "Director of Puppies"
 │   └── "Manager of Puppies"
 └── "VP of Sadness"

 */
 
 // 注: 原文此處的樹圖和代碼有點(diǎn)不對(duì)應(yīng), 應(yīng)該是作者畫錯(cuò)了, 這里改了一下

感覺(jué)不用再啰嗦了, 就是遍歷搜索節(jié)點(diǎn), 找到的話new 一個(gè)Node設(shè)定好相互間的父子關(guān)系, 找不到這個(gè)特定的節(jié)點(diǎn)就拋出異常 : )

有了添加, 那就要有刪除嘛:

Tree.prototype.remove = function (data, fromData, traversal) {
    var childToRemove = null,
        parent = 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 removes not exist.")
        } else {
            childToRemove = parent.children.splice(index, 1);
        }
    } else {
        throw new Error("Parent does not exist.");
    }
};

function findIndex(arr, data) {
    var index;

    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}

tree.remove("Manager of Puppies", "VP of Finance", tree.traverseDF);
tree.remove("VP of Sadness", "CEO", tree.traverseDF);

/*

 tree

 "CEO"
 ├── "VP of Happiness"
 └── "VP of Finance"
    ├── "Director of Puppies"
    └── "Manager of Puppies"

 */

其實(shí)都是類似的套路, 另外, 數(shù)組的findIndex 方法已經(jīng)存在于ES6的標(biāo)準(zhǔn)里, 我們大可以直接使用而不用再次定義一個(gè)類似的方法.

這篇文章重點(diǎn)是如何建立一棵樹, 和遍歷方法DFS, BFS 的思想, 至于那些增刪改查, 只要懂得遍歷, 那都好辦, 具體情況具體分析

好啦, 到這里這些方法已經(jīng)全部都實(shí)現(xiàn)了. 本文沒(méi)有逐字翻譯, 大部分是意譯, 和原文是有些出入的, 此外代碼也有一些邊角的改動(dòng), 并沒(méi)有一一指明.

原文鏈接: Data Structures With JavaScript: Tree

完整代碼, 或者訪問(wèn)相應(yīng)的JS Bin

更新(9/18): 如果你想看二叉樹的實(shí)現(xiàn)