本篇文章给大家带来了关于javascript的相关知识，主要介绍了javascript树结构深度优先算法，树结构可以说是前端中最常见的数据结构之一，比如说dom树、级联选择、树形组件，下面一起来看一下，希望对大家有帮助。
【相关推荐：javascript视频教程、web前端】
什么是树
在现实生活中，相信每个人对树都很熟悉，不管是柳树、杨树还是桃树，可以说树在我们生活中随处可见；在计算机世界，树是一种分层结构的抽象模型，
如下图所示：
立即学习“Java免费学习笔记（深入）”；
树结构的应用有很多，就比如公司的组织架构，就可以用树来表示，如下图：
除了组织架构，像族谱、省市等都可以使用树结构来表示。
树的术语
树有很多的术语，如下图：
树：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中并没有提供树这个数据结构，但是我们可以通过对象和数组来模拟一个树，
例如下面这段代码：
Medeo
AI视频生成工具
191 查看详情
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就是前面定义的那个树/* 结果ABEFCGDHI*/
可以看到，和图中的顺序是一致的，也就是说我们的算法没有问题。
广度优先
所谓的广度优先就是依次访问离根节点近的节点，它的遍历顺序如下图：
实现思路如下：
创建要给队列，把根节点入队；把队头出队并访问；把队头的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)/* 结果ABCDEFGHI*/
可以看到，和图中的顺序是一致的，也就是说我们的算法没有问题。
【相关推荐：javascript视频教程、web前端】
以上就是一文掌握JavaScript树结构深度优先算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/836457.html
微信扫一扫 
支付宝扫一扫 
