深度递归和广度递归

stormgens 发布于2019-08-22 11:12 / 2864人阅读

摘要：递归递归算法在日常工作中算是用的比较多的一种，比如树的遍历，多层级树状结构的生成，遍历寻找某个树节点等先来看下数据结构张飞关羽刘备荀彧关平曹操貂蝉一般情况下后台返回类似于如上的嵌套数据结构，或者说只得到一部分数据，点击某个子节点，异步加载节

递归

递归算法在日常工作中算是用的比较多的一种，比如DOM树的遍历，多层级树状结构的生成，遍历寻找某个树节点等

1 先来看下数据结构

var result = {
      id:0,
    name:"张飞",
      item:[
        {id:1,name:"关羽"},
        {id:2,name:"刘备",item:[
          {id:5,name:"荀彧"},
          {id:6,name:"关平"}

        ]},
        {id:3,name:"曹操"},
        {id:4,name:"貂蝉"},
      ]
}

一般情况下后台返回类似于如上的嵌套数据结构，或者说只得到一部分数据，点击某个子节点，异步加载节点，异步加载之后的数据可能如下：

  var result = {
  id:0,
  name:"张飞",
  item:[
    {id:1,name:"关羽"},
    {id:2,name:"刘备",item:[
      {id:5,name:"荀彧"},
      {id:6,name:"关平"}

    ]},
    //点击曹操这一项，加载出来刘禅和周仓，点击周仓，又异步加载项羽和别姬
    {id:3,name:"曹操",item:[
      {id:8,name:"刘禅"},
      {id:9,name:"周仓",item:[
        {id:10,name:"项羽"},
        {id:11,name:"别姬"}
      ]}
    ]},
    {id:4,name:"貂蝉"},
  ]
}

//点击曹操，返回如下数组
[
  {id:8,name:"刘禅"},
  {id:9,name:"周仓"}
]
//点击周仓，返回如下数组
[
  {id:8,name:"项羽"},
  {id:9,name:"别姬"}
]

2 如何实现项目中的需求

以目前我做的一个react项目为例：需求是

将类似于这样的数据以树状结构展示出来

异步加载子节点的数据，有可能是加载子节点，有可能是加载同级节点

所以就需要定位到每次点击的节点的位置，然后根据其他属性判断如何添加节点

关键就是如何通过递归找到对应id的节点位置

我的实现思路就是维持一个state状态对象，每次异步请求回来的数据，根据返回的id来判断点击的位置（数据中所有节点id唯一），进而将数据添加到state中对应的id位置中

3 代码实现递归

深度优先

var item = [result]
//设置一个全局的value，存放找到对应item的时候的引用地址
var value = null ;
//函数要有返回值，否则默认返回undefiend
function getName(item,id){
  if(!item) return null ;
  for (var i = 0 ;i
如果想要更加的通用一些，可以稍加优化一下
var item = [result]
function getName(item,id){
  let value = null ;
  let ret = recurision(item,id);
  return ret ;
  function recurision(item,id){
    if(!item) return null ;
    for (var i = 0 ;i
以上代码实现递归的核心思路是依靠声明一个外部的变量，递归函数内部进行查找，如果找到对应的item，则将此item赋值给value,递归函数返回改value值；
总感觉代码还不够简洁，大家有好的思路欢迎随时交流。
上面这种方法，传入的item是数组，当时考虑的是传入数组可能会方便一些；
下面这种方法传入的rootItem是对象，感觉下面这种方法会比较好一些；
这两者采取的递归方式都是深度优先的搜索方式，通过我们记录递归的执行轨迹可以看出来；
====2017/9/20更新,地铁上看了一些文章；优化一下代码；
function transerDF(rootItem,id){
  var value = null ;
  (function recurse(currentItem){
    if(currentItem == null) return null ;
    console.log(currentItem.id);//记录递归的执行轨迹
    if(currentItem.item){
      for(var i = 0 ; i < currentItem.item.length ; i++){
        recurse(currentItem.item[i])
      }
    }
    if(currentItem.id == id){
      value = currentItem;
    }
  })(rootItem)
  return value ;
}
var ret = transerDF(result,1);
console.log(ret);

广度优先
function transerBF(rootItem,id){
  var value ;
  var queue = [];//用数组模拟队列
  queue.push(rootItem);//放入队列末尾
  var currentItem = queue.shift();//取出队列中的首位
  while(currentItem){
    console.log(currentItem.id);//记录递归轨迹
    if(currentItem.item){
      for(var i=0;i
以上分析通过记录递归轨迹，我们可以很清晰的看到递归执行的顺序以及深度递归和广度递归不同的实现思想；
jimwmg@foxmail.com

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

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

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

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

Betta 2019-08-26 10:09 评论0 收藏0
遍历多叉树（递归、非递归广度优先、深度优先）

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

wing324 2019-08-22 10:57 评论0 收藏0
js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

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

Yuanf 2019-08-23 11:38 评论0 收藏0
JS数据结构描述之广度遍历和深度遍历

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

printempw 2019-08-20 15:35 评论0 收藏0
JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

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

roadtogeek 2019-08-23 16:33 评论0 收藏0