资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/实现深度遍历和广度遍历(递归与非递归版本)

实现深度遍历和广度遍历(递归与非递归版本)

Betta / 2964人阅读

摘要：先画个树，然后解释何为深度，何为广度第一层子集第二层子集第二层子集第三层，子集第三层第四层图就不画太复杂了，最高四层的结构，如果换成的形式的话可以理解成第一层第二层

先画个树，然后解释 何为深度， 何为广度

                            第一层  子集
                                    |
                        __________________________
                        |                        |
                第二层1 子集             第二层2 子集       
                        |                        | 
                -----------------
                第三层11，子集       第三层12   
                         |
                    第四层111

图就不画太复杂了，最高四层的结构，如果换成html的形式的话可以理解成

------第一层
    
    ----------第二层1
        
  •  -----------第三层 11
             -----------第四层 111
        
    • 
        
        
  • ---------------第三层 12
        
    • 
    

    
    
 ------------第一层2

深度遍历，就是 从 第一层开始 -》 1 -》 11 -》111 -》 12 -》 2
这个意思就是，如果有下一级优先探索下一级的，没有了话，再去探索兄弟层级（以此类推）
就是做一道菜，需要菜和调料，调料是需要调制的，比如调料需要鸡汁和糖，鸡汁又需要调制，那么 正常流程 就是 ，
1、开始做菜 -》 开始调料 -》 鸡汁 -》调制鸡汁的材料
2、等这些弄完了，再去加糖 ，完成调料步骤
3、糖加完了，再去切菜，完成做菜步骤
这个就是一个深度的过程

而广度遍历则相反， 顺序应该是 -> 1-> 2 -> 11 -> 12 -> 111
意思就是有兄弟层级优先解析兄弟层级，然后解析下一层级

广度比较符合正常人的思维，就像复习的时候，
1.先把整本书捋一遍，然后画重点，
2.捋完之后看重点，重点内容里面有一些具体时间，再整理出来，
3.最后重点背诵时间
广度遍历需要手动去终结（判断还有没有整理内容了）

根据js单线程的原理，深度很好实现，因为循环递归默认就是深度遍历
把刚刚的图 写成一个数组

const arr = [
     {
         name: "1",
         childrens: [
             {
                 name: "11",
                 childrens: [
                     {
                         name: "111"
                     }
                 ]
             },

             {
                 name: "12"
             }
         ]
     },

     {
         name: "2"
     }
]

我多加了一些换行，方便看清楚

深度遍历

function check(nodeArr) {
    nodeArr.forEach(node => {
        console.log(node.name)
        if(node.childrens) {
            check(node.childrens)
        }
    })
}
check(arr) //
1
11
111
12
2

这段代码很好理解，如果有子集，将子集和父集做同样处理，或者说，作为一个新的参数给check这个方法。

广度遍历
广度遍历的话需要一个容器去记录子集，等此层级的兄弟集处理完成，再去处理子集，子集的处理也以此类推
先上代码

function checkN(nodeX) {
    var node_ = []; // 用来存储子集
    nodeX.forEach(node => {
        console.log(node.name);
        if(node.childrens) {
            node_ = [...node_, ...node.childrens];
        }
    })
    if(node_[0])
        checkN(node_);
}
checkN(arr) //
1
2
11
12
111

具体内容就这些了，这两个算法我刚刚自己想着写的，不知道和一些比较正式的文章算法是不是略有出入，我也懒得去看了

应一个大佬朋友，也是我高中同学的要求，写了一个非递归版本

这个是深度优先的.....

 function check_(nodeArr) {
     let processList = nodeArr;
     while(processList[0]) {
         const a = processList.shift();
         if(a.childrens) 
             processList = [...a.childrens, ...processList];
         console.log(a.name);        
     }
 }
 check_(arr);// 
1
11
111
12
2

这个是广度优先的

 function checkX_(nodeArr) {
     let processList = nodeArr;
     while(processList[0]) {
         const a = processList.shift();
         if(a.childrens) {
             processList = [...processList,...a.childrens];
         }
             console.log(a.name);        
     }
 }

checkX_(arr);// 
1
2
11
12
111

这两个代码的相似度几乎是百分之九十，唯一的区别就是先进先出（广度优先），和先进后出（深度优先）

先进先出的话，后来者就排到其后面，先进后出，后来者就排到其前面
那么唯一的区别就是 processList = [...a.childrens, ...processList]; 还是 processList = [...processList,...a.childrens];

云服务器 GPU云服务器 非递归遍历 递归遍历java java递归遍历树 php 递归遍历树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/105696.html

相关文章

  • js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

    摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。 树的简介 栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

    Yuanf 评论0 收藏0

  • JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

    摘要：算法之深度优先遍历和广度优先遍历背景在开发页面的时候，我们有时候会遇到这种需求在页面某个节点中遍历，找到目标节点，我们正常做法是利用选择器，或者，但在本文，我们从算法的角度去查找节点，同时理解一下深度优先遍历和广度优先遍历的原理。 JS算法之深度优先遍历(DFS)和广度优先遍历(BFS) 背景 在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom节点，...

    roadtogeek 评论0 收藏0

  • 二叉树遍历

    摘要：前言本篇文章是在二叉排序树的基础上进行遍历查找与删除结点。接下来我们根据构造的这颗二叉树进行相应遍历查找与删除操作。遍历二叉树二叉树的遍历分为深度优先遍历和广度优先遍历。中序遍历二叉排序树，得到的数组是有序的且是升序的。 前言 本篇文章是在二叉排序树的基础上进行遍历、查找、与删除结点。 那么首先来看一下什么是二叉排序树？ 二叉排序树 定义 二叉排序树，又称二叉查找树、二叉搜索树。 若...

    aboutU 评论0 收藏0

  • JS数据结构描述之广度遍历和深度遍历

    摘要：一数据模型二递归实现递归实现三非递归广度优先实现先将第一层节点放入栈如果该节点有子节点，继续添加进入栈底非递归广度优先实现四非递归深度优先实现先将第一层节点放入栈如果该节点有子节点，继续添加进入栈顶非递归深度优先实现 文章来源：http://www.html-js.com/articl... 简单的遍历一个树形结构数据的几种方法、非递归方法效率最好。 一：数据模型: (function...

    printempw 评论0 收藏0

  • 遍历多叉树（递归、非递归广度优先、深度优先）

    简单的遍历一个树形结构数据的几种方法、非递归方法效率最好。 (function (window, undefined) { var treeNodes = [ { id: 1, name: 1, children: [ { i...

    wing324 评论0 收藏0

发表评论

登陆后可评论

0条评论

Betta

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<