概念

  • 深度优先遍历：从某个顶点出发，首先访问这个顶点，然后找出刚访问这个节点的第一个未被访问的邻接点，然后再以此邻接点作为顶点，继续寻找下一个顶点进行访问。重复步骤，直到所有的节点都被访问完为止。
  • 广度优先遍历：从某个顶点出发，首先访问这个顶点，然后找到刚访问这个顶点的所有未被访问的邻接点，访问完后再访问这些节点中的第一个邻接点的所有节点，重复步骤，直到所有的节点都被访问完为止。

    深度优先遍历

    ```javascript // 测试的树 const node = { name: ‘A’, children: [{
    1.   name: 'B',
    2.   children: [{
    3.       name: 'C'
    4.     }, {
    5.       name: 'D'
    6.     }]
    7. }, {
    8. name: 'E',
    9. children: [{
    10.     name: 'F'
    11.   }, {
    12.     name: 'G'
    13.   }]
    }, {
    1. name: 'L'
    }, {
    1. name: 'M'
    }] }

// 深度优先遍历的递归写法 const nodeList = [] function deepTraversal(node) { if (node) { nodeList.push(node.name) let children = node.children ? node.children : [] for (let i = 0;i < children.length; i++) { deepTraversal(children[i]) } } return nodeList.join(‘,’) } console.log(deepTraversal(node))

// 深度优先遍历的非递归写法 function deepTraversal(node) { let nodes = [] if (node) { let stack = [] // 同时存放将来要访问的节点 stack.push(node) while(stack.length) { let item = stack.pop() // 正在访问的节点 nodes.push(item.name) let children = item.children ? item.children : [] for (let i = children.length - 1; i>=0; i—) { // 将现在访问的节点的子节点存入 stack，供将来访问 stack.push(children[i]) } } } return nodes.join(‘,’) } console.log(deepTraversal(node)) ```

https://juejin.cn/post/6882627409393221646

https://blog.csdn.net/m0_37686205/article/details/100044144

https://workstudy.top/2020/11/17/JS-%E4%B9%8B%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%E5%92%8C%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86/#%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86

https://cloud.tencent.com/developer/article/1601620