javascript javascript中树的广度优先遍历
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33703019/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
breadth-first traversal of a tree in javascript
提问by devdropper87
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;
};
回答by Matt Timmermans
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 beforeeverything else, while for BFS you push the children onto the end of a queue, so they will be popped and processed aftereverything else.
从根本上说，DFS 和 BFS 之间的区别在于，在 DFS 中，您将当前节点的子节点推送到堆栈上，因此它们将在其他所有操作之前被弹出和处理，而对于 BFS，您将子节点推送到队列的末尾，所以它们将在其他一切之后被弹出和处理。
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 易于递归实现，因为您可以使用调用堆栈作为堆栈。你不能用 BFS 做到这一点，因为你需要一个队列。为了使相似性清晰，让我们首先将您的 DFS 转换为迭代实现：
//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]);
}
}
};
And now BFS
现在 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]);
}
}
};
