JavaScript平鋪數組轉樹(shù)形結構的實(shí)現示例

目錄

后臺丟來(lái)了1w條數據

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

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

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

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

好家伙，這不就是需要我將平鋪數組轉成樹(shù)形結構嘛！
一頓操作猛如虎，二話(huà)不說(shuō)寫(xiě)遞歸。

遞歸方式

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

非遞歸方式

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

總結

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

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

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

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

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