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

樹可謂是web開發者最常碰到的數據結構之一了. 要知道, 整張網頁就是一棵DOM樹啊 (Document Object Model ). 所以我們就來學習樹這一數據結構吧 !

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

在計算機科學里, 樹是一種分層的數據結構, 用節點來描述數據. 每個節點都保存有自己的數據和指向其他節點的指針.

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

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

嗯, 所以一張網頁就是節點有它的子節點們, 每個子節點又有可能有各自的子節點, 這樣一直嵌套下去, 就構成了一棵DOM樹.

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

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

parent 指向它的父節點

children 指向它的子節點們所組成的數組

_root 代表一棵樹的根節點

traverseDF(callback) 用DFS遍歷一棵樹

traverseBF(callback) 用BFS遍歷一棵樹

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

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

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

來開始寫代碼吧 !

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

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

Tree 構造函數里只有兩行代碼, 第一行先是創建了一個節點, 第二行是把這個節點設為樹的根節點.

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

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

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

方法上面已經列舉過啦.

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

        // step4 可以在這里寫你處理每一個節點的回調函數
        callback(currentNode);

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

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

首先, 利用立即執行函數表達式把根節點傳進recurse 函數, 此時, currentNode 就是根節點

進入for 循環后, 依次遍歷當前節點的每一個子節點

在for 循環體里, 遞歸地調用recurse 函數再遍歷子節點的子節點

當currentNode 不再有子節點了, 就會退出for 循環, 然后調用callback 回調函數后, 就一層層地返回了

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

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

接下來的例子只用上面提及到的代碼創建了一棵樹, 并用traverseDF 遍歷, 雖然不夠優雅, 但好歹能正常工作. 在后面實現 add(value) 這個方法后, 我們的實現看起來就不會那么傻逼了

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

接下來來看看寬度優先遍歷BFS吧 !

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

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

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

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();`, 可能是他之前封裝的構造函數
// 我們這里用數組來就好, push()表示進隊列, shift()表示出隊列

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

創建一個空數組, 表示隊列queue

把根節點_root 壓入隊列

聲明currentNode 變量, 并用根節點_root 初始化

當currentNode 表示一個節點, 轉換成布爾值不為false 時, 進入while 循環

用for 循環來取得currentNode 的每一個子節點, 并把他們逐個壓入queue

對currentNode 調用回調函數 callback

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

就這樣一直重復, 直到沒有隊列中沒有節點賦值給currentNode , 程序結束

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

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

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

下面我們來定義contains 方法:

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

它是這樣被調用的:

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

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

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

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

函數體內 traversal.call(this, callback) , this 綁定到當前函數的執行環境對象, 在這里來說tree.contains()... 的話, tree 就是 this

這和你直接調用traverseDF(callback) 或者 traverseBF(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.");
    }
};

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"

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

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

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

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"

 */

其實都是類似的套路, 另外, 數組的findIndex 方法已經存在于ES6的標準里, 我們大可以直接使用而不用再次定義一個類似的方法.

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

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

原文鏈接: Data Structures With JavaScript: Tree

完整代碼, 或者訪問相應的JS Bin

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