JavaScript树结构深度优先算法

网友投稿 • 2022年10月7日 pm7:13 • 云知识 • 阅读 0

　　什么是树

　　现实中树随处可见；在计算机世界，树就是一种分层结构的抽象模型。

　　如下图所示：

　　树结构的可以用在很多情景，就如下图公司的组织架构，用“树”就可以表达出来，如下图：

　　组织架构只是其中之一，比如族谱、省市等用树的结构形式展现是完全可以。

　　树的术语

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

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

　　上述展示我们想要的表示，算法没什么问题。

原创文章，作者：网友投稿，如若转载，请注明出处：https://www.cloudads.cn/archives/3973.html

JavaScript树结构深度优先算法

相关推荐

发表评论