用JavaScript来学习树「译」
文章目录
树可谓是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
更新(9/18): 如果你想看二叉树的实现
<!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>
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论