JavaScript平鋪數組轉樹形結構的實現示例

更新時間：2021年07月30日 09:58:07 作者：MikiMiki

本文主要介紹了JavaScript平鋪數組轉樹形結構的實現示例，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

后臺丟來了1w條數據

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

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' },
]

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

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

好家伙，這不就是需要我將平鋪數組轉成樹形結構嘛！
一頓操作猛如虎，二話不說寫遞歸。

遞歸方式

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

非遞歸方式

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

總結

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

我們來看一個對比圖：