树的深度遍历(DFS)和广度遍历(BFS)

树的简介

什么是树

树是一种数据结构
复制代码

树的常见分类

二叉树
二叉平衡树
二叉搜索树
红黑树
复制代码

树的特点

树一般都有一个根，连接着根的是树干；
树干会发生分叉，形成许多树枝，树枝会继续分化成更小的树枝；
树枝的最后是叶子；
复制代码

深度优先遍历(DFS)

        let tree = [
          {
            label: 'a',
            children: [
              {
                label: 'b',
                children: [
                  {
                    label: 'd'
                  },
                  {
                    label: 'e'
                  }
                ]
              },
              {
                label: 'c',
                children: [
                  {
                    label: 'f'
                  }
                ]
              }
            ]
          }
        ]
复制代码

    /*
     使用递归
   */
    function deepSearch (tree) {
     for (var i = 0; i < tree.length; i++) {
       console.log(tree[i].label)
       if (tree[i].children) {
         deepSearch(tree[i].children)
       }
     }
   }
       /*
     不使用递归, 使用栈的思想
     要求数据结构直接给的是一个对象
   */
  function deepSearch1(tree) {
   let nodes = [] // 按顺序保存所有的节点
   if (tree) {
     let stack = [] // 定义一个栈
     stack.push(tree) // 原始的树入栈
     while(stack.length != 0) {
       let item = stack.pop() // 出栈
       console.log(item, 'item')
       nodes.push(item)
       children=item&&item.children?item.children:[];
       for(let i = children.length - 1; i >= 0; i--) { // 栈顶的元素先出栈，所以后面的子节点先入栈
         stack.push(children[i]) // 子节点入栈
       }
     }
     console.log(nodes, 'nodes') // abdecf
     console.log(stack,'stack')
   }
  }    
    
复制代码

广度优先遍历(BFS)

    /*
      实现广度优先搜索 (Breath First Search)
      选取，标记， 队列（先进先出）
    */
    let tree = [
      {
        label: 'a',
        children: [
          {
            label: 'b',
            children: [
              {
                label: 'd'
              },
              {
                label: 'e'
              }
            ]
          },
          {
            label: 'c',
            children: [
              {
                label: 'f'
              }
            ]
          }
        ]
      }
    ]
    function breathSearch(tree) {
      let nodes = []
      let quene = tree // 创建一个队列，按顺序保存数据
      for (var i = 0; i < quene.length; i++) {
        console.log(quene[i])
        nodes.push(quene[i])
        quene = quene[i].children ? quene.concat(quene[i].children): quene
      }
      console.log(nodes, 'nodes') // abcdef
    }
    breathSearch(tree)
复制代码

总结

深度优先遍历使用的是递归，栈(先进后出)的思想，广度优先遍历使用队列(先进先出)的思想