深度遞歸和廣度遞歸

stormgens 發(fā)布于2019-08-22 11:12 / 2867人閱讀

摘要：遞歸遞歸算法在日常工作中算是用的比較多的一種，比如樹的遍歷，多層級(jí)樹狀結(jié)構(gòu)的生成，遍歷尋找某個(gè)樹節(jié)點(diǎn)等先來看下數(shù)據(jù)結(jié)構(gòu)張飛關(guān)羽劉備荀彧關(guān)平曹操貂蟬一般情況下后臺(tái)返回類似于如上的嵌套數(shù)據(jù)結(jié)構(gòu)，或者說只得到一部分?jǐn)?shù)據(jù)，點(diǎn)擊某個(gè)子節(jié)點(diǎn)，異步加載節(jié)

遞歸

遞歸算法在日常工作中算是用的比較多的一種，比如DOM樹的遍歷，多層級(jí)樹狀結(jié)構(gòu)的生成，遍歷尋找某個(gè)樹節(jié)點(diǎn)等

1 先來看下數(shù)據(jù)結(jié)構(gòu)

var result = {
      id:0,
    name:"張飛",
      item:[
        {id:1,name:"關(guān)羽"},
        {id:2,name:"劉備",item:[
          {id:5,name:"荀彧"},
          {id:6,name:"關(guān)平"}

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

一般情況下后臺(tái)返回類似于如上的嵌套數(shù)據(jù)結(jié)構(gòu)，或者說只得到一部分?jǐn)?shù)據(jù)，點(diǎn)擊某個(gè)子節(jié)點(diǎn)，異步加載節(jié)點(diǎn)，異步加載之后的數(shù)據(jù)可能如下：

  var result = {
  id:0,
  name:"張飛",
  item:[
    {id:1,name:"關(guān)羽"},
    {id:2,name:"劉備",item:[
      {id:5,name:"荀彧"},
      {id:6,name:"關(guān)平"}

    ]},
    //點(diǎn)擊曹操這一項(xiàng)，加載出來劉禪和周倉，點(diǎn)擊周倉，又異步加載項(xiàng)羽和別姬
    {id:3,name:"曹操",item:[
      {id:8,name:"劉禪"},
      {id:9,name:"周倉",item:[
        {id:10,name:"項(xiàng)羽"},
        {id:11,name:"別姬"}
      ]}
    ]},
    {id:4,name:"貂蟬"},
  ]
}

//點(diǎn)擊曹操，返回如下數(shù)組
[
  {id:8,name:"劉禪"},
  {id:9,name:"周倉"}
]
//點(diǎn)擊周倉，返回如下數(shù)組
[
  {id:8,name:"項(xiàng)羽"},
  {id:9,name:"別姬"}
]

2 如何實(shí)現(xiàn)項(xiàng)目中的需求

以目前我做的一個(gè)react項(xiàng)目為例：需求是

將類似于這樣的數(shù)據(jù)以樹狀結(jié)構(gòu)展示出來

異步加載子節(jié)點(diǎn)的數(shù)據(jù)，有可能是加載子節(jié)點(diǎn)，有可能是加載同級(jí)節(jié)點(diǎn)

所以就需要定位到每次點(diǎn)擊的節(jié)點(diǎn)的位置，然后根據(jù)其他屬性判斷如何添加節(jié)點(diǎn)

關(guān)鍵就是如何通過遞歸找到對(duì)應(yīng)id的節(jié)點(diǎn)位置

我的實(shí)現(xiàn)思路就是維持一個(gè)state狀態(tài)對(duì)象，每次異步請(qǐng)求回來的數(shù)據(jù)，根據(jù)返回的id來判斷點(diǎn)擊的位置（數(shù)據(jù)中所有節(jié)點(diǎn)id唯一），進(jìn)而將數(shù)據(jù)添加到state中對(duì)應(yīng)的id位置中

3 代碼實(shí)現(xiàn)遞歸

深度優(yōu)先

var item = [result]
//設(shè)置一個(gè)全局的value，存放找到對(duì)應(yīng)item的時(shí)候的引用地址
var value = null ;
//函數(shù)要有返回值，否則默認(rèn)返回undefiend
function getName(item,id){
  if(!item) return null ;
  for (var i = 0 ;i
如果想要更加的通用一些，可以稍加優(yōu)化一下
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
以上代碼實(shí)現(xiàn)遞歸的核心思路是依靠聲明一個(gè)外部的變量，遞歸函數(shù)內(nèi)部進(jìn)行查找，如果找到對(duì)應(yīng)的item，則將此item賦值給value,遞歸函數(shù)返回改value值；
總感覺代碼還不夠簡(jiǎn)潔，大家有好的思路歡迎隨時(shí)交流。
上面這種方法，傳入的item是數(shù)組，當(dāng)時(shí)考慮的是傳入數(shù)組可能會(huì)方便一些；
下面這種方法傳入的rootItem是對(duì)象，感覺下面這種方法會(huì)比較好一些；
這兩者采取的遞歸方式都是深度優(yōu)先的搜索方式，通過我們記錄遞歸的執(zhí)行軌跡可以看出來；
====2017/9/20更新,地鐵上看了一些文章；優(yōu)化一下代碼；
function transerDF(rootItem,id){
  var value = null ;
  (function recurse(currentItem){
    if(currentItem == null) return null ;
    console.log(currentItem.id);//記錄遞歸的執(zhí)行軌跡
    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);

廣度優(yōu)先
function transerBF(rootItem,id){
  var value ;
  var queue = [];//用數(shù)組模擬隊(duì)列
  queue.push(rootItem);//放入隊(duì)列末尾
  var currentItem = queue.shift();//取出隊(duì)列中的首位
  while(currentItem){
    console.log(currentItem.id);//記錄遞歸軌跡
    if(currentItem.item){
      for(var i=0;i
以上分析通過記錄遞歸軌跡，我們可以很清晰的看到遞歸執(zhí)行的順序以及深度遞歸和廣度遞歸不同的實(shí)現(xiàn)思想；
jimwmg@foxmail.com