什么是树?

菜园前端
• 阅读 329

原文链接:https://note.noxussj.top/?source=helloworld


什么是树?

在生活中,大家对树肯定不陌生,小朋友都知道树不就是一类植物嘛,不管在任何地方都有各种各样的树。但是在计算机科学里面树是什么呢?一种分层数据的抽象模型,在我们前端工作中无处不在。在 JavaScript 中没有树这种数据结构,但是可以通过 Object 和 Array 这两个数据结构构建树。

深度与广度优先遍历

深度优先遍历

尽可能深的搜索树的分支,主要通过递归实现。

口诀:

  1. 访问根阶段
  2. 对根节点的 children 每个元素进行深度优先遍历

什么是树?

function dfs(root) {
    console.log(root.value)

    root.children.forEach(dfs)
}

广度优先遍历

先访问离根节点最近的节点,主要通过队列实现。

口诀:

  1. 新建一个队列,把根节点入队
  2. 把队头出队并访问
  3. 把队头的 children 元素分别入队
  4. 重复 2 和 3 步骤,直到队列为空

什么是树?

function bfs(root) {
    const q = [root]

    while (q.length) {
        const n = q.shift()

        console.log(n)

        n.children.forEach((child) => {
            q.push(child)
        })
    }
}

常用操作

  • 深度优先遍历
  • 广度优先遍历

应用场景

  1. DOM 树
  2. 级联选择
  3. 树形控件
  4. 组织架构图
点赞
收藏
评论区
推荐文章
Souleigh ✨ Souleigh ✨
3年前
Vue - diff 算法
diff是什么?diff就是比较两棵树,render会生成两颗树,一棵新树newVnode,一棵旧树oldVnode,然后两棵树进行对比更新找差异就是diff,全称difference,在vue里面diff算法是通过patch函数来完成的,所以有的时候也叫patch算法⏳diff发生的时机diff发生在什么时候呢?当然我们可以说在数据更新的时候发生d
徐小夕 徐小夕
3年前
JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:)(https://imghelloworld.osscnbe
Stella981 Stella981
3年前
React的虚拟DOM
上一篇文章中,DOM树的信息可以用JavaScript对象来表示,反过来,可以根据这个用JavaScript对象表示的树结构来真正构建一颗DOM树。用JavaScript对象表示DOM信息和结构,当状态变更的时候,重新渲染这个JavaScript的对象结构,当然这样做,其实并没有更新到真正的页面上。但是可以用新渲染的对象树和旧的树进行对比,记录这两棵树
Wesley13 Wesley13
3年前
Unity 行为树
引言在代码里面动态的操作单颗行为树以及管理所有的行为树,也是一个很重要的事情。一、操作单颗树这是我们项目里面,一个敌人绑定了行为树,自动创建的behaviortree脚本。!(https://oscimg.oschina.net/oscnet/7da4eb8863129cc1a0a9461b2b
Wesley13 Wesley13
3年前
MySQL面试(二)
1、为什么索引遵循最左匹配原则?  当B树的数据项是符合的数据结构,比如(name,age,sex)的时候,B树是按照从左到右的顺序建立搜索树的。比如当(张三,20,F)这样的数据来检索的时候,b树会优先比较name来确定下一步的所搜方向,如果name相同再依次比较age和sex,最后得到检索的数据;但当(20,F)这样的没有name的数据来的时候
Wesley13 Wesley13
3年前
Java数据结构和算法(十五)——无权无向图
前面我们介绍了树这种数据结构,树是由n(n0)个有限节点通过连接它们的边组成一个具有层次关系的集合,把它叫做“树”是因为它看起来像一棵倒挂的树,包括二叉树、红黑树、234树、堆等各种不同的树,有对这几种树不了解的可以参考我前面几篇博客。而本篇博客我们将介绍另外一种数据结构——图,图也是计算机程序设计中最常用的数据结构之一,从数学意义上讲
Wesley13 Wesley13
3年前
2020面试题(答案中)
平衡二叉搜索树必须是“平衡”的情况下,其大部分操作的复杂度才能达到O(logn)。你可以按任意顺序位置插入/删除数据,或者使用AVL树或者红黑树,但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可,所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(logn)的性能。搜索在二叉树中搜索会很快,但是在堆中搜索会
Wesley13 Wesley13
3年前
B
BTreeBTree又叫做B树,和平衡二叉树不同的地方在于B树是多叉树(平衡多路查找树),Oracle和MongoDB的索引技术就是基于B树的数据结构,B树也可以看作是对23查找树的一种扩展。一个m阶的BTree有以下性质1.每个节点最多有m个子节点;2.每个非叶子节点(根节点除外)至少含有m/2个子节点;3.
Stella981 Stella981
3年前
MongoDB索引存储BTree与LSM树(转载)
1、为什么MongoDB使用B树,而不是B树MongoDB是一种nosql,也存储在磁盘上,被设计用在数据模型简单,性能要求高的场合。性能要求高,我们看B树与B树的区别:_B树内节点不存储数据,所有data存储在叶节点导致查询时间复杂度固定为logn。
菜园前端 菜园前端
1年前
什么是二叉树?
原文链接:什么是二叉树?树中每个节点最多只能有两个子节点,在JavaScript中一般都是通过Object来模拟二叉树。常用操作前序遍历中序遍历后序遍历前序遍历根左右。口诀:1.访问根节点2.对根节点的左子树进行前序遍历3.对根节点的右子树进行前序遍历通过