迷失了理解这个回调函数的作用（BFS，树的宽度级别）

Question

我目前正在研究和学习树，并且一直在处理遍历的不同实现。

class Node {
  constructor(data) {
      this.data = data;
      this.children = [];
  }

  add(data) {
      this.children.push(new Node(data));
  }

  remove(data) {
      this.children = this.children.filter(node => {
          return node.data !== data;
      })
  }
}

traverseBF(fn) {
    const arr = [this.root];
    while (arr.length) {
        const node = arr.shift();
        arr.push(...node.children);
        fn(node); //what role does this play?
    }
    return count;
}

traverseDF(fn) {
    const arr = [this.root]; 
    while (arr.length) {  
        const node = arr.shift(); 
        arr.unshift(...node.children); 
        fn(node); //what role does this play???
    }
}

我想我已经明白回调函数有它声明的上下文，并且能够访问外部函数中的变量，我认为这就是 arr 保持最新和回调函数的原因对于 BFS/DFS 在这种情况下工作是不可或缺的。然而，学习计算宽度级别打破了我的理解。

function levelWidth(root) {
  const arr = [root, 's'];
  const counters = [0];

  while (arr.length > 1) {
      const node = arr.shift();

      if (node === 's') {
          counters.push(0);
          arr.push('s');
      } else {
          arr.push(...node.children);
          counters[counters.length - 1]++;
      }
  }
  return counters;
}

这里没有回调，这个 BFS 搜索和遍历工作正常。任何人都可以帮助我更好地理解为什么在第一个实例而不是这个实例中需要它吗？？

当我这样调用遍历时到底发生了什么？

const letters = [];
const t = new Tree();
t.root = new Node('a');
t.root.add('b');
t.root.add('d');
t.root.children[0].add('c');
t.root.children[1].add('e');

t.traverseBF(node => {
    letters.push(node.data);
});
console.log(letters);

Answer 1

这里没有对错。

回调版本有两点不同：

它不应用任何使用访问节点的逻辑。它只处理遍历，不处理任何其他逻辑。任何特定的逻辑都留给调用者，调用者可以为此目的传递回调。在您的最后一个示例中，该特定逻辑包括将节点的 data 值收集到一个数组中。但是请注意，遍历函数并不知道这个逻辑，这是一个很好的关注点分离。

注意：traverseBF(fn)末尾的return count不应该存在（没有count）
它不会让调用者等到所有个节点都被访问。

non-callback 版本，不仅访问节点，而且还负责对这些节点进行 特定的 处理（即一些计数），并且它 returns 仅该处理的结果。这不太通用。如果你想要一个完全不同的目的的遍历，你不能使用这个函数，因为它真的不会告诉调用者它访问过的节点，也不会告诉调用者它发生的顺序。

你也可以想象一种“in-between”遍历实现：不使用回调，只是将所有访问过的节点收集到一个数组中，然后returns完成按访问顺序排列的节点数组。这更通用，但调用者必须等待，直到所有节点都已访问，然后才能开始在返回的节点数组上应用自己的算法。

所以，我会说回调版本更灵活和通用。

然而，实现这种通用遍历的更现代的方法不是通过回调系统，而是作为 生成器。

这是它的样子（注意开头的 *）

* traverseBF() {
    const arr = [this.root];
    while (arr.length) {
        const node = arr.shift();
        arr.push(...node.children);
        yield node;  // <---
    }
}

* traverseDF() {
    const arr = [this.root]; 
    while (arr.length) {  
        const node = arr.shift(); 
        arr.unshift(...node.children); 
        yield node; // <---
    }
}

调用者必须知道这些方法是生成器这一事实，但您可以像这样使用 for 循环：

let letters = [];
for (let node of t.traverseDF()) {
    // do something with this node before continuing the traversal
    letters.push(node.data);
}
console.log(letters);

这里的额外优势是调用者可以随时决定中止遍历。在上面的代码中，循环中的早期 break 实际上意味着遍历不会再完成。对于前面提到的所有其他方法，您必须触发异常才能实现；在所有其他情况下，遍历必须运行直到完成。

迷失了理解这个回调函数的作用（BFS，树的宽度级别）

Getting lost understanding the role of this callback function (BFS, width level for trees)

javascript

algorithm

tree

callback

breadth-first-search