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

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

const flatArr = [
  { 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)選擇器中，他接收的是如下的樹形結(jié)構(gòu)：

let options = [
  {
    value: 'zhinan',
    label: '指南',
    children: [
      {
        value: 'shejiyuanze',
        label: '設(shè)計(jì)原則',
        children: [
          { value: 'yizhi', label: '一致' },
          { value: 'fankui', label: '反饋'}
        ],
      }
    ]
  }
]

好家伙，這不就是需要我將平鋪數(shù)組轉(zhuǎn)成樹形結(jié)構(gòu)嘛！
一頓操作猛如虎，二話不說(shuō)寫遞歸。

遞歸方式

大功告成，代碼簡(jiǎn)潔，思路清晰，一運(yùn)行，what？頁(yè)面卡死了，console.time() 計(jì)算，大概使用了18s才計(jì)算出我們需要的樹形結(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è)面卡頓，此法肯定是不可取的，那么，有沒有更好的方案呢？

非遞歸方式

這里巧妙的應(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)，通過 Map 保存每個(gè)節(jié)點(diǎn)及其子節(jié)點(diǎn)的信息，子節(jié)點(diǎn)保存的是 Map 上的引用，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)都可以在 Map 中通過 id 找到，時(shí)間復(fù)雜度為 O(n)

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

通過上面時(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ì)快很多！

最后，不得不感慨一下，通過這個(gè)對(duì)比，我們也可以明顯的感受到算法的重要性，不同的實(shí)現(xiàn)方式，差異可以很大，這值得引起每一個(gè) developer 對(duì)算法的重視！

到此這篇關(guān)于JavaScript平鋪數(shù)組轉(zhuǎn)樹形結(jié)構(gòu)的實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)JavaScript平鋪數(shù)組轉(zhuǎn)樹形結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！