js中树形结构的深度遍历与广度遍历

树形结构的深度遍历与广度遍历

定义

深度遍历：一个树形结构中，由一个数据分支全部遍历完才去遍历另外一个分支，直至全部数据遍历完成。

广度遍历：先遍历最外层的分支数据，然后一层一层的进行深入遍历，直至全部数据遍历完成。

树形数据

  
  const nodeList = [
    {
      id: 1,
      children: [
        {
          id: 3,
          children: [
            {
              id: 6,
              children: [
                { id: 9 }
              ]
            },
            {
              id: 7
            }
          ]
        },
        {
          id: 4,
          children: [
            { id: 8 }
          ]
        },
        {
          id: 5
        }
      ]
    },
    {
      id: 2
    }
  ]
  

详细描述

深度遍历： 如上树形数据结构nodeList，深度遍历的时候首先遍历到id为1的节点，如果有children子节点就继续往下遍历（如id为3数据），直至把id为1分支上的数据全部遍历完成后才去遍历另外分支上的数据（如id为2节点），然后再id为2的分支上也执行之前操作。

广度遍历：如上树形数据结构nodeList，首先遍历最外层数据（首先是id为1，然后是id为2的数据），最外层遍历完成后再去遍历往里一层的数据（如id为3，然后id为4的数据），直至当前层数据遍历完毕，接着去遍历在网下一层数据，直至所有数据遍历完毕。

使用场景

在日常开发中经常会遇到多级菜单或者树形下拉框等，可能需要给数据增加自己的标识和字段，还有要查找某项数据的id传给后端，再或者执行平铺等操作，都会涉及到树形数据的处理。

深度遍历

深度遍历的实现可以使用递归的方式，也可以借用栈的思想特点（先入后出，只能在栈顶进行操作）来实现。因为我们日常开发的树形层级不会嵌套特别多，所以采用哪种方式都可以，但是如果遇到层级特别深的递归会有很大的性能问题，最好采用栈思想来实现。代码实例：

  // 深度遍历
  const each = data => {
    let stack = [...data], node;

    while (node = stack.shift()) {
      console.log(node.id);
      // 如果有子元素的话进行压栈操作
      if (node.children) stack.unshift(...node.children)
    }
  }

  each(nodeList)
  // 打印数据顺序
  // 1
  // 3
  // 6
  // 9
  // 7
  // 4
  // 8
  // 5
  // 2

广度遍历

广度遍历的实现可以借用队列的思想（先进先出）来实现。实例代码如下：

  // 广度遍历
  const each = data => {
    let node, list = [...data];

    while (node = list.shift()) {
      console.log(node.id);
      // 如果有子元素就放入队列
      node.children && list.push(...node.children);
    }
  }
  
  each(nodeList);

  // 打印数据顺序
  // 1
  // 2
  // 3
  // 4
  // 5
  // 6
  // 7
  // 8
  // 9