目录什么是树树的术语javascript中的树广度优先和深度优点遍历算法深度优先广度优先什么是树 在现实生活中,相信每个人对树都很熟悉,不管是柳树、杨树还是桃树,可以说树在我们生活中
在现实生活中,相信每个人对树都很熟悉,不管是柳树、杨树还是桃树,可以说树在我们生活中随处可见;在计算机世界,树是一种分层结构的抽象模型,
如下图所示:
树结构的应用有很多,就比如公司的组织架构,就可以用树来表示,如下图:
除了组织架构,像族谱、省市等都可以使用树结构来表示。
树有很多的术语,如下图:
n=0
时,称为空树;A D H
;树结构可以说是前端中最常见的数据结构之一,比如说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就是前面定义的那个树
可以看到,和图中的顺序是一致的,也就是说我们的算法没有问题。
所谓的广度优先就是依次访问离根节点近的节点,它的遍历顺序如下图:
实现思路如下:
children
依次入队;实现代码如下:
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)
可以看到,和图中的顺序是一致的,也就是说我们的算法没有问题。
到此这篇关于JavaScript树结构深度优先算法的文章就介绍到这了,更多相关js 树结构内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: JavaScript树结构深度优先算法
本文链接: https://www.lsjlt.com/news/164159.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-01-12
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
2023-05-20
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0