深度优先遍历和广度优先遍历

以html节点为列进行深度优先和广度优先遍历

<div class="parent">
  <div class="child-1">
    <div class="child-1-1">
      <div class="child-1-1-1">
        1-1-1
      </div>
    </div>
    <div class="child-1-2">
      <div class="child-1-2-1">
        1-2-1
      </div>
      <div class="child-1-2-2">
        1-2-2
      </div>
    </div>
    <div class="child-1-3">
      1-3
    </div>
  </div>
  <div class="child-2">
    <div class="child-2-1">
      2-1
    </div>
    <div class="child-2-2">
      <div class="child-2-2-1">
        2-2-1
      </div>
    </div>
  </div>
  <div class="child-3">
    <div class="child-3-1">
      3-1
    </div>
  </div>
</div>

1. 深度优先遍历

• 递归

// 方法1，传参保存结果
function deepTraversal1(node, nodeList = []) {
  if (node) {
    nodeList.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      deepTraversal1(children[i], nodeList)
    }
  }
  return nodeList
}
let result = deepTraversal1(document.querySelector(".parent"))
console.log(result)

// 方法2，concat拼凑结果
function deepTraversal2(node) {
  let nodeList = []
  if (node) {
    nodeList.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      nodeList = nodeList.concat(deepTraversal2(children[i]))
    }
  }
  return nodeList
}
let result = deepTraversal2(document.querySelector(".parent"))
console.log(result)

• 非递归，栈表示法

function deepTraversal3(node) {
  let stack = [], nodeList = []
  if (node) {
    stack.push(node)
    let children = node.children
    while(stack.length) {
      let item = stack.pop()
      nodeList.push(item)
      let children = item.children
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
  }
  return nodeList
}

let result = deepTraversal3(document.querySelector(".parent"))
console.log(result)

深度优先遍历

2. 广度优先遍历

• 队列表示法

function widthTraversal(node) {
  let queue = [], nodeList = []
  if (node) {
    queue.push(node)
    while(queue.length) {
      let item = queue.shift()
      let children = item.children
      nodeList.push(item)
      for (let i = 0; i < children.length; i++) {
        queue.push(children[i])
      }
    }
  }
  return nodeList
}

广度优先遍历