广度优先遍历、深度优先遍历js实现

介绍

• 深度优先遍历：自上而下的遍历
• 广度优先遍历：逐层遍历

例如一个二叉树，每次遍历优先找叶子节点就是深度优先，每次先找同一层次的节点就是广度优先

一、深度优先

  var tree = [
    {
      name: "中国",
      children: [
        {
          name: "北京",
          children: [
            {
              name: "海淀区",
            },
            {
              name: "昌平区",
            },
          ],
        },
        {
          name: "浙江省",
          children: [
            {
              name: "杭州市",
            },
            {
              name: "嘉兴市",
            }
          ],
        },
      ],
    }
  ];
 function shendu(data){
    const result = []
    data.forEach(item=>{
      var map = (data)=>{
        result.push(data.name)
        data.children && data.children.forEach(item=>map(item))
      }
      map(item)
    })
    return result
  }
  let res = shendu(tree)
  console.log(res)  //  ['中国', '北京', '海淀区', '昌平区', '浙江省', '杭州市', '嘉兴市']

二、广度优先

  function guangdu(data){
    var result = []
    var arr = data
    while(arr.length >0){
      [...arr].forEach((item)=>{
        result.push(item.name)
        item.children && arr.push(...item.children)
        arr.shift()
      })
    }
    return result
  }
  let res = guangdu(tree)
  console.log(res)   // ['中国', '北京', '浙江省', '海淀区', '昌平区', '杭州市', '嘉兴市']