摘要：樹可謂是開發(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 ). 所以我們就來學(xué)習(xí)樹這一數(shù)據(jù)結(jié)構(gòu)吧 !

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

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

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

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

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

因為每棵樹都包含節(jié)點, 所以我們有理由抽象出兩個構(gòu)造函數(shù): Node 和 Tree. 下面列出的是他們的屬性和方法. 掃一眼就好, 到具體實現(xiàn)可以再回來看有什么.

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

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

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

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

traverseDF(callback) 用DFS遍歷一棵樹

traverseBF(callback) 用BFS遍歷一棵樹

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

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

remove(child, parent) 從樹里移除一個節(jié)點

來開始寫代碼吧 !

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)建了一個節(jié)點, 第二行是把這個節(jié)點設(shè)為樹的根節(jié)點.

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

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

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

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

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

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

        // step1, 把根節(jié)點傳進來
    })(this._root);
};

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

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

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

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

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

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

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

接下來的例子只用上面提及到的代碼創(chuàng)建了一棵樹, 并用traverseDF 遍歷, 雖然不夠優(yōu)雅, 但好歹能正常工作. 在后面實現(xiàn) add(value) 這個方法后, 我們的實現(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
 
*/

用traverseDF(callback) 遍歷:

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

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

DFS和BFS 的不同, 在于遍歷順序的不同. 為了體現(xiàn)這點, 我們再次使用之前DFS用過的那棵樹, 這樣就好比較異同了

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

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

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)有了個大致的概念, 那就又來愉快地敲代碼吧:

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();
    }
};

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

這里的概念稍微有點多, 讓我們先來梳理一下:

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

把根節(jié)點_root 壓入隊列

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

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

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

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

queue 的隊頭出隊列, 將其賦值給currentNode

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

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

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

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

下面我們來定義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 方法實際上只是對樹的遍歷方法包裹多了一層而已:

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

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

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

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

經(jīng)過前面的步驟我們已經(jīng)知道如何在一棵樹搜索一個節(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.");
    }
};

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"

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

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

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

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ù)組的findIndex 方法已經(jīng)存在于ES6的標(biāo)準(zhǔn)里, 我們大可以直接使用而不用再次定義一個類似的方法.

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

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

原文鏈接: Data Structures With JavaScript: Tree

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

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