JS DOM先序遍历：递归、迭代、NodeIterator与TreeWalker实战

DOM树先序遍历概述

DOM树是由文档中所有节点（包括元素节点、文本节点及注释节点等）构成的层级结构，其解析与构建是浏览器运行的核心功能之一。鉴于DOM树本质上是树形结构，我们可以应用通用的树遍历算法来处理它。此外，DOM2标准中的“Traversal”模块引入了两种新类型，使得实现DOM树的先序遍历变得更加便捷。

注：本文介绍的5种方法均针对DOM进行先序遍历（即深度优先遍历），且仅关注Element类型节点。

基于DOM1接口的递归与迭代实现

1. 使用DOM1中的基础接口，递归遍历DOM树

DOM1为基础类型Node提供了一系列API，支持基础的DOM操作。利用递归方式遍历DOM树的代码逻辑较为直观，其核心思路是先处理当前节点，随后从左至右递归遍历其子节点。具体实现代码如下：


/**
  * 使用递归的方式先序遍历DOM树
  * @param node 根节点
  */
 function traversal(node){
   //对node的处理
   if(node && node.nodeType === 1){
     console.log(node.tagName);
   }
   var i = 0, childNodes = node.childNodes,item;
   for(; i < childNodes.length ; i++){
     item = childNodes[i];
     if(item.nodeType === 1){
       //递归先序遍历子节点
       traversal(item);
     }
   }
 }

2. 使用DOM1的基础接口，迭代遍历DOM树

与第一种递归方法不同，此处采用迭代方式遍历DOM树。迭代实现相对复杂，关键在于使用栈来维护节点的访问路径。处理完当前节点后，需将该节点的第一个Element子节点设为下一轮循环的根节点，并按从右到左的顺序将其他子元素压入栈中。若当前节点无Element子节点，则从栈中弹出节点作为新的根节点，直至栈为空。具体实现代码如下：


/**
 * 使用迭代的方式先序遍历DOM树
 * @param node 根节点
 */
function traversalIteration(node){
  var array = [], i = 0,k = 0,elementCount = 0, len = 0, childNodes,item;
  while(node != null){
    console.log(node.tagName);
    childNodes = node.childNodes;
    len = node.childNodes.length;
    elementCount = 0;
    if(len > 0){
      for(i = 0; i < len; i++){
        item = childNodes[i];
        if(item.nodeType === 1){
          elementCount++;
          node = item;
          break;
        }
      }
      for(k = len -1 ; k > i; k--){
        item = childNodes[k];
        if(item.nodeType == 1){
          elementCount++;
          array.push(item);
        }
      }
      if(elementCount < 1){
        node = array.pop();
      }
    }else{
      node = array.pop();
    }
  }
}

基于DOM扩展API的递归遍历

3. 使用DOM扩展的Element Traversal API，递归遍历DOM树

DOM Element Traversal API提供了一系列便捷接口，简化了获取节点Element子节点的过程。在《DOM扩展：DOM API的进一步增强[总结篇-上]》的第2节中已介绍过该API。具体实现代码如下：


/**
 * 使用DOM扩展的Traversal API提供的新的接口先序遍历DOM树
 * @param node 根节点
 */
function traversalUsingTraversalAPI(node){
  if(node && node.nodeType === 1){
    console.log(node.tagName);
  }
  var i = 0,len = node.childElementCount, child = node.firstElementChild;
  for(; i < len ; i++){
    traversalUsingTraversalAPI(child);
    child = child.nextElementSibling;
  }
}

使用NodeIterator与TreeWalker遍历

4. 使用NodeIterator

DOM2的“Traversal”模块提供了NodeIterator类型，利用它可以轻松实现DOM树的先序遍历。《JavaScript高级程序设计第三版》的12.3.1节对此类型进行了详细介绍，此处直接给出具体实现代码：


/**
 * 使用DOM2的"Traversal"模块提供的NodeIterator先序遍历DOM树
 * @param node 根节点
 */
function traversalUsingNodeIterator(node){
  var iterator = document.createNodeIterator(node, NodeFilter.SHOW_ELEMENT,null,false);
  var node = iterator.nextNode();
  while(node != null){
    console.log(node.tagName);
    node = iterator.nextNode();
  }
}

5. 使用TreeWalker

TreeWalker类型可视为NodeIterator的增强版，《JavaScript高级程序设计第三版》的12.3.2节对此进行了介绍。此处同样直接给出具体实现代码：


/**
 * 使用DOM2的"Traversal"模块提供的TreeWalker先序遍历DOM树
 * @param node 根节点
 */
function traversalUsingTreeWalker(node){
  var treeWalker = document.createTreeWalker(node, NodeFilter.SHOW_ELEMENT,null,false);
  if(node && node.nodeType === 1){
    console.log(node.tagName);
  }
  var node = treeWalker.nextNode();
  while(node != null){
    console.log(node.tagName);
    node = treeWalker.nextNode();
  }
}

以上即为JavaScript实现DOM树先序遍历的五种方法分享，希望对读者的学习与实践有所帮助。

JavaScript实现DOM树先序遍历的5种方法详解

DOM树先序遍历概述

基于DOM1接口的递归与迭代实现

基于DOM扩展API的递归遍历

使用NodeIterator与TreeWalker遍历

实用工具推荐