“树”，是web开发中最常用的数据结构之一。这句话对开发者和用户来讲，都适用：开发人员通过HTML创造了一个DOM，用户则通过DOM消费网络信息。
进一步讲，您正在阅读的本文也是以树的形式在浏览器中渲染的。文章中的段落由<p>标签中的文字所代表；<p>标签嵌套在<body>元素中，而<body>元素则是<html>的子元素。
数据的嵌套类似一个家谱：<html>元素是一个爹爹，<body>元素是一个孩儿，<p>元素则是<body>元素的孩儿。如果你感觉这种类比容易理解，那么在接下来实现一棵树的过程中，更多的类比对你来说应该也不成问题。
在本文中，我们将创建一颗有两种遍历方式的树：Depth-First-Search(DFS)深度优先搜索，和Breadth-First-Search(BFS)宽度优先搜索（遍历是指访问树的每一个节点）。这两种遍历方式各自强调了对一颗树操作的不同姿势；而且他们用到了我们之前提过的（ 没翻，去找原文 ）数据结构：DFS用到了栈，BFS用到了队列。
树（DFS 和 BFS）
树，是一种使用节点来模拟分等级（层次）数据的数据结构。节点存储数据，并指向其他节点（每个节点都存储有自身数据，和指向其它节点的指针）。部分读者可能对节点、指针等术语不太熟悉，所以我们这里做一个类比：把一棵树比作一个组织结构。这个组织结构有一个最高负责人（根节点），比如说总经理。紧跟着就是在其之下的职位，比如说一个副总。
我们用一个从老总指向副总的箭头来表示这种关系。老总 → 副总。一个职位（老总），就是一个节点；老总和副总之间的关系（箭头），就是指针。在组织结构图中创建更多的类似关系，只需要重复上面的步骤，一个节点指向另外一个节点。
在概念上，我希望节点和指针能够讲得通。在实践上，我们再可以举一个DOM的栗子。一个DOM的根节点就是<html>，它指向了<head>和<body>。然后重复下去生成一颗DOM树。
这么搞最赞的一点就是它具有嵌套节点的能力：一个<ul>，内部可以有n个<li>节点，每个<li>也可以有兄弟<li>节点。（作者发出了奇怪的赞美）
对树进行操作
树跟节点可以用两个单独的构造器来描述：Node和Tree。
Node
data存储一个值parent指向这个节点的父节点children指向表中的下一个节点 （这个可能有一堆，那么可能是一个数组）
Tree
_root指向这个树的根节点traverseDF(callback)使用DFS遍历树的节点traverseBF(callback)使用BFS遍历树的节点contains(data,traversal)在树里面搜索一个节点add(data,toData,traverse)向树添加一个节点remove(child,parent)删除树的一个节点
实现一棵树
下面开始写代码！
节点Node的属性
function Node(data) {
this.data = data;
this.parent = null;
this.children = [];
}每个Node的实例都包含三个属性，data，parent和children。第一个属性保存跟这个节点有关的数据，比如“村长”。第二个属性指向一个节点（在js中，就是等于号，比如this.parent = someOtherNode 这个就实现指针了好吧。什么值传递就不细展开了。其他算法中的指针实现也类似。）。
function Tree(data) {
var node = new Node(data);
this._root = node;
}Tree包含两行代码，第一行创建了一个Node的实例node，第二行把这个node赋值给了this._root。就是对一个树进行了初始化，给了它一个根节点。 Tree和Node的定义只需要很少的代码，但是这些代码已经足够我们模拟一个有层次的数据结构。为了说明这一点，我们可以通过用一点测试数据来创建Tree的实例（间接也创建了Node的实例）：
var tree = new Tree('CEO');
tree._root;
// 返回{data: 'CEO', parent: null, children: []}有parent和children的存在，我们可以把节点添加为_root的子节点，同时把这些子节点的父节点赋值为_root。
树的方法
接下来，我们给树添加下面这5个方法：
Tree
traverseDF(callback)traverseBF(callback)contains(data,traversal)add(child,parent)remove(node,parent)
这些方法都需要对树进行遍历，我们首先来实现遍历方法（们）。
第一个: traverseDF(callback)
对树进行深度优先遍历：
Tree.prototype.traverseDF = function(callback) {
// 一个递归，立即执行函数
(function recurse(currentNode) {
// 第二步
for (var i = 0, length = currentNode.children.length; i < length; i++) {
// 第三步
recurse(currentNode.children[i]);
}
// 第四步
callback(currentNode);
// 首先执行
})(this._root);
};traverseDF(callback)有一个callback参数，顾名思义，callback是一个稍后会在traverseDF(callback)内调用的函数。
traverseDF(callback)内包含了一个叫做recurse的函数。recurse的意思是递归，这是一个递归函数，用人话说就是这个函数会调用自己，然后（特定条件下）自动结束。注意上面代码注释中的第*步，我会用他们来描述一下recurse函数是怎么遍历到整棵树的：
- 首先执行：
recurse，以树的根节点作为参数。此时，currentNode指向这个根节点。 - 第二步： 进入到一个
for循环，对currentNode（比如说根节点）的每一个子节点进行迭代，从第一个开始。 - 第三步： 在
for循环体内，调用recurse，传参currentNode的某一个子节点。具体哪一个子节点取决于for循环的迭代情况。 - 第四步： 当
currentNode没有更多的子节点，退出for循环，并调用在调用traverseDf(callback)时传递进来的callback函数。
第二步（自终止），第三步（自调用），第四步（回调函数） 会重复进行，直到我们遍历到树的所有节点。
完整的讲述递归需要一整面文章，这超出了本文的范围。读者可以用上面的traverseDF(callback)来实验（在浏览器里面打个断点看看是怎么执行的），来尝试理解它是怎么工作的。
下面这段例子用来说明一个树是如何被traverseDF(callback)遍历的。
首先我们创建一颗树用来遍历，下面这种方法并不好，但是可以起到说明的效果。理想的方式是使用后面在第四部分要实现的add(value)。
/*
建立一颗结构如下的树
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];
然后我们调用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)
这个方法用来进行宽度优先遍历。
深度优先和宽度优先的遍历顺序是不一样的，我们使用在traverseBF(callback)中用过的树来证明这一点：
/*
tree
one (depth: 0)
├── two (depth: 1)
│ ├── five (depth: 2)
│ └── six (depth: 2)
├── three (depth: 1)
└── four (depth: 1)
└── seven (depth: 2)
*/然后传入相同的回调函数：
tree.traverseBF(function(node) {
console.log(node.data)
});
/*
logs the following strings to the console
'one'
'two'
'three'
'four'
'five'
'six'
'seven'
*/上面的log和树的结构已经说明了宽度优先遍历的模式。从根节点开始，然后向下一层，从左向右遍历所有这一层的节点。重复进行知道到达最底层。
现在我们有了概念，那么来实现代码：
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)的定义包含了很多逻辑，作者在这里解释了一堆。我感觉对理解代码并没有帮助。
尝试解释一下，根节点算第一层：
- 从根节点开始，这个时候currentNode是根节点；
第一次while遍历currentNode的所有子节点，推进队列。（这个时候第二层已经遍历到了，并且会在while循环中依次执行，先进先出）
- 执行回调函数，传入currentNode；
- currentNode赋值为第二层第一个子节点。
第二次while：对currentNode，第二层第一个子节点的所有子节点遍历，推入队列。注意这里是第三层的第一部分。
- 执行回调函数，传入currentNode；
- currentNode赋值为第二层第二个子节点。
第三次while：对currentNode，第二层第二个子节点的所有子节点遍历，推入队列。注意这里是第三层的第二部分。
- 执行回调函数，传入currentNode；
- currentNode赋值为第二层第三个子节点。
- 最后几次while
：这个时候已经没有下一层了，不会进入for循环，就是依次把队列里剩的节点传到回调函数里面执行就对了。
这样就很清楚了。
第三个: contains(callback,traversal)
这个方法用来在树里搜索一个特定的值。为了使用我们之前定义的两种遍历方式，contains(callback,traversal)可以接受两个参数，要找的值，和要进行的遍历方式。
Tree.prototype.contains = function(callback, traversal) {
traversal.call(this, callback);
};call方法的第一个参数把traversal绑定在调用contains(callback,traversal)的那棵树上面，第二个参数是一个在每个节点上面调用的函数。
下面这个函数大家自己理解，我感觉原作者解释反了。
// 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)
现在我们会找了，再来个添加的方法吧。
Tree.prototype.add = function(data, toData, traversal) {
//实例一个node
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);
/*
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;
//因为是删除某个数据下的某个值，所以先定义找爹
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;
}