用JavaScript来学习树「译」

2017-09-13 10:30:31来源:segmentfault作者:acfasj人点击

分享

树可谓是web开发者最常碰到的数据结构之一了.要知道,整张网页就是一棵DOM树啊 (Document Object Model ).所以我们就来学习树这一数据结构吧 !


在这篇文章中,我们将创建一棵树并且用两种不同的方法来遍历它:Depth-First Search ( DFS,深度优先遍历 ),和 Breadth-First Search ( BFS, 宽度/广度优先搜索 ).DFS方法使用借助栈 ( stack ) 这一数据结构来访问树的每个节点,BFS则借助了队列 ( queue ).



在计算机科学里,树是一种分层的数据结构,用节点来描述数据.每个节点都保存有自己的数据和指向其他节点的指针.


用我们熟悉的DOM来解释一下节点 ( node ) 和 指针 ( pointer ) .在一张网页的DOM里,<html> 标签被称为根节点/根元素 ( root node ),那么,代表html 的这个节点就有指向它的子节点们的指针.具体到下面的代码:


var rootNode = document.getElementsByTagName('html')[0];
//rootNode.childNodes可以粗暴地认为就是指针啦
var childNodes = rootNode.childNodes;
console.log(childNodes);

嗯,所以一张网页就是节点有它的子节点们,每个子节点又有可能有各自的子节点,这样一直嵌套下去,就构成了一棵DOM树.


对树的操作

因为每棵树都包含节点,所以我们有理由抽象出两个构造函数: Node 和 Tree. 下面列出的是他们的属性和方法.扫一眼就好,到具体实现可以再回来看有什么.


Node
data 属性用来保存节点自身的值,简单起见,先假设它保存的是一个基本类型的值,如字符串one
parent指向它的父节点children指向它的子节点们所组成的数组Tree
_root代表一棵树的根节点traverseDF(callback)用DFS遍历一棵树traverseBF(callback)用BFS遍历一棵树contains(callback, traversal)用DFS或BFS 在树里遍历搜索一个节点add(data, toData, traverse)往树里添加一个节点remove(child, parent)从树里移除一个节点具体的代码实现

来开始写代码吧 !


Node构造函数
function Node(data) {
this.data = data;
this.parent = null;
this.children = [];
}
Tree构造函数
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的方法

方法上面已经列举过啦.


1. traverseDF(callback) 深度优先遍历
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'

*/
2. traverseBF(callback)

接下来来看看宽度优先遍历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 )就让能让我们的访问顺序截然不同


3. contains(callback, traversal)

下面我们来定义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) 并没有什么不同,只是提供了一个更一致的对外接口


4. add(data, toData, traversal)

经过前面的步骤我们已经知道如何在一棵树搜索一个节点了,那么我们就可以给某个特定的节点来添加子节点啦


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设定好相互间的父子关系,找不到这个特定的节点就抛出异常 : )


5. remove(data, fromData, traversal)

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


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


<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Tree in JS</title>
</head>
<body>
<script>
/********************************** 构造函数 ********************************/
function Node(data) {
this.data = data;
this.parent = null;
this.children = [];
}function Tree(data) {
var node = new Node(data);
this._root = node;
}var tree = new Tree ('CEO');
console.log(tree._root);/********************************** 1. traverseDF ********************************/
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);
};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*/
tree.traverseDF(function(node) {
console.log(node.data)
});/*logs the following strings to the console'five'
'six'
'two'
'three'
'seven'
'four'
'one'*//********************************** 2. traverseBF ********************************/
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();
}
};tree.traverseBF(function(node) {
console.log(node.data)
});/*logs the following strings to the console'one'
'two'
'three'
'four'
'five'
'six'
'seven'*//********************************** 3. contains ********************************/
Tree.prototype.contains = function (callback, traversal) {
traversal.call(this, callback);
};tree.contains(function (node) {
if (node.data === 'two') {
console.log(node);
}
}, tree.traverseBF);/********************************** 4. add ********************************/
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' *//********************************** 5. remove ********************************/
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' */</script>
</body>
</html>

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台