Javascript-ONLY DOM树遍历- DFS和BFS

Javascript-ONLY DOM Tree Traversal - DFS and BFS?

本文关键字：DFS BFS 遍历 DOM Javascript-ONLY      更新时间：2023-09-26

谁能提供代码，伪代码，甚至提供良好的链接实现DFS(深度优先搜索)和BFS(广度优先搜索)在纯JavaScript(没有JQuery，或任何辅助库)?我一直在努力理解如何实现这两种遍历，但我似乎无法真正区分BFS和DFS实现的区别。

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

(我能想到遍历的唯一方法是遍历每个父节点，从该节点(在本例中是类名)获得我需要的内容，然后查看它们是否有子节点，对每个子节点递归。我想这是DFS吧?同样，我很难理解DOM遍历实现中的差异!)

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

让我们以以下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);

此代码将一直运行，直到堆栈中有任何节点。在每一步中，我们获得堆栈中的顶部节点，如果它不是空的，如果我们之前没有访问过它，我们就访问它，并将它的所有子节点添加到堆栈中。

队列通常用于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);

此代码将一直运行，直到队列中有任何节点为止。在每一步中，我们获得队列中的第一个节点，如果它不是空的，如果我们之前没有访问过它，我们就访问它，并将它的所有子节点添加到队列中。

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

DFS:

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

循环遍历所有元素，对于每个元素循环遍历每个子元素，以此类推。

BFS: 

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

循环遍历元素，将它们的子元素压入堆栈，然后从每个元素重新开始。正如您所看到的，这会消耗更多的空间(子数组)，这不是最好的…

对于DFS，您可以使用TreeWalker或NodeIterator API和NodeFilter.SHOW_ELEMENT过滤器。

相关文章：