javascript - --这是广度优先还是深度优先搜索的例子？

Question

这是一个遍历整个文档对象模型的简单函数。我想知道这是广度优先还是深度优先，以及如何理解原因:

var traverseDOM = function () {
  function traverse (parent) {
    // mark 1
    _(parent.childNodes).forEach((child) => {
      traverse(child);
    }
    // mark 2
  }
  traverse(document.body);
}

从这个相关的 SO Post 看来是深度优先搜索.

可以根据wikipedia进一步分类.

InOrder、PreOrder 和 PostOrder。

Answer 1

考虑下面的树:

您从 traverse(1) 开始:

traverse(1)

在“标记 1”之后，该方法将开始遍历所有子节点，为每个子节点调用 traverse。第一个，traverse(1.1)，将“介入执行”:

traverse(1)
traverse(1.1)

当 traverse(1.1) 命中“标记 1”时，它将开始处理 它的 子级并调用 traverse(1.1.1) :

traverse(1)
traverse(1.1)
traverse(1.1.1)

由于“1.1.1”没有任何 child ，traverse(1.1.1) 到达“标记 2”，执行流程将返回到 forEach 循环父方法的 traverse(1.1):

traverse(1)
traverse(1.1)

循环继续，traverse 将为第二个 child “1.1.2”调用:

traverse(1)
traverse(1.1)
traverse(1.1.2)

在处理完“1.1”的两个子项后，traverse(1.1) 到达“标记 2”，执行流程现在回到 forEach 循环中 遍历(1):

traverse(1)

继续“1.2”:

traverse(1)
traverse(1.2)

我会在这里停下来，但你应该掌握它。您可以看到，“1.1.1”和“1.1.2”在“1.2”之前被访问，使其成为深度优先搜索。广度优先搜索将在“1.1.1”之前访问“1.2”和“1.3”。