【前端100问】Q5：介绍下深度优先遍历和广度优先遍历，如何实现

写在前面

此系列来源于开源项目：前端 100 问：能搞懂 80%的请把简历给我
为了备战 2021 春招
每天一题，督促自己
从多方面多角度总结答案，丰富知识
介绍下深度优先遍历和广度优先遍历，如何实现？

正文回答

<div class="parent">
  <div class="child-1">
    <div class="child-1-1">
      <div class="child-1-1-1">a</div>
    </div>
    <div class="child-1-2">
      <div class="child-1-2-1">b</div>
    </div>
    <div class="child-1-3">c</div>
  </div>
  <div class="child-2">
    <div class="child-2-1">d</div>
    <div class="child-2-2">e</div>
  </div>
  <div class="child-3">
    <div class="child-3-1">f</div>
  </div>
</div>

深度优先遍历 DFS 与树的先序遍历比较类似

找到一个节点后，把它的后辈都找出来，最常用递归法。

let deepTraversal1 = (node, nodeList = []) => {
  if (node !== null) {
    nodeList.push(node);
    let children = node.children;
    for (let i = 0; i < children.length; i++) {
      deepTraversal1(children[i], nodeList);
    }
  }
  return nodeList;
};

let deepTraversal2 = (node) => {
  let nodes = [];
  if (node !== null) {
    nodes.push(node);
    let children = node.children;
    for (let i = 0; i < children.length; i++) {
      nodes = nodes.concat(deepTraversal2(children[i]));
    }
  }
  return nodes;
};

// 非递归
let deepTraversal3 = (node) => {
  let stack = [];
  let nodes = [];
  if (node) {
    // 推入当前处理的node
    stack.push(node);
    while (stack.length) {
      let item = stack.pop();
      let children = item.children;
      nodes.push(item);
      // node = [] stack = [parent]
      // node = [parent] stack = [child3,child2,child1]
      // node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
      // node = [parent, child1-1] stack = [child3,child2,child1-2]
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i]);
      }
    }
  }
  return nodes;
};

广度优先遍历

找到一个节点后，把他同级的兄弟节点都找出来放在前边，把孩子放到后边，最常用 while

let widthTraversal2 = (node) => {
  let nodes = [];
  let queue = [];
  if (node) {
    queue.push(node);
    while (queue.length) {
      let item = queue.shift();
      let children = item.children;
      nodes.push(item);
      // 队列，先进先出
      // nodes = [] queue = [parent]
      // nodes = [parent] queue = [child1,child2,child3]
      // nodes = [parent, child1] queue = [child2,child3,child1-1,child1-2]
      // nodes = [parent,child1,child2]
      for (let i = 0; i < children.length; i++) {
        queue.push(children[i]);
      }
    }
  }
  return nodes;
};

应用场景

对象的深拷贝