深广度优先遍历

之前其实有写过一篇类似的文章《深度优先遍历(DFS)-栈和广度优先遍历(BFS)-队列的理解》
再次复习一下,写了不一样的注释。而且之前是用 dom 做的遍历,这次还是回到数据来。

// 深广度优先遍历

const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        {
          value: 4,
          children: [
            {
              value: 8
            },
            {
              value: 9
            },
          ],
        },
        {
          value: 5,
          children: [
            {
              value: 10
            },
            {
              value: 11
            },
          ],
        },
      ],
    },
    {
      value: 3,
      children: [
        {
          value: 6,
          children: [
            {
              value: 12
            },
            {
              value: 13
            },
          ],
        },
        {
          value: 7,
          children: [
            {
              value: 14
            },
            {
              value: 15
            },
          ],
        },
      ],
    }
  ],
};

// 深度优先,递归解法
// 最好理解的做法,检测到一个节点有 children,就递归遍历
// 一直挖到没有,就返回上一个节点的兄弟节点继续遍历
function deepthTraversal1(tree) {
  const arr = [];
  function recursion(node) {
    if (!node) return;
    arr.push(node.value);
    if (node.children) {
      node.children.forEach(child => {
        recursion(child);
      });
    }
  }
  recursion(tree);
  return arr;
}

// 深度优先,栈解法
// 每一轮遍历先把当前节点的值访问了,再遍历其子节点
// 利用队列先进后出特性,右边进去右边出,
// 一开始是[1],这轮循环把 1 的 children 都遍历了,循环这次后是[3,2]
// !!!注意这里遍历是倒序的,所以会是先3后2,正序也可以,只是这样的深度顺序就不一样,倒序遍历的结果好理解
// 第二次是[3,2],这轮循环把 2 的 children 都遍历了,循环这次后是[3,5,4]
// 第三次是[3,5,4],这轮循环把 4 的 children 都遍历了,循环这次后是[3,5,9,8]
// 以此类推,按层级来看,就是把相同层级 L 的节点在同次循环中加入
// 然后它们的子层级也就是相同的 L+1 节点,会在遍历 L 节点 children 时候加入
// 这样由于先进后出,每个节点的子节点后加入栈,反而会先被访问到
// 变成访问 L 节点,下次访问它的子节点 L+1,下次是它的孙节点,L+1+1,这样达到深度优先效果
function deepthTraversal2(tree) {
  const arr = [];
  const stack = [tree];
  while(stack.length) {
    const node = stack.pop();
    arr.push(node.value);
    const children = node.children;
    if (children && children.length) {
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i]);
      }
    }
  }
  return arr;
}

// 广度优先,队列解法
// 每一轮遍历先把当前节点的值访问了,再遍历其子节点
// 利用队列先进先出特性,右边进去左边出,
// 一开始是[1],这轮循环把 1 的 children 都遍历了,循环这次后是[2,3]
// 第二次是[2,3],这轮循环把 2 的 children 都遍历了,循环这次后是[3,4,5]
// 第三次是[3,4,5],这轮循环把 3 的 children 都遍历了,循环这次后是[4,5,6,7]
// 以此类推,按层级来看,就是把相同层级 L 的节点在同次循环中加入
// 然后它们的子层级也就是相同的 L+1 节点,会在遍历 L 节点 children 时候加入
// 所以保证了每个相同层级的节点都在一起,且按照上到下的顺序遍历,这样达到广度优先效果
function breadthTraversal(tree) {
  const arr = [];
  const queue = [tree];
  while(queue.length) {
    const node = queue.shift();
    arr.push(node.value);
    if (node.children && node.children.length) {
      node.children.forEach((child) => {
        queue.push(child);
      });
    }
  }
  return arr;
}

console.log('深度优先-递归: ', deepthTraversal1(tree));

console.log('深度优先-迭代: ', deepthTraversal2(tree));

console.log('广度优先: ', breadthTraversal(tree));