遞歸查找樹形數據結構

遞歸

遞歸演算法在日常工作中算是用的比較多的一種，比如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來判斷點擊的位置，進而將數據添加到state中對應的id位置中

3 代碼實現遞歸

var item = [result]//設置一個全局的value，存放找到對應item的時候的引用地址var value = null ;//函數要有返回值，否則默認返回undefiendfunction getName(item,id){ if(!item) return null ; for (var i = 0 ;i<item.length;i++){ if(item[i].id == id) { value = item[i] break ; }; if(item[i].item){ getName(item[i].item,id) }; } return value ;}//可以試著改變id看下效果，最好打下斷電，可以更加深刻的了解下程序運行的過程var foundName = getName(item,7);console.log(foundName,foundName)

如果想要更加的通用一些，可以稍加優化一下

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.length;i++){ if(item[i].id == id) { value = item[i] break ; }; if(item[i].item){ recurision(item[i].item,id) }; } return value; }}var foundName = getName(item,9);console.log(foundName,foundName)

以上代碼實現遞歸的核心思路是依靠聲明一個外部的變數，遞歸函數內部進行查找，如果找到對應的item，則將此item賦值給value,遞歸函數返回改value值；

總感覺代碼還不夠簡潔，大家有好的思路歡迎隨時交流。

###4 優化

//廣度優先function transerBF(rootItem,id){ var value ; var queue = [];//用數組模擬隊列 queue.push(rootItem);//放入隊列末尾 var currentItem = queue.shift();//取出隊列中的首位 while(currentItem){ console.log(currentItem.id);//記錄遞歸軌跡 if(currentItem.item && currentItem.item.length > 0){ for(var i=0;i<currentItem.item.length;i++){ queue.push(currentItem.item[i]); } } if(currentItem.id == id ){ value = currentItem; } currentItem = queue.shift(); } return value;}var ret = transerBF(result,11);console.log(ret);//深度優先function transerDF(rootItem,id){ var value = null ; (function recurse(currentItem){ if(currentItem == null) return null ; console.log(currentItem.id);//記錄遞歸的執行軌跡 if(currentItem.item && currentItem.item.length > 0){ 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);

jimwmg@foxmail.com