JavaScript树结构深度优先算法

目录
  • 什么是树
    • 树的术语
  • JavaScript中的树
  • 广度优先和深度优点遍历算法
    • 深度优先
    • 广度优先

什么是树

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

如下图所示：

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

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

树的术语

树有很多的术语，如下图：

  • 树：n(n≥0)个节点所构成的有限集合，当n=0时，称为空树；
  • 节点的度：节点的子树个数，例如B节点的度就是2，A节点的度就是3；
  • 树的度：树的所有节点中最大的度数，例如上图中，树的度是3；
  • 叶子节点：度为0的节点，也叫叶节点；
  • 子节点：如上图；
  • 兄弟节点：如上图；
  • 根节点：如上图；
  • 树的深度：树中所有结点中的最大层次，例如上图中树的深度就是3；
  • 节点的层次：例如E节点的层次就是3，节点的层次就是父节点层次+1，根节点的层次为1；
  • 路径：一个节点到另一个节点的通道，例如A→H的路径就是A D H；
  • 路径长度：一个节点到另一个节点的距离，例如A→H的路径就是3。

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 },
      ],
    },
  ],
}

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

深度优先

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

实现思路如下：

  • 访问根节点；
  • 对根节点的children持续进行深度优先遍历（递归）；

实现代码如下：

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
*/

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

广度优先

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

实现思路如下：

  • 创建要给队列，把根节点入队；
  • 把队头出队并访问；
  • 把队头的children依次入队；
  • 重复执行2、3步，直到队列为空。

实现代码如下：

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树结构深度优先算法的文章就介绍到这了,更多相关JS 树结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • js实现无限层级树形数据结构(创新算法)

    由于做项目的需要,把一个线性数组转成树形数组,在网上查了很多文章,觉得他们写的太复杂了,于是自己写了一个,在折腾了一下午终于把它写出来啦(激动.gif),用两个filter过滤器就搞定了,代码简洁明了,数据结构小白都能看懂. js代码:把扁平数据转成树形数据 function setTreeData(source){ let cloneData = JSON.parse(JSON.stringify(source)) // 对源数据深度克隆 return cloneData.filter(fat

  • JS中的算法与数据结构之二叉查找树（Binary Sort Tree）实例详解

    本文实例讲述了JS中的算法与数据结构之二叉查找树(Binary Sort Tree).分享给大家供大家参考,具体如下: 二叉查找树(Binary Sort Tree) 我们之前所学到的列表,栈等都是一种线性的数据结构,今天我们将学习计算机中经常用到的一种非线性的数据结构--树(Tree),由于其存储的所有元素之间具有明显的层次特性,因此常被用来存储具有层级关系的数据,比如文件系统中的文件:也会被用来存储有序列表等. 在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的

  • 浅谈JavaScript构造树形结构的一种高效算法

    浅谈JavaScript构造树形结构的一种高效算法

    引言 我们经常会碰到树形数据结构,比如组织层级.省市县或者动植物分类等等数据.下面是一个树形结构的例子: 在实际应用中,比较常见的做法是将这些信息存储为下面的结构,特别是当存在1对多的父/子节点关系时: const data = [ { id: 56, parentId: 62 }, { id: 81, parentId: 80 }, { id: 74, parentId: null }, { id: 76, parentId: 80 }, { id: 63, parentId: 62 }, {

  • JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例

    JavaScript数据结构与算法之二叉树实现查找最小值、最大值、给定值算法示例

    本文实例讲述了JavaScript数据结构与算法之二叉树实现查找最小值.最大值.给定值算法.分享给大家供大家参考,具体如下: function Node(data,left,right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() { this.root = null; this.

  • javascript将扁平的数据转为树形结构的高效率算法

    当我们需要将一个一维数组转换成一个多层结构的时候,最简单但是最慢的就是多个for循环嵌套,但是这样做有一些缺点,那就是效率太低.而且有多少层就需要嵌套几个for循环,不好用. 我实现了用O(n)级算法将 一个扁平的数组即一维数组代表的菜单结构转换成一个多层级的菜单结构. 一位数组中每一个元素必须要包含以下属性: 拥有一个唯一的id 拥有一个parent_id, 这个id指向它父级的id 其他则为每一个元素中的一些信息,我这里是菜单,就有菜单的名称和url信息. 注: 在层级结构中,第一层的par

  • JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

    JavaScript数据结构与算法之二叉树遍历算法详解【先序、中序、后序】

    本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法.分享给大家供大家参考,具体如下: javascript数据结构与算法--二叉树遍历(先序) 先序遍历先访问根节点, 然后以同样方式访问左子树和右子树 代码如下: /* *二叉树中,相对较小的值保存在左节点上,较大的值保存在右节点中 * * * */ /*用来生成一个节点*/ function Node(data, left, right) { this.data = data;//节点存储的数据 this.left = left;

  • JavaScript数据结构与算法之二叉树添加/删除节点操作示例

    JavaScript数据结构与算法之二叉树添加/删除节点操作示例

    本文实例讲述了JavaScript数据结构与算法之二叉树添加/删除节点操作.分享给大家供大家参考,具体如下: function Node(data,left,right) { this.data = data; this.left = left; this.right = right; this.show = show; } function show() { return this.data; } function BST() { this.root = null; this.insert =

  • JavaScript树结构深度优先算法

    JavaScript树结构深度优先算法

    目录 什么是树 树的术语 JavaScript中的树 广度优先和深度优点遍历算法 深度优先 广度优先 什么是树 在现实生活中,相信每个人对树都很熟悉,不管是柳树.杨树还是桃树,可以说树在我们生活中随处可见:在计算机世界,树是一种分层结构的抽象模型, 如下图所示: 树结构的应用有很多,就比如公司的组织架构,就可以用树来表示,如下图: 除了组织架构,像族谱.省市等都可以使用树结构来表示. 树的术语 树有很多的术语,如下图: 树:n(n≥0)个节点所构成的有限集合,当n=0时,称为空树: 节点的度:节

  • javascript时间排序算法实现活动秒杀倒计时效果

    制做一个活动页面 秒杀列表页 需要一个时间的算法排序 自己琢磨了半天想了各种算法也没搞出来,后来问了下一个后台的php同学 他写了个算法给我看了下 ,刚开始看的时候觉得这就是个纯算法,不能转化成页面的dom效果,可是再看了两遍发现可以, 于是我就改了改,实现了,先分享给大家. 页面需求是:从11点到20点 每隔一个小时一场秒杀 如果是当前时间就显示正在秒杀 之前的商品就往最后排 以此类推 类似最开始的11点顺序是 11,12,13,14,15,16,17,18,19,20(点): 到12点的顺序

  • Javascript数据结构与算法之列表详解

    Javascript数据结构与算法之列表详解

    前言:在日常生活中,人们经常要使用列表,比如我们有时候要去购物时,为了购物时东西要买全,我们可以在去之前,列下要买的东西,这就要用的列表了,或者我们小时候上学那段时间,每次考完试后,学校都会列出这次考试成绩前十名的同学的排名及成绩单,等等这些都是列表的列子.我们计算机内也在使用列表,那么列表适合使用在什么地方呢?不适合使用在什么地方呢? 适合使用在:当列表的元素不是很多的情况下,可以使用列表,因为对列表中的元素查找或者排序时,效率还算非常高,反之:如果列表元素非常多的情况下,就不适合使用列表了.

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript数据结构与算法之队列原理与用法实例详解

    JavaScript数据结构与算法之队列原理与用法实例详解

    本文实例讲述了JavaScript数据结构与算法之队列原理与用法.分享给大家供大家参考,具体如下: 队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素.队列用于存储按顺序排列的数据,先进先出,这点和栈不一样(后入先出).在栈中,最后入栈的元素反而被优先处理.我们现在可以把队列想象对我们去餐馆吃饭的情景,很多人排队吃饭,排在最前面的人先打饭.新来的人只能在后面排队.直到轮到他们为止. 一:对队列的操作 队列有2种主要的操作,向队尾中插入新元素enqueue()方法和删除队列中的队首的元

  • Python深度优先算法生成迷宫

    本文实例为大家分享了Python深度优先算法生成迷宫,供大家参考,具体内容如下 import random #warning: x and y confusing sx = 10 sy = 10 dfs = [[0 for col in range(sx)] for row in range(sy)] maze = [[' ' for col in range(2*sx+1)] for row in range(2*sy+1)] #1:up 2:down 3:left 4:right opera

  • JavaScript数组去重算法实例小结

    本文实例总结了JavaScript数组去重算法.分享给大家供大家参考,具体如下: 测试用例: arr = ["1",3,"1",1,4,5,1,"2",5,1,{"name":"li","age":20},2,4,3,{"name":"li","age":20},""]; 方法一:借助于临时数组与indexO

  • JavaScript选择排序算法原理与实现方法示例

    JavaScript选择排序算法原理与实现方法示例

    本文实例讲述了JavaScript选择排序算法原理与实现方法.分享给大家供大家参考,具体如下: 一.选择排序简介 冒泡排序.插入排序.选择排序合称为简单排序.下面是选择排序的思想: 假设有一个数组a,我们想象成有一个班级名叫a班,现在全班随意排成一排,排头的位置是a[0],排尾的位置是a[a.length-1].但高矮顺序不是有序的,我们想从矮到高排,排头最矮,排尾最高. 选择排序是这样工作的: 第一轮: (1)a[1]位置队员与a[0]位置队员比较,如果比a[0]位置队员矮,就把a[1]的位置

  • 10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径

    10分钟教你用python动画演示深度优先算法搜寻逃出迷宫的路径

    深度优先算法(DFS 算法)是什么? 寻找起始节点与目标节点之间路径的算法,常用于搜索逃出迷宫的路径.主要思想是,从入口开始,依次搜寻周围可能的节点坐标,但不会重复经过同一个节点,且不能通过障碍节点.如果走到某个节点发现无路可走,那么就会回退到上一个节点,重新选择其他路径.直到找到出口,或者退到起点再也无路可走,游戏结束.当然,深度优先算法,只要查找到一条行得通的路径,就会停止搜索:也就是说只要有路可走,深度优先算法就不会回退到上一步. 如果你依然在编程的世界里迷茫,可以加入我们的Python学

  • JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】

    JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】

    本文实例讲述了JavaScript数据结构与算法之基本排序算法定义与效率比较.分享给大家供大家参考,具体如下: javascript数据结构与算法--基本排序算法(冒泡.选择.排序)及效率比较 一.数组测试平台 javascript数据结构与算法--基本排序(封装基本数组的操作),封装常规数组操作的函数,比如:插入新数据,显示数组数据,还有交换数组元素等操作来调用不同的排序算法 function CArray(numElements) { this.dataStore = []; this.po

随机推荐