[JavaScript知识库] js算法的深度优先遍历和广度优先遍历

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> JavaScript知识库 -> js算法的深度优先遍历和广度优先遍历 -> 正文阅读

[JavaScript知识库]js算法的深度优先遍历和广度优先遍历

深度优先遍历实现方式1

//深度优先遍历方法
let tree =  {
    id: '1',
    title: '节点1',
    children: [
      {
        id: '1-1',
        title: '节点1-1'
      },
      {
        id: '1-2',
        title: '节点1-2',
        children: [{
          id: '2',
          title: '节点2',
          children: [
            {
              id: '2-1',
              title: '节点2-1'
            }
          ]
        }]
      }
    ]
  }
  //主要级就是当前节点遍历完，然后再去遍历兄弟节点这样的顺序
let deepTraversal1 = (node, nodeList = []) => {
    if (node !== null) {
      nodeList.push(node.id)
      if(node.children && node.children.length>0){
        let children = node.children
        for (let i = 0; i < children.length; i++) {
          deepTraversal1(children[i], nodeList)
        }
      }
    }
    return nodeList
}
console.log(deepTraversal1(tree))

在这里插入图片描述

深度优先遍历实现方式2

//深度优先遍历方法
let tree =  {
    id: '1',
    title: '节点1',
    children: [
      {
        id: '1-1',
        title: '节点1-1'
      },
      {
        id: '1-2',
        title: '节点1-2',
        children: [{
          id: '2',
          title: '节点2',
          children: [
            {
              id: '2-1',
              title: '节点2-1'
            }
          ]
        }]
      }
    ]
  }
  
  let deepTraversal2 = (node) => {
    let nodes = []
    if (node !== null) {
      nodes.push(node.id)
      if(node.children && node.children.length>0){
        let children = node.children
        for (let i = 0; i < children.length; i++) {
          nodes = nodes.concat(deepTraversal2(children[i]))
        }
      }
    }
    return nodes
  }

console.log(deepTraversal2(tree))

深度优先遍历实现方式3 ,非递归的方式

//深度优先遍历方法

let tree =  {
    id: '1',
    title: '节点1',
    children: [
      {
        id: '1-1',
        title: '节点1-1'
      },
      {
        id: '1-2',
        title: '节点1-2',
        children: [{
          id: '2',
          title: '节点2',
          children: [
            {
              id: '2-1',
              title: '节点2-1'
            }
          ]
        }]
      }
    ]
  }
  
  let widthTraversal3 = (node) => {
    let nodes = []
    let stack = []

    if(node){
      stack.push(node)
      while(stack.length){
        let item = stack.shift()
        let children = item.children
        nodes.push(item.id)
        if(children){
           for(var i=0;i<children.length;i++){
            stack.push(children[i])
           }
        }
      }
    }

    return nodes
  }

console.log(widthTraversal3(tree))

广度优先搜索

let tree = [
    {
      id: '1',
      title: '节点1',
      children: [
        {
          id: '1-1',
          title: '节点1-1'
        },
        {
          id: '1-2',
          title: '节点1-2'
        }
      ]
    },
    {
      id: '2',
      title: '节点2',
      children: [
        {
          id: '2-1',
          title: '节点2-1'
        }
      ]
    }
  ]


function treeForeach(tree,func){
  let node,list = [...tree]
  while(node = list.shift()){
    func(node)
    node.children && list.push(...node.children)
  }
}

treeForeach(tree,node => console.log(node.title))
console.log(tree);