We have already introduced some techniques for traversing binary trees:

1- Traversing through binary tree using recursive and iterative algorithms

2- Traversing through binary tree using parent pointers

This article will put what you’ve learned into practice and see how to traverse the DOM. We will not use getElementById, getElementsByClassname or querySelector/querySelectorAll under the premise of these built-in API, look at how to find the DOM elements through different selectors. This article will also help you understand the underlying workings of these apis.

DOM traversal overview

Borrowing the idea of the first article, we first give the algorithm for DOM sequential traversal:

function walkPreOrder(node){ if(! Console. log(node) for(let child of node.children){walkPreOrder(child)}}Copy the code

We can also modify the algorithm to return an iterator:

function* walkPreOrder(node){ if(! Yield node for(let child of node.children){yield* walkPreOrder(child)} walkPreOrder(root)){ console.log(node) }Copy the code

To traverse the DOM, you can use any of the breadth – or depth-first algorithms discussed in previous articles. But for this article, we’ll just focus on the above approach.

Suppose the document we want to traverse has the following HTML structure:

<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>
Copy the code

Find nodes by ID

The browser provides the Document.getelementById () API for this purpose. This is easy to do with walkPreOrder(). To see:

Function locateById(nodeId){for(let node of walkPreOrder(document.body)){function locateById(nodeId){for(let node of walkPreOrder(document.body)){ if(node.id === nodeId){ return node } } return null }Copy the code

You can use the locateById() function like this:

Const img = locateById('profile'Copy the code

Find nodes by class name

Browser provides for this document. The getElementsByClassName () this API. Here’s how to do something similar:

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')
Copy the code

How does the browser optimize this selection query

Selecting a DOM node is a very frequent operation for Web applications. It is definitely not optimal to traverse the DOM tree multiple times to query the same selector. The browser uses Memoization to optimize this operation.

Here is the source code for the Mozilla parser, taken from the startTag function:

// 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)); }}Copy the code

As you can see, the node IDS are put into a simple hash table. We can take a similar approach to ensure that repeated queries on the same ID do not need to be fully traversed, but simply look for the hash table to return.

Here’s what happens when we add the staging:

Function getSelectors(){const idLocations = {} const classLocations = {} if(idLocations.hasOwnProperty(nodeId)) return idLocations[nodeId] for(let node of walkPreOrder(document.body)){ If (node.id === nodeId){idLocations[nodeId]= 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 foundCopy the code

Handle more complex selectors

Let’s try something like element.querySelector. Here’s how MDN describes it:

The querySelector() method of the Element interface returns the first Element in the descendant of the current Element that matches the specified selector group.

Example:

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

We can pass any selector to this function, and it will traverse the DOM to find the appropriate element for us. Here’s how to do it:

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')Copy the code

The implementation (similar to Element.querySelectorAll) of myQuerySelectorAll is similar:

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
}
Copy the code

pleasantly surprised

You can clone any tree using the recursive preemptive traversal described at the beginning of this article. Let’s see how it can clone any DOM tree, similar to what element.clonenode (true) does:

  • Create a clone of the source node, that is, create a new node with the same label name and copy all properties.
  • Calls recursively on all child elements of the source nodecloneTreeMethod to append the returned node as a child element to the cloned node.
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 }Copy the code