The data structure

const data = [{
  name: 'a'.children: [{name: 'a1'.children: [{name: 'a11' },
        { name: 'a12']}, {},name: 'a2' },
    { name: 'a3'},],}, {name: 'b'.children: [{name: 'b1' },
      { name: 'b2' },
      { name: 'b3'}],}]Copy the code

Graphical data

1, depthFirstSearch – depthFirstSearch

  • You go down the node level by level, and then you go back to the node and continue searching

Find the order

code

// Recurse, find a node down, put res, child node also
const data = [...]
function depthFirstSearch(data, res = []) {
  data.forEach(i= >{
    res.push(i.name)
    if(i.hasOwnProperty('children')) {// If there are child elements, continue the search
      depthFirstSearch(i.children, res)
    }
  })
  return res
}
console.log('Depth-first traversal order', depthFirstSearch(data))
/ / depth-first traversal sequence (10) [' a ', 'a1', 'a11', 'a12', 'a2, a3', 'b', 'b1, b2, b3']
Copy the code

2. BreadthFirstSearch – breadthFirstSearch

  • Using the characteristics of queues, each layer is queued, first in, first out

Find the order

code

// Create an execution queue and terminate when the queue is empty
function breadthFirstSearch(data) {
  let queue = []// Simulate a queue, first in first out
  let res = [] // Store sequence set - result
  queue = JSON.parse(JSON.stringify(data)) // Assign a deep copy
  while (queue.length > 0) {
    let item = queue.shift()// Remove the first item from the queue
    res.push(item.name) // The order in which values are stored
    if (item.hasOwnProperty('children')) { // Queue again if there are child nodesqueue.push(... item.children) } }return res
}
console.log('Breadth first',breadthFirstSearch(data))
/ / breadth first (10) [' a ', 'b', 'a1, a2, a3', 'b1, b2, b3,' a11 ', 'a12]
Copy the code

Code parsing

  • For the first time,Queue = [a, b]
  • The second time, theaPut in the result set,Result set = [a].Queue = [b]And found thataI have children, I queue them,Queue = [b, A1, A2, A3]
  • The third timebPut in the result set,Result set = [a, b].Queue = [A1, A2, A3]And found thatbI have children, I queue them,Queue = [A1, A2, A3, B1, B2,b3]
  • And so on. We found out it’s first in, first out, so it’s a queue.

Usage scenarios

  • If the tree is deep, use breadth-first search.
  • If the tree is wide, use depth-first search.