对DOM应用树遍历算法

我们已经介绍了一些遍历二叉树的技术：

1- Traversing through binary tree using recursive and iterative algorithms

2- Traversing through binary tree using parent pointers

本文将学以致用，看看怎么对DOM进行遍历。我们会在不使用getElementById、getElementsByClassname或querySelector/querySelectorAll这些内置API的前提下，看看怎么通过不同的选择器找到DOM元素。因此通过本文也可以了解这些API的底层工作原理。

DOM遍历概述

借用第一篇文章的思想，我们先给出对DOM进行先序遍历的算法：

function walkPreOrder(node){
  if(!node) return

  // 做些什么
  console.log(node)

  for(let child of node.children){
     walkPreOrder(child)
  }
}

也可以修改这个算法，让它返回迭代器：

function* walkPreOrder(node){
  if(!node) return

  // 做些什么
  yield node
  for(let child of node.children){
    yield* walkPreOrder(child)
  }
}

// 用法
for(let node of walkPreOrder(root)){
  console.log(node)
}

要遍历DOM，可以使用之前文章中讨论过的任何广度或深度优先算法。但在本文中，我们只关注上面这种方式。

假设我们要遍历的文档有下面这样的HTML结构：

<html>
  <head>
    <title>DOM selection algorithm</title>
  </head>
<body>

  <div class="container">
    <div class="body">
      <div class="row">
        <img id="profile" src="xyz.jpg" alt="">
      </div>
      <div class="row"></div>
      <div class="row"></div>
    </div>
  </div>

</body>
</html>

通过ID查找节点

浏览器为此提供了document.getElementById() 这个API。而使用walkPreOrder()很容易实现这个操作。来看：

function locateById(nodeId){
  // 以深度优先（preOrder）方式迭代所有节点
  // 找到节点之后立即返回
  for(let node of walkPreOrder(document.body)){
     if(node.id === nodeId){
        return node
     }
  }
   return null
}

可以像这样使用locateById()函数：

const img = locateById('profile')
// 返回图片节点

通过类名查找节点

浏览器为此提供了document.getElementsByClassName() 这个API。下面看看怎么实现类似的操作：

function locateAllByClassName(className){
   const result = []
   for(let node of walkPreOrder(document.body)){
      if(node.classList.contains(className)){
        result.push(node)
      }
   }
   return result
}

// 用法
const elements = locateAllByClassName('row')

浏览器怎么优化这种选择查询

对Web应用来说，选择DOM节点是非常高频的操作。为查询相同的选择器而多次遍历DOM树肯定不是最优的。浏览器使用暂存（memoization）来优化这个操作。

这里是Mozilla解析器的源代码，节选自startTag函数：

 // ID uniqueness
 @IdType String id = attributes.getId();
 if (id != null) {
      LocatorImpl oldLoc = idLocations.get(id);
      if (oldLoc != null) {
            err("Duplicate ID \u201C" + id + "\u201D.");
            errorHandler.warning(new SAXParseException(
                  "The first occurrence of ID \u201C" + id
                  + "\u201D was here.", oldLoc));
       } else {
            idLocations.put(id, new LocatorImpl(tokenizer));
       }
 }

可以看到，节点ID被放到了一个简单的散列表里。我们可以采用类似的办法，确保对相同ID的重复查询不需要完全遍历，只要查找散列表返回就行了。

下面是我们添加了暂存之后的结果：

function getSelectors(){
  const idLocations = {}
  const classLocations = {}

  // 更新后的选择器函数
  function locateById(nodeId){
    if(idLocations.hasOwnProperty(nodeId)) 
       return idLocations[nodeId]

    for(let node of walkPreOrder(document.body)){
       if(node.id === nodeId){
          idLocations[nodeId]= node // 暂存
          return node
       }
     }
    idLocations[nodeId]= null // 暂存
    return null
  }

  function locateAllByClassName(className){
    if(classLocations.hasOwnProperty(className)) 
         return classLocations[className]

    const result = []
    for(let node of walkPreOrder(document.body)){
       if(node.classList.contains(className)){
          result.push(node)
        }
     }
     classLocations[nodeId]= result
     return result
  }

  return {
       locateById,
       locateAllByClassName
    }

} 

  // 用法
  const {locateById, locateAllByClassName} = getSelectors();
  const result = locateAllByClassName('row') // returns array of elements
  const img = locateById('profile') // returns an element, if found

处理更复杂的选择器

下面我们试试类似element.querySelector的功能。MDN是这么介绍它的：

Element接口的querySelector()方法返回当前元素后代中与指定选择器组匹配的第一个元素。

例子：

const firstRow = document.querySelector('.container .row:first-child')

我们可以给这个函数传任何选择器，然后它会遍历DOM替我们找到相应的元素。下面看看可以怎么实现：

function myQuerySelector(selector){
  const path = selector.split(' ').map(str => str.trim())

  let currentNode = document.body
  while(path.length && currentNode){

    const currentSelector = path.shift()
    let found = false

    for(let node of walkPreOrder(currentNode)){
      if(node.matches(currentSelector)){
        currentNode = node
        found = true
        break
      }
    }

    if(!found) currentNode = null
  }
  return currentNode
}

// 用法
const firstRow = myQuerySelector('.container .row:first-child')

实现（类似element.querySelectorAll的）myQuerySelectorAll也差不多：

function myQuerySelectorAll(selector){
  const path = selector.split(' ').map(str => str.trim())
  const result = []

  let currentNode = document.body
  while(path.length && currentNode){

    const currentSelector = path.shift()

    for(let node of walkPreOrder(currentNode)){
      if(node.matches(currentSelector)){
        currentNode = node
        result.push(currentNode)
      }
    }
  }
  return result
}

惊喜

可以使用本文开始描述的递归先序遍历克隆任何树。我们下面看看怎么通过它克隆任意DOM树，类似element.cloneNode(true) 所做的：

创建源节点的克隆，即使用相同的标签名创建一个新节点，并复制所有属性。
在源节点所有子元素上递归调用 cloneTree方法，将返回的节点作为子元素追加到克隆的节点。

function cloneTree(node){
  if(!node) return

  const clonedNode = document.createElement(node.tagName.toLowerCase())
  const attributes = node.getAttributeNames()

  attributes.forEach(attribute => {
     clonedNode.setAttribute(attribute, node.getAttribute(attribute))
  })

  for(const child of node.children){
      clonedNode.append(cloneTree(child))
  }

  return clonedNode
}