深度遍历 & 广度遍历

遍历

• 深度遍历
• 广度遍历

测试数据

const data = [
  {
      name: 'a',
      children: [
          { name: 'b', children: [{ name: 'e' }] },
          { name: 'c', children: [{ name: 'f' }] },
          { name: 'd', children: [{ name: 'g' }] },
      ],
  },
  {
      name: 'a2',
      children: [
          { name: 'b2', children: [{ name: 'e2' }] },
          { name: 'c2', children: [{ name: 'f2' }] },
          { name: 'd2', children: [{ name: 'g2' }] },
      ],
  }
]

深度遍历 DFS

优先往左下走，深度为先
思路：

• 找到最终的处理逻辑（收集值）
• 找到同样的数据结构，children 和父级都是一样的
• 方式就是递归处理（递归就干一件事，收集值）

const dfs = (arr) => {
  const r = [];
  arr.forEach(obj => {
    const _walk = (obj) => {
      r.push(obj.name);
      obj.children?.forEach(child => _walk(child))
    }
    _walk(obj)
  })
  return r;
}
// test
console.log(dfs(data).join(','))  // a,b,e,c,f,d,g,a2,b2,e2,c2,f2,d2,g2

广度遍历 BFS

同级优先，一层一层来
思路： 层级遍历的话，有一个遍历队列，遍历到子级的时候，将其子级放在队列里面排队，保证下次遍历的就是它

• 找到要处理逻辑（收集值）
• 找到相同的数据结构（children 和父级都是做一样的事情）
• 使用队列来遍历（将一层数据塞进去，遍历完 shift 掉，然后遇到子级，重新更新队列，因此遍历的队列可以是拷贝）

const bfs = (arr) => {
  const r = [];
  const queue = [...arr];
  while(queue.length) {
    [...queue].forEach(i => {
      queue.shift();
      r.push(i.name);
      i.children && i.children.forEach(child => queue.push(child))
    })
  }
  return r;
}
// test
console.log(bfs(data).join(','))  // a,a2,b,c,d,b2,c2,d2,e,f,g,e2,f2,g2