用JavaScript来学习树「译」

摘要：树可谓是开发者最常碰到的数据结构之一了要知道整张网页就是一棵树啊所以我们就来学习树这一数据结构吧在这篇文章中我们将创建一棵树并且用两种不同的方法来遍历它深度优先遍历和宽度广度优先遍历方法使用借助栈这一数据结构来访问树的每个节点则借助了队

树可谓是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): 如果你想看二叉树的实现