树的深度优先遍历算法,js复杂树形结构的遍历算法
本文给大家带来了一些关于javascript的知识，主要介绍了JavaScript树结构的深度优先算法。树形结构可以说是前端最常见的数据结构之一，比如DOM树、级联选择、树形组件等。下面就一起来看看吧，希望对你有所帮助。
【相关推荐：javascript视频教程，web前端】
什么是树
在现实生活中，相信大家对树都很熟悉，不管是柳树、杨树还是桃树。可以说，在我们的生活中，树随处可见；在计算机世界里，树是一种分层结构的抽象模型，
如下图所示：
树结构的应用有很多，就比如公司的组织架构，就可以用树来表示，如下图：
除了组织结构，如家谱，省市可以用树形结构表示。
树的术语
树有很多的术语，如下图：
树:n(n0)个节点的有限集，当n=0时，称为空树；节点的节点的度:子树个数，比如节点B的度是2，节点A的度是3；树的度:树的所有节点的最大度。比如上图中，树的度是3；叶子节点:度为0的节点，也叫叶节点;子节点:如上图；兄弟节点:如上图；根节点:如上图；树的深度:所有结点中的最大层次在树中，比如上图中树的深度为3；节点的层次:比如E节点的级别是3，节点的级别是父节点层次+1，根节点的层次为1；路径:一个节点到另一个节点的通道。比如AH的路径是A D H；路径长度:一个节点到另一个节点的距离比如AH的路径是3。
JavaScript中的树
树形结构可以说是前端最常见的数据结构之一，如DOM树、级联选择、树形组件等。
JavaScript没有提供树形数据结构，但是我们可以通过对象和数组来模拟一棵树。
例如下面这段代码：
常数树={
值： A ，
儿童：[
{
值：“B”，
儿童：[
{值： E ，子级：null }，
{值： F ，子级：null }，
],
},
{
值： C ，
children: [{ value: G ，children: null }]，
},
{
值：“D”，
儿童：[
{值： H ，子级：null }，
{值： I ，子级：null }，
],
},
],
}
广度优先和深度优点遍历算法
深度优先
所谓的深度优先遍历算法，就是尽可能深的去搜索树的分支，它的遍历顺序如下图：
实现思路如下：
访问根节点；对根节点的子节点继续深度优先遍历(递归);实现代码如下：
函数dfs(根){
console.log(root.value)
root . children root . children . foreach(DFS)//与以下内容一致
//if (root.children) {
//root . children . foreach(child={
//dfs(子级)
//})
//}
}
Dfs(tree) //这个树就是前面定义的树。
/*结果
A
B
E
F
C
G
D
H
我
*/如你所见，与图中顺序一致，说明我们的算法没有问题。
广度优先
所谓的广度优先就是依次访问离根节点近的节点，它的遍历顺序如下图：
实现思路如下：
要创建队列，请将根节点入队。让组长出队，参观；把排在队伍最前面的孩子依次放进队伍里；重复步骤2和3，直到队列为空。实现代码如下：
函数bfs(根){
//1.创建一个新队列，并使用该节点加入团队。
const q=[root]
//4重复执行
while (q.length 0) {
Const node=q.shift() //2组长离队
console.log(节点.值)
//3个组长孩子依次入队。
节点.子节点
node.children.forEach(child={
q.push(儿童)
})
}
}
树
/*结果
A
B
C
D
E
F
G
H
我
*/如你所见，与图中顺序一致，说明我们的算法没有问题。
【相关推荐：javascript视频教程，web前端】以上是一篇关于掌握JavaScript树结构深度优先算法的文章的详细内容。更多请关注我们的其他相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。