JavaScript-only DOM樹遍歷 - DFS和BFS？

Question

任何人都可以提供代碼，僞代碼，甚至提供良好的鏈接來實現DFS和BFS在普通的JavaScript（沒有JQuery，或任何幫助庫）？我一直在試圖理解如何實現遍歷，但我似乎無法真正區分BFS和DFS實現的區別。

如果我們想要一個具體的問題作爲例子：我想在給定的節點遍歷DOM，並獲取所有的類名。

（我認爲遍歷的唯一方法是遍歷每個父節點，從該節點獲取我需要的內容，在這個例子中是類名，然後看看他們是否有孩子，爲每個孩子遞歸。相信這是DFS？再一次，我很難理解DOM遍歷實現方式的差異！）

最後，如果這是重複，請對不起。我到處搜索了好的，清晰的例子，但沒有找到任何好的答案！如果已經有一個很好的答案在那裏，請讓我知道:)

Answer 1

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

該循環槽的元素，推動他們的孩子到棧上，並與他們的eeach再次啓動。正如你所看到的，這會消耗更多的空間（孩子的陣列）至極是不是最好的...

Answer 2

讓我們用下面的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。

僞代碼：

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

該代碼會去，直到有棧中的任何節點。在每一步中，我們都得到堆棧中的頂層節點，如果它不是空的，並且我們之前沒有訪問它，那麼我們將訪問它並將其所有子節點添加到堆棧中。

Queue通常用於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 3

對於DFS，您可以使用TreeWalker或NodeIterator API和NodeFilter.SHOW_ELEMENT進行過濾。