DOM樹遍歷之JS實現DFS&BFS

imccl 發布于2019-08-20 15:52 / 1372人閱讀

摘要：對于上面例子遍歷結果應為則總是先遍歷當前層級的所有節點，只有當當前層級所有節點都遍歷結束后才會進入下一層級。

我們一般可以采用DFS（深度優先遍歷）和BFS（廣度優先遍歷）來遍歷DOM樹

介紹 DFS & BFS

我們來結合具體例子進行分析，給出HTML代碼片段如下：

DFS總是先進入下一級節點，只有當下一級沒有未遍歷的子節點時才會進入到當前層級的其它節點。對于上面例子DFS遍歷結果應為：

root, container, sidebar, menu, main, post, copyright

BFS則總是先遍歷當前層級的所有節點，只有當當前層級所有節點都遍歷結束后才會進入下一層級。對于上面例子BFS遍歷結果應為：

root, container, sidebar, main, menu, post, copyright

DFS的具體實現

DFS主要采用遞歸實現，依次遍歷節點，如果遍歷到的節點有子節點，則開始遍歷子節點

const DFSTraverse = (rootNodes, rootLayer) => {
      const roots = Array.from(rootNodes)
      while (roots.length) {
        const root = roots.shift()
        printInfo(root, rootLayer)
        // 如果有子節點，直接遍歷子節點，同時將層級加1
        if (root.children.length) {
          DFSTraverse(root.children, rootLayer + 1)
        }
      }
    }

BFS的具體實現

BFS采用隊列的思想，采用出隊的方式遍歷節點，如果遍歷到的節點有子節點，則將子節點入隊（這里處理節點層級的方式比DFS更復雜一些，因為這里將所有節點都放到了同一個數組中進行處理）

const BFSTraverse = (rootNodes, rootLayer) => {
      const roots = Array.from(rootNodes)
      const rootsLayer = [] // 單用一個數組存放每個節點的的層級
      // 初始化
      for (let i = 0; i < roots.length; i++) {
        rootsLayer.push(rootLayer)
      }
      var rootIdx = 0 // 記錄當前處理roots中的第幾個節點，方便查找rootsLayer中對應的層級
      while (roots.length) {
        const root = roots.shift() // 出隊
        printInfo(root, rootsLayer[rootIdx])
        // 如果有子節點，將子節點放到roots隊列中
        if (root.children.length) {
          Array.prototype.push.apply(roots, Array.from(root.children))
          // 將當前層級加1得到子節點的層級
          rootLayer = rootsLayer[rootIdx] + 1
          for (let i = 0; i < root.children.length; i++) {
            rootsLayer.push(rootLayer)
          }
        }
        // 處理下一個root節點
        rootIdx++
      }
    }

結果

先給大家補全代碼：

// 輸入節點信息
const printInfo = (node, layer) => {
      var str = ""
      for (let i = 1; i < layer; i++) {
        str += " "
      }
      console.log(`${layer}:${str}${node.tagName} .${node.className}`);
    }

console.log("DFS *******************************");
DFSTraverse(document.querySelectorAll(".root"), 1);
console.log("BFS *******************************");
BFSTraverse(document.querySelectorAll(".root"), 1);

上面例子的運行結果為：

參考

破解前端面試（80% 應聘者不及格系列）：從 DOM 說起
Javascript-ONLY DOM Tree Traversal - DFS and BFS?

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/82556.html

DOM樹遍歷之JS實現DFS&amp;BFS

摘要：對于上面例子遍歷結果應為則總是先遍歷當前層級的所有節點，只有當當前層級所有節點都遍歷結束后才會進入下一層級。我們一般可以采用DFS（深度優先遍歷）和BFS（廣度優先遍歷）來遍歷DOM樹介紹 DFS & BFS 我們來結合具體例子進行分析，給出HTML代碼片段如下： DFS總是先進入下一...

fengxiuping 2019-08-01 16:40 評論0 收藏0
JS算法之深度優先遍歷(DFS)和廣度優先遍歷(BFS)

摘要：算法之深度優先遍歷和廣度優先遍歷背景在開發頁面的時候，我們有時候會遇到這種需求在頁面某個節點中遍歷，找到目標節點，我們正常做法是利用選擇器，或者，但在本文，我們從算法的角度去查找節點，同時理解一下深度優先遍歷和廣度優先遍歷的原理。 JS算法之深度優先遍歷(DFS)和廣度優先遍歷(BFS) 背景在開發頁面的時候，我們有時候會遇到這種需求：在頁面某個dom節點中遍歷，找到目標dom節點，...

roadtogeek 2019-08-23 16:33 評論0 收藏0
JavaScript樹結構深度優先算法

　　什么是樹　　現實中樹隨處可見；在計算機世界，樹就是一種分層結構的抽象模型?！　∪缦聢D所示：　　樹結構的可以用在很多情景，就如下圖公司的組織架構，用樹就可以表達出來，如下圖：　　組織架構只是其中之一，比如族譜、省市等用樹的結構形式展現是完全可以?！　涞男g語　　樹有很多的術語，如下圖：　　樹：n(n≥0)個節點所構成的有限集合，當n=0時，稱為空樹；　　節點的度：節點的子樹個數，例如B節點的度就...

3403771864 2022-09-19 22:06 評論0 收藏0
用JavaScript來學習樹「譯」

摘要：樹可謂是開發者最常碰到的數據結構之一了要知道整張網頁就是一棵樹啊所以我們就來學習樹這一數據結構吧在這篇文章中我們將創建一棵樹并且用兩種不同的方法來遍歷它深度優先遍歷和寬度廣度優先遍歷方法使用借助棧這一數據結構來訪問樹的每個節點則借助了隊樹可謂是web開發者最常碰到的數據結構之一了. 要知道, 整張網頁就是一棵DOM樹啊 (Document Object Model ). 所以我...

Youngdze 2019-08-22 11:05 評論0 收藏0
js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現與非遞歸實現)

摘要：樹中結點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結構等中序遍歷可以實現表達式樹，在編譯器底層很有用后序遍歷可以用來實現計算目錄內的文件及其信息等。樹的簡介棧、隊列、鏈表等數據結構，都是順序數據結構。而樹是非順序數據結構。樹型結構是一類非常重要的非線性結構。直觀地，樹型結構是以分支關系定義的層次結...

Yuanf 2019-08-23 11:38 評論0 收藏0