深度遞歸和廣度遞歸

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

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

遞歸

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

1 先來看下數(shù)據(jù)結構

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:"貂蟬"},
      ]
}

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

  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:"貂蟬"},
  ]
}

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

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

以目前我做的一個react項目為例：需求是

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

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

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

關鍵就是如何通過遞歸找到對應id的節(jié)點位置

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

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

深度優(yōu)先

var item = [result]
//設置一個全局的value，存放找到對應item的時候的引用地址
var value = null ;
//函數(shù)要有返回值，否則默認返回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
以上代碼實現(xiàn)遞歸的核心思路是依靠聲明一個外部的變量，遞歸函數(shù)內部進行查找，如果找到對應的item，則將此item賦值給value,遞歸函數(shù)返回改value值；
總感覺代碼還不夠簡潔，大家有好的思路歡迎隨時交流。
上面這種方法，傳入的item是數(shù)組，當時考慮的是傳入數(shù)組可能會方便一些；
下面這種方法傳入的rootItem是對象，感覺下面這種方法會比較好一些；
這兩者采取的遞歸方式都是深度優(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ù)組模擬隊列
  queue.push(rootItem);//放入隊列末尾
  var currentItem = queue.shift();//取出隊列中的首位
  while(currentItem){
    console.log(currentItem.id);//記錄遞歸軌跡
    if(currentItem.item){
      for(var i=0;i
以上分析通過記錄遞歸軌跡，我們可以很清晰的看到遞歸執(zhí)行的順序以及深度遞歸和廣度遞歸不同的實現(xiàn)思想；
[email protected]

GPU云服務器云服務器 php 遞歸深度樹形遞歸遞歸編程遞歸打印

文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://systransis.cn/yun/91979.html

實現(xiàn)深度遍歷和廣度遍歷(遞歸與非遞歸版本)

摘要：先畫個樹，然后解釋何為深度，何為廣度第一層子集第二層子集第二層子集第三層，子集第三層第四層圖就不畫太復雜了，最高四層的結構，如果換成的形式的話可以理解成第一層第二層先畫個樹，然后解釋何為深度，何為廣度第一層子集 | ...

Betta 2019-08-26 10:09 評論0 收藏0
遍歷多叉樹（遞歸、非遞歸廣度優(yōu)先、深度優(yōu)先）

簡單的遍歷一個樹形結構數(shù)據(jù)的幾種方法、非遞歸方法效率最好。 (function (window, undefined) { var treeNodes = [ { id: 1, name: 1, children: [ { i...

wing324 2019-08-22 10:57 評論0 收藏0
js 中二叉樹的深度遍歷與廣度遍歷(遞歸實現(xiàn)與非遞歸實現(xiàn))

摘要：樹中結點的最大層次稱為樹的深度或高度。二叉樹有深度遍歷和廣度遍歷，深度遍歷有前序中序和后序三種遍歷方法。二叉樹的前序遍歷可以用來顯示目錄結構等中序遍歷可以實現(xiàn)表達式樹，在編譯器底層很有用后序遍歷可以用來實現(xiàn)計算目錄內的文件及其信息等。樹的簡介棧、隊列、鏈表等數(shù)據(jù)結構，都是順序數(shù)據(jù)結構。而樹是非順序數(shù)據(jù)結構。樹型結構是一類非常重要的非線性結構。直觀地，樹型結構是以分支關系定義的層次結...

Yuanf 2019-08-23 11:38 評論0 收藏0
JS數(shù)據(jù)結構描述之廣度遍歷和深度遍歷

摘要：一數(shù)據(jù)模型二遞歸實現(xiàn)遞歸實現(xiàn)三非遞歸廣度優(yōu)先實現(xiàn)先將第一層節(jié)點放入棧如果該節(jié)點有子節(jié)點，繼續(xù)添加進入棧底非遞歸廣度優(yōu)先實現(xiàn)四非遞歸深度優(yōu)先實現(xiàn)先將第一層節(jié)點放入棧如果該節(jié)點有子節(jié)點，繼續(xù)添加進入棧頂非遞歸深度優(yōu)先實現(xiàn) 文章來源：http://www.html-js.com/articl... 簡單的遍歷一個樹形結構數(shù)據(jù)的幾種方法、非遞歸方法效率最好。一：數(shù)據(jù)模型: (function...

printempw 2019-08-20 15:35 評論0 收藏0
JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)

摘要：算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷背景在開發(fā)頁面的時候，我們有時候會遇到這種需求在頁面某個節(jié)點中遍歷，找到目標節(jié)點，我們正常做法是利用選擇器，或者，但在本文，我們從算法的角度去查找節(jié)點，同時理解一下深度優(yōu)先遍歷和廣度優(yōu)先遍歷的原理。 JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS) 背景在開發(fā)頁面的時候，我們有時候會遇到這種需求：在頁面某個dom節(jié)點中遍歷，找到目標dom節(jié)點，...

roadtogeek 2019-08-23 16:33 評論0 收藏0