Javascript-ONLY DOM Tree Traversal - DFS和BFS？

Question

任何人都可以提供代码,伪代码,甚至提供在纯JavaScript(无JQuery或任何帮助库)中实现DFS和BFS的良好链接？我一直试图理解如何实现任一遍历,但我似乎无法真正区分BFS和DFS实现的区别.

如果我们想要一个具体问题作为一个例子:我想在给定节点遍历DOM,并获取所有类名.

(我能想到遍历的唯一方法是遍历每个父节点,从该节点得到我需要的东西,在这个例子中是类名,然后看看他们是否有孩子,为每个孩子递归.我相信这是DFS ？同样,我很难理解DOM遍历实现中的差异!)

最后,对不起,如果这是重复.我到处寻找好的,明确的例子,但没有找到任何好的答案!如果那里有一个很好的答案,请告诉我:)

Answer 1

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

此代码将一直存在,直到队列中有任何节点.在每个步骤中,我们得到队列中的第一个节点,如果它不是null,并且如果我们之前没有访问它,那么我们访问它并将其所有子节点添加到队列中.

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

Answer 2

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

这会循环遍历元素，将它们的子元素推入堆栈，然后从每个元素重新开始。如您所见，这消耗了更多的空间（子数组），这不是最好的......

Answer 3

对于 DFS，您可以使用TreeWalker或NodeIterator API 并使用NodeFilter.SHOW_ELEMENT.