• 技术文章 >web前端 >js教程

    一文掌握JavaScript树结构深度优先算法

    长期闲置长期闲置2022-07-25 17:45:08转载196
    本篇文章给大家带来了关于javascript的相关知识,主要介绍了JavaScript树结构深度优先算法,树结构可以说是前端中最常见的数据结构之一,比如说DOM树、级联选择、树形组件,下面一起来看一下,希望对大家有帮助。

    【相关推荐:javascript视频教程web前端

    什么是树

    在现实生活中,相信每个人对树都很熟悉,不管是柳树、杨树还是桃树,可以说树在我们生活中随处可见;在计算机世界,树是一种分层结构的抽象模型

    如下图所示:

    树结构的应用有很多,就比如公司的组织架构,就可以用树来表示,如下图:

    除了组织架构,像族谱、省市等都可以使用树结构来表示。

    树的术语

    树有很多的术语,如下图:

    JavaScript中的树

    树结构可以说是前端中最常见的数据结构之一,比如说DOM树、级联选择、树形组件等等;

    JavaScript中并没有提供树这个数据结构,但是我们可以通过对象和数组来模拟一个树,

    例如下面这段代码:

    const tree = {
      value: 'A',
      children: [
        {
          value: 'B',
          children: [
            { value: 'E', children: null },
            { value: 'F', children: null },
          ],
        },
        {
          value: 'C',
          children: [{ value: 'G', children: null }],
        },
        {
          value: 'D',
          children: [
            { value: 'H', children: null },
            { value: 'I', children: null },
          ],
        },
      ],
    }

    广度优先和深度优点遍历算法

    深度优先

    所谓的深度优先遍历算法,就是尽可能深的去搜索树的分支,它的遍历顺序如下图:

    实现思路如下:

    实现代码如下:

    function dfs(root) {
      console.log(root.value)
      root.children && root.children.forEach(dfs) // 与下面一致
      // if (root.children) {
      //   root.children.forEach(child => {
      //     dfs(child)
      //   })
      // }
    }
    dfs(tree) // 这个tree就是前面定义的那个树
    /* 结果
    A
    B
    E
    F
    C
    G
    D
    H
    I
    */

    可以看到,和图中的顺序是一致的,也就是说我们的算法没有问题。

    广度优先

    所谓的广度优先就是依次访问离根节点近的节点,它的遍历顺序如下图:

    实现思路如下:

    实现代码如下:

    function bfs(root) {
      // 1. 新建队列 跟节点入队
      const q = [root]
      // 4 重复执行
      while (q.length > 0) {
        const node = q.shift() // 2 队头出队
        console.log(node.value)
        // 3 队头 children 依次入队
        node.children &&
          node.children.forEach(child => {
            q.push(child)
          })
      }
    }
    bfs(tree)
    /* 结果
    A
    B
    C
    D
    E
    F
    G
    H
    I
    */

    可以看到,和图中的顺序是一致的,也就是说我们的算法没有问题。

    【相关推荐:javascript视频教程web前端

    以上就是一文掌握JavaScript树结构深度优先算法的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:脚本之家,如有侵犯,请联系admin@php.cn删除
    专题推荐:javascript
    上一篇:Angular如何进行视图封装?聊聊三种封装模式 下一篇:聊聊Node.js中的多进程和多线程
    VIP课程(WEB全栈开发)

    相关文章推荐

    • 【活动】充值PHP中文网VIP即送云服务器• 总结分享JavaScript中异步与回调的基本概念• 简单了解JavaScript事件的冒泡、委派、绑定和传播• 火了!新的JavaScript运行时:Bun,性能完爆Node• JavaScript怎么处理树状结构数据的增删改查• 简单介绍JavaScript “原型“与“原型链“
    1/1

    PHP中文网