这篇文章主要讲解了“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。
树结构可以说是前端中最常见的数据结构之一,比如说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树结构深度优先算法怎么使用”的内容了,经过本文的学习后,相信大家对JavaScript树结构深度优先算法怎么使用这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。