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);
  }
};

我怎样才能改变它以使其首先变宽？
这就是Tree Class的样子：

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屋！