web前端怎么將扁平數據結構轉Tree

這篇文章主要介紹“web前端怎么將扁平數據結構轉Tree”，在日常操作中，相信很多人在web前端怎么將扁平數據結構轉Tree問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”web前端怎么將扁平數據結構轉Tree”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

我們看下題目：打平的數據內容如下：

let arr = [
    {id: 1, name: '部門1', pid: 0},
    {id: 2, name: '部門2', pid: 1},
    {id: 3, name: '部門3', pid: 1},
    {id: 4, name: '部門4', pid: 3},
    {id: 5, name: '部門5', pid: 4},
]

輸出結果

[
    {
        "id": 1,
        "name": "部門1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "部門2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "部門3",
                "pid": 1,
                "children": [
                    // 結果 ,,,
                ]
            }
        ]
    }
]

我們的要求很簡單，可以先不用考慮性能問題。實現功能即可，回頭分析了面試的情況，結果使我大吃一驚。

10%的人沒思路，沒碰到過這種結構

60%的人說用過遞歸，有思路，給他個筆記本，但就是寫不出來

20%的人在引導下，磕磕絆絆能寫出來

剩下10%的人能寫出來，但性能不是最佳

感覺不是在招聘季節遇到一個合適的人真的很難。

接下來，我們用幾種方法來實現這個小算法

什么是好算法，什么是壞算法

判斷一個算法的好壞，一般從執行時間和占用空間來看,執行時間越短，占用的內存空間越小，那么它就是好的算法。對應的，我們常常用時間復雜度代表執行時間，空間復雜度代表占用的內存空間。

時間復雜度

時間復雜度的計算并不是計算程序具體運行的時間，而是算法執行語句的次數。

隨著n的不斷增大，時間復雜度不斷增大，算法花費時間越多。 常見的時間復雜度有

• 常數階O(1)

• 對數階O(log2 n)

• 線性階O(n)

• 線性對數階O(n log2 n)

• 平方階O(n^2)

• 立方階O(n^3)

• k次方階O(n^K)

• 指數階O(2^n)

計算方法

• 選取相對增長最高的項

• 最高項系數是都化為1

• 若是常數的話用O(1)表示

舉個例子：如f(n)=3*n^4+3n+300 則 O(n)=n^4

通常我們計算時間復雜度都是計算最壞情況。計算時間復雜度的要注意的幾個點

• 如果算法的執行時間不隨n的增加而增長，假如算法中有上千條語句，執行時間也不過是一個較大的常數。此類算法的時間復雜度是O(1)。 舉例如下：代碼執行100次，是一個常數，復雜度也是O(1)。

    let x = 1;
    while (x <100) {
     x++;
    }

• 有多個循環語句時候，算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的方法決定的。舉例如下：在下面for循環當中，外層循環每執行一次，內層循環要執行n次，執行次數是根據n所決定的，時間復雜度是O(n^2)。

  for (i = 0; i < n; i++){
         for (j = 0; j < n; j++) {
             // ...code
         }
     }

• 循環不僅與n有關，還與執行循環判斷條件有關。舉例如下：在代碼中，如果arr[i]不等于1的話，時間復雜度是O(n)。如果arr[i]等于1的話，循環不執行，時間復雜度是O(0)。

    for(var i = 0; i<n && arr[i] !=1; i++) {
    // ...code
    }

空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間的大小。

計算方法：

• 忽略常數，用O(1)表示

• 遞歸算法的空間復雜度=(遞歸深度n)*(每次遞歸所要的輔助空間)

計算空間復雜度的簡單幾點

僅僅只復制單個變量，空間復雜度為O(1)。舉例如下：空間復雜度為O(n) = O(1)。

   let a = 1;
   let b = 2;
   let c = 3;
   console.log('輸出a,b,c', a, b, c);

遞歸實現，調用fun函數，每次都創建1個變量k。調用n次，空間復雜度O(n*1) = O(n)。

    function fun(n) {
       let k = 10;
       if (n == k) {
           return n;
       } else {
           return fun(++n)
       }
    }

不考慮性能實現，遞歸遍歷查找

主要思路是提供一個遞getChildren的方法，該方法遞歸去查找子集。 就這樣，不用考慮性能，無腦去查，大多數人只知道遞歸，就是寫不出來。。。

/**
 * 遞歸查找，獲取children
 */
const getChildren = (data, result, pid) => {
  for (const item of data) {
    if (item.pid === pid) {
      const newItem = {...item, children: []};
      result.push(newItem);
      getChildren(data, newItem.children, item.id);
    }
  }
}
/**
* 轉換方法
*/
const arrayToTree = (data, pid) => {
  const result = [];
  getChildren(data, result, pid)
  return result;
}

從上面的代碼我們分析，該實現的時間復雜度為O(2^n)。

不用遞歸，也能搞定

主要思路是先把數據轉成Map去存儲，之后遍歷的同時借助對象的引用，直接從Map找對應的數據做存儲

function arrayToTree(items) {
  const result = [];   // 存放結果集
  const itemMap = {};  // 
  // 先轉成map存儲
  for (const item of items) {
    itemMap[item.id] = {...item, children: []}
  }
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

從上面的代碼我們分析，有兩次循環，該實現的時間復雜度為O(2n)，需要一個Map把數據存儲起來，空間復雜度O(n)

最優性能

主要思路也是先把數據轉成Map去存儲，之后遍歷的同時借助對象的引用，直接從Map找對應的數據做存儲。不同點在遍歷的時候即做Map存儲,有找對應關系。性能會更好。

function arrayToTree(items) {
  const result = [];   // 存放結果集
  const itemMap = {};  // 
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;
    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }
    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    }
    const treeItem =  itemMap[id];
    if (pid === 0) {
      result.push(treeItem);
    } else {
      if (!itemMap[pid]) {
        itemMap[pid] = {
          children: [],
        }
      }
      itemMap[pid].children.push(treeItem)
    }
  }
  return result;
}

從上面的代碼我們分析，一次循環就搞定了，該實現的時間復雜度為O(n)，需要一個Map把數據存儲起來，空間復雜度O(n)

小試牛刀

從我們的測試結果來看，隨著數量的增大，遞歸的實現會越來越慢，基本成指數的增長方式。

到此，關于“web前端怎么將扁平數據結構轉Tree”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！