仅限Java的DOM树遍历-DFS和BFS？ [英] Javascript-ONLY DOM Tree Traversal - DFS and BFS?

问题描述

任何人都可以提供代码，伪代码，甚至提供良好的链接，以纯JavaScript（无JQuery或任何帮助程序库）实现DFS和BFS吗？我一直在尝试了解如何实现这两种遍历，但似乎无法真正区分BFS和DFS实现的区别。

Can anyone provide either code, pseudocode, or even provide good links to implementing DFS and BFS in plain JavaScript (No JQuery, or any helper libraries)? I've been trying to understand how to implement either traversal, but I can't seem to really distinguish the difference of a BFS and DFS implementation.

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

If we want a concrete problem as an example: I want to traverse down the DOM at a given node, and get all the class names.

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

(The only way I can think to traverse is to go through each parent node, get what I need from that node which in this example is the class name, then see if they have children, recurse for each child. I believe this is DFS? Again, I'm having a hard time understanding the differences in a DOM traversal implementation!)

最后，抱歉一个重复。我到处搜索了很好的清晰示例，但没有找到任何好的答案！如果已经有了一个好的答案，请告诉我:)

Finally, sorry if this is a repeat. I've searched everywhere for good, clear examples but haven't found any great answers! If there's already a good answer out there, please let me know :)

推荐答案

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

Let's use the following HTML code as an example:

<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将始终首先进入下一级别的节点，并且仅当没有更多的un-遍历的子节点将移至当前级别的下一个节点。

DFS will always go to the next level of nodes first, and only if there are no more un-traversed child nodes will it step to a next node on the current level.

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

A DFS would traverse the nodes of the example in the following order:

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

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

BFS will always traverse all the nodes in the current level first and only after that will it go to the next level of nodes.

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

A BFS would traverse the nodes of the example in the following order:

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

没有明确的答案，您应该使用其中之一。通常，这取决于您的需求。

There isn't a definite answer which one of these you should use. Usually it depends on your needs.

实施细节：

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

For a DFS people often use a stack.

伪代码：

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，并且如果我们之前没有访问过它，那么我们将访问它并将其所有子节点添加到堆栈中。

This code will go until there is any nodes in the stack. In each step we get the top node in the stack and if it's not null and if we haven't visited it before than we visit it and add all its children to the stack.

队列通常用于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，并且如果我们之前没有访问过它，那么我们将访问它并将其所有子节点添加到队列中。

This code will go until there is any nodes in the queue. In each step we get the first node in the queue and if it's not null and if we haven't visited it before than we visit it and add all its children to the queue.

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

Note that the main difference between the two algorithm is the data type we use.

这篇关于仅限Java的DOM树遍历-DFS和BFS？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！