DOM树遍历之JS实现DFS&BFS

imccl 发布于2019-08-20 15:52 / 1333人阅读

摘要：对于上面例子遍历结果应为则总是先遍历当前层级的所有节点，只有当当前层级所有节点都遍历结束后才会进入下一层级。

我们一般可以采用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?

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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树结构深度优先算法

　　什么是树　　现实中树随处可见；在计算机世界，树就是一种分层结构的抽象模型。　　如下图所示：　　树结构的可以用在很多情景，就如下图公司的组织架构，用树就可以表达出来，如下图：　　组织架构只是其中之一，比如族谱、省市等用树的结构形式展现是完全可以。　　树的术语　　树有很多的术语，如下图：　　树：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