javascript 中树的广度优先遍历

Question

我正在尝试很好地学习数据结构，并为常规树上的回调的深度优先 traversal/application 实现了以下代码：

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

我该如何更改它以使其广度优先？这就是树 Class 的样子：

var Tree = function (value) {
  var newTree = {};

  newTree.value = value;
  newTree.children = [];
  extend(newTree, treeMethods);

  return newTree;
};

Answer 1

从根本上说，DFS 和 BFS 之间的区别在于，使用 DFS 时，您将当前节点的子节点压入堆栈，因此它们将在其他所有内容之前被弹出并处理，而对于 BFS，您将子项推到队列的末尾，因此它们将在其他所有内容之后被弹出并处理。

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

现在 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 中树的广度优先遍历

breadth-first traversal of a tree in javascript

javascript

tree

data-structures