Javascript-ONLY DOM Tree Traversal - DFS and BFS？

Question

任何人都可以提供代码，伪代码，甚至提供良好的链接来实现DFS（深度优先搜索）和BFS（广度优先搜索）在普通JavaScript（没有JQuery，或任何帮助程序库）中？我一直在试图了解如何实现任一遍历，但我似乎无法真正区分 BFS 和 DFS 实现的区别。

如果我们想要一个具体问题作为示例：我想在给定节点上遍历 DOM，并获取所有类名。

（我认为遍历的唯一方法是遍历每个父节点，从该节点获取我需要的东西，在本例中是类名，然后查看它们是否有子节点，递归每个子节点。我相信这是DFS？同样，我很难理解DOM遍历实现中的差异！）

最后，如果这是一个重复，很抱歉。我到处寻找好的、清晰的例子，但没有找到任何好的答案！如果已经有好的答案，请告诉我：）

Answer 1

对于DFS，您可以使用TreeWalker或NodeIterator API并使用NodeFilter.SHOW_ELEMENT进行过滤。

Answer 2

DFS:

function m(elem) {
    elem.childNodes.forEach(function(a) {
        m(a);
    });
    //do sth with elem
}
m(document.body);

这将循环遍历所有元素，并对每个元素遍历每个子元素，依此类推。

基础设施：

var childs = [];

function m(elem) {
    elem.childNodes.forEach(function(a) {
        childs.push(a);
    });
    b = childs;
    childs = [];
    b.forEach(function(a) {
        m(a);
    });
}
m(document.body);

这将循环元素，将其子元素推到堆栈上，然后从每个元素开始。正如您所看到的，这会消耗更多的空间（子数组），这不是最好的。。。

Answer 3

让我们使用以下 HTML 代码作为示例：

<div class="a">
    <div class="aa">
        <span class="aaa">
        </span>
        <span class="aab">
        </span>
    </div>
    <div class="ab">
        <span class="aba">
        </span>
        <span class="abb">
        </span>
    </div>
</div>

DFS 将始终首先转到下一级节点，并且仅当不再有未遍历的子节点时，它才会单步执行到当前级别的下一个节点。

DFS将按以下顺序遍历示例的节点：

a, aa, aaa, aab, ab, aba, abb

BFS 将始终首先遍历当前级别中的所有节点，然后才会进入下一级节点。

BFS将按以下顺序遍历示例中的节点:

a, aa, ab, aaa, aab, aba, abb

没有一个明确的答案，你应该使用其中的哪一个。通常这取决于你的需要。

实施细节:

对于DFS，人们经常使用堆栈。

伪代码：

stack my_stack;
list visited_nodes;
my_stack.push(starting_node);

while my_stack.length > 0
   current_node = my_stack.pop();

   if current_node == null
       continue;
   if current_node in visited_nodes
      continue;
   visited_nodes.add(current_node);

   // visit node, get the class or whatever you need

   foreach child in current_node.children
      my_stack.push(child);

此代码将一直持续到堆栈中有任何节点为止。在每个步骤中，我们都会获得堆栈中的顶级节点，如果它不为 null，并且我们以前没有访问过它，那么我们就会访问它并将其所有子节点添加到堆栈中。

队列通常用于BFS。

伪代码：

queue my_queue;
list visited_nodes;
my_queue.enqueue(starting_node);

while my_queue.length > 0
   current_node = my_queue.dequeue();

   if current_node == null
       continue;
   if current_node in visited_nodes
      continue;
   visited_nodes.add(current_node);

   // visit node, get the class or whatever you need

   foreach child in current_node.children
      my_queue.enqueue(child);

此代码将一直持续到队列中有任何节点。在每个步骤中，我们都会获得队列中的第一个节点，如果它不为空并且我们以前没有访问过它，那么我们将访问它并将其所有子节点添加到队列中。

请注意，这两种算法之间的主要区别是我们使用的数据类型。