JavaScript平鋪數(shù)組轉(zhuǎn)樹(shù)形結(jié)構(gòu)的實(shí)現(xiàn)示例

第JavaScript平鋪數(shù)組轉(zhuǎn)樹(shù)形結(jié)構(gòu)的實(shí)現(xiàn)示例目錄后臺(tái)丟來(lái)了1w條數(shù)據(jù)

遞歸方式非遞歸方式總結(jié)

后臺(tái)丟來(lái)了1w條數(shù)據(jù)

千算萬(wàn)算，還是沒(méi)有逃過(guò)，后臺(tái)真的就上萬(wàn)條數(shù)據(jù)一次丟給前端了。好吧，好在還不是10w條。如下，后臺(tái)返回的是這樣的結(jié)構(gòu)：

constflatArr=[

{id:'001',name:'節(jié)點(diǎn)1'},

{id:'0011',parentId:'001',name:'節(jié)點(diǎn)1-1'},

{id:'00111',parentId:'0011',name:'節(jié)點(diǎn)1-1-1'},

{id:'002',name:'節(jié)點(diǎn)2'},

可以看到，這實(shí)際上就是一個(gè)平鋪的數(shù)組，我們的需求是，要將這樣數(shù)據(jù)渲染在Element-ui的級(jí)聯(lián)選擇器中，他接收的是如下的樹(shù)形結(jié)構(gòu)：

letoptions=[

value:'zhinan',

label:'指南',

children:[

value:'shejiyuanze',

label:'設(shè)計(jì)原則',

children:[

{value:'yizhi',label:'一致'},

{value:'fankui',label:'反饋'}

好家伙，這不就是需要我將平鋪數(shù)組轉(zhuǎn)成樹(shù)形結(jié)構(gòu)嘛！

一頓操作猛如虎，二話不說(shuō)寫(xiě)遞歸。

遞歸方式

大功告成，代碼簡(jiǎn)潔，思路清晰，一運(yùn)行，what？頁(yè)面卡死了，console.time()計(jì)算，大概使用了18s才計(jì)算出我們需要的樹(shù)形結(jié)構(gòu)。

我反省了下我自己，這可是上萬(wàn)條數(shù)據(jù)，每次從下往上遞歸尋找父節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)都需要遍歷一次數(shù)組，這當(dāng)然耗時(shí)了！而且計(jì)算時(shí)長(zhǎng)已經(jīng)明顯導(dǎo)致了頁(yè)面卡頓，此法肯定是不可取的，那么，有沒(méi)有更好的方案呢？

非遞歸方式

這里巧妙的應(yīng)用了對(duì)象保存的是引用的特點(diǎn)，每次將當(dāng)前節(jié)點(diǎn)的id作為key，保存對(duì)應(yīng)節(jié)點(diǎn)的引用信息，遍歷數(shù)組時(shí)，每次更新objMap的children信息，這樣objMap中保留了所有節(jié)點(diǎn)極其子節(jié)點(diǎn)，最重要的是，我們只需要遍歷一遍數(shù)組，時(shí)間復(fù)雜度為O(n)。使用這種方式，計(jì)算時(shí)長(zhǎng)只需要60ms！

總結(jié)

遞歸方式：每次遞歸尋找當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)時(shí)都需要重新遍歷一遍數(shù)組，時(shí)間復(fù)雜度為O(nlogn)

非遞歸方式：從根節(jié)點(diǎn)往下尋找子節(jié)點(diǎn)，通過(guò)Map保存每個(gè)節(jié)點(diǎn)及其子節(jié)點(diǎn)的信息，子節(jié)點(diǎn)保存的是Map上的引用，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)都可以在Map中通過(guò)id找到，時(shí)間復(fù)雜度為O(n)

我們來(lái)看一個(gè)對(duì)比圖：

通過(guò)上面時(shí)間復(fù)雜度隨數(shù)據(jù)量增大的走勢(shì)可以看出，當(dāng)數(shù)據(jù)越來(lái)越大時(shí)，遞歸算法的耗時(shí)將遠(yuǎn)遠(yuǎn)大于非遞歸算法。因此，當(dāng)數(shù)據(jù)量小時(shí)，使用遞歸算法有一定的優(yōu)勢(shì)，但是當(dāng)數(shù)據(jù)大到一定的程度時(shí)，遞歸的做法的劣勢(shì)將越來(lái)越明顯，使用非遞歸算法會(huì)快很多！

最后，不得不感