深度与广度优先遍历

//数据格式
const tree = {
  val:'a',
  children:[
    {
      val:'b',
      children:[{
        val:'d',
        children:[]
      },{
        val:'e',
        children:[]
      }]
    },
    {
      val:'c',
      children:[{
        val:'f',
        children:[]
      },{
        val:'g',
        children:[]
      }]
    },
  ]
};

深度遍历顺序是a、b、d、e、c、f、g

//dfs(深度遍历)
// 深度优先遍历算法口诀
// 1、访问根节点
// 2、对根节点的children挨个进行深度优先遍历
const dfs = (root)=>{
  //深度优先遍历只有两行，1、先获取这个节点，2、对这个节点的children遍历
  console.log(root.val)
  root.children.forEach(dfs)
}
dfs(tree)//a、b、d、e、c、f、g

广度遍历顺序是a、b、c、d、e、f、g

//bfs(广度遍历)
//广度优先遍历算法口诀
//1、新建一个队列，把根节点入队
//2、把对头出队并访问
//3、把队头的children挨个入队
//4、重复弟二三步，直到队列为空
const bfs = (root)=>{
  // 1、先建一个队列，根节点入队
  const q = [root];
  while(q.length>0){
    // 2、shift移除队列第一个，并访问当前队头，
    const n = q.shift();
    console.log(n.val)
    //3、把队头的children挨个入队
    n.children.forEach(child=>{
      q.push(child)
    })
  }
}
bfs(tree)//a、b、c、d、e、f、g