后臺丟來了1w條數(shù)據(jù)

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

const flatArr = [
  { id: '001', name: '節(jié)點1' },
  { id: '0011', parentId: '001', name: '節(jié)點1-1' },
  { id: '00111', parentId: '0011', name: '節(jié)點1-1-1' },
  { id: '002', name: '節(jié)點2' },
]

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

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

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

遞歸方式

大功告成，代碼簡潔，思路清晰，一運行，what？頁面卡死了，console.time() 計算，大概使用了18s才計算出我們需要的樹形結(jié)構(gòu)。
我反省了下我自己，這可是上萬條數(shù)據(jù)，每次從下往上遞歸尋找父節(jié)點的子節(jié)點時都需要遍歷一次數(shù)組，這當(dāng)然耗時了！而且計算時長已經(jīng)明顯導(dǎo)致了頁面卡頓，此法肯定是不可取的，那么，有沒有更好的方案呢？

非遞歸方式

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

總結(jié)

• 遞歸方式：每次遞歸尋找當(dāng)前節(jié)點的子節(jié)點時都需要重新遍歷一遍數(shù)組，時間復(fù)雜度為 O(nlogn)
• 非遞歸方式：從根節(jié)點往下尋找子節(jié)點，通過 Map 保存每個節(jié)點及其子節(jié)點的信息，子節(jié)點保存的是 Map 上的引用，每個節(jié)點的子節(jié)點都可以在 Map 中通過 id 找到，時間復(fù)雜度為 O(n)

我們來看一個對比圖：

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

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

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

最新評論