javascript中树的广度优先遍历 [英] breadth-first traversal of a tree in javascript
问题描述
我正在努力学习数据结构,并为常规树上的回调的深度优先遍历/应用实现了以下代码:
I am trying to learn data structures well and implemented the following code for a depth-first traversal/application of a callback on a regular tree:
Tree.prototype.traverse = function (callback) {
callback(this.value);
if (!this.children) {
return;
}
for (var i = 0; i < this.children.length; i++) {
var child = this.children[i];
child.traverse(callback);
}
};
我该如何更改以使其广度优先?这是树类的样子:
How could I change this to make it breadth first instead? This is what the Tree Class looks like:
var Tree = function (value) {
var newTree = {};
newTree.value = value;
newTree.children = [];
extend(newTree, treeMethods);
return newTree;
};
推荐答案
从根本上说,DFS 和 BFS 的区别在于,使用 DFS 时,您将当前节点的子节点推入堆栈,因此它们将被弹出和处理 在其他所有事情之前,而对于 BFS,您将孩子推到队列的末尾,因此它们将在其他所有事情之后 被弹出和处理.
Fundamentally, the difference between DFS and BFS is that with a DFS you push the children of the current node onto a stack, so they will be popped and processed before everything else, while for BFS you push the children onto the end of a queue, so they will be popped and processed after everything else.
DFS 易于递归实现,因为您可以使用调用堆栈作为堆栈.你不能用 BFS 做到这一点,因为你需要一个队列.为了使相似性清晰,让我们首先将您的 DFS 转换为迭代实现:
DFS is easy to implement recursively because you can use the call stack as the stack. You can't do that with BFS, because you need a queue. Just to make the similarity clear, lets convert your DFS to an iterative implementation first:
//DFS
Tree.prototype.traverse = function (callback) {
var stack=[this];
var n;
while(stack.length>0) {
n = stack.pop();
callback(n.value);
if (!n.children) {
continue;
}
for (var i = n.children.length-1; i>=0; i--) {
stack.push(n.children[i]);
}
}
};
现在是 BFS
//BFS
Tree.prototype.traverse = function (callback) {
var queue=[this];
var n;
while(queue.length>0) {
n = queue.shift();
callback(n.value);
if (!n.children) {
continue;
}
for (var i = 0; i< n.children.length; i++) {
queue.push(n.children[i]);
}
}
};
这篇关于javascript中树的广度优先遍历的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!