js中的數(shù)組轉(zhuǎn)樹型結(jié)構(gòu)方式

更新時間：2023年06月07日 10:44:40 作者：酥脆角

這篇文章主要介紹了js中的數(shù)組轉(zhuǎn)樹型結(jié)構(gòu)方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

什么是數(shù)組轉(zhuǎn)樹型結(jié)構(gòu)

將數(shù)組中的元素按照特定規(guī)則組織成一個樹形結(jié)構(gòu)，專業(yè)術(shù)語是數(shù)組轉(zhuǎn)樹。

具體實(shí)現(xiàn)方式可能因情況而異，但通常需要考慮以下幾個要素：

數(shù)組中元素的順序和位置如何影響樹的結(jié)構(gòu)；
樹的節(jié)點(diǎn)應(yīng)包含哪些信息，例如值、子節(jié)點(diǎn)等；
如何確定每個節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)的索引或指針；
如何處理數(shù)組中缺失的節(jié)點(diǎn)或空值。
在實(shí)際應(yīng)用中，可能還需要考慮對樹進(jìn)行遍歷、搜索等操作的效率問題。

應(yīng)用場景: 比如前端開發(fā)中的菜單導(dǎo)航、商品分類等。

實(shí)現(xiàn)數(shù)組轉(zhuǎn)樹型結(jié)構(gòu)的一般思路是

遍歷數(shù)組，將每個元素轉(zhuǎn)換為樹節(jié)點(diǎn)對象（通常包含 id 和 parentId 等屬性）。
將所有節(jié)點(diǎn)按照 parentId 屬性進(jìn)行分組，形成一個以 parentId 為鍵、以對應(yīng)節(jié)點(diǎn)數(shù)組為值的字典。
找到根節(jié)點(diǎn)（即沒有父節(jié)點(diǎn)或其父節(jié)點(diǎn)不在數(shù)組中的節(jié)點(diǎn)），并遞歸構(gòu)建整個樹形結(jié)構(gòu)。

下面是一個基于 JavaScript 的示例代碼實(shí)現(xiàn)：

function arrayToTree(list, parentId = null) {
  const arr = []
  list.forEach(item => {
    if (item.pid === parentId) {
      // 找到了匹配的節(jié)點(diǎn)
      // 當(dāng)前節(jié)點(diǎn)的id 和 當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)的pid是相等的
      const children = transListToTreeData(list, item.id) 
      // 找到的節(jié)點(diǎn)的子節(jié)點(diǎn)
      item.children = children
      arr.push(item)
    }
  })
  return arr
}
// 使用示例
const array = [
  { id: 1, name: 'A', parentId: null },
  { id: 2, name: 'B', parentId: 1 },
  { id: 3, name: 'C', parentId: 1 },
  { id: 4, name: 'D', parentId: 2 },
  { id: 5, name: 'E', parentId: 2 },
  { id: 6, name: 'F', parentId: 3 },
  { id: 7, name: 'G', parentId: null }
];
const tree = arrayToTree(array, null);
console.log(tree);

在上述代碼中，arrayToTree 函數(shù)接收一個數(shù)組和可選的 parentId 參數(shù)，用于指定父節(jié)點(diǎn)的 id 值。

在函數(shù)內(nèi)部，首先判斷數(shù)組中的 id跟 parentId 是否相等,相等的就將對象添加到此對象的子數(shù)組中,在當(dāng)中定義的 arr 就是篩選出來的數(shù)組,再重新調(diào)用一下 arrayToTree 函數(shù)構(gòu)建子樹,最后返回包含當(dāng)前節(jié)點(diǎn)以及其子樹的對象。

示例代碼運(yùn)行結(jié)果如下：

[
  {
    "id": 1,
    "name": "A",
    "parentId": null,
    "children": [
      {
        "id": 2,
        "name": "B",
        "parentId": 1,
        "children": [
          {
            "id": 4,
            "name": "D",
            "parentId": 2,
            "children": []
          },
          {
            "id": 5,
            "name": "E",
            "parentId": 2,
            "children": []
          }
        ]
      },
      {
        "id": 3,
        "name": "C",
        "parentId": 1,
        "children": [
          {
            "id": 6,
            "name": "F",
            "parentId": 3,
            "children": []
          }
        ]
      }
    ]
  },
  {
    "id": 7,
    "name": "G",
    "parentId": null,
    "children": []
  }
]

注意：

數(shù)組轉(zhuǎn)樹型結(jié)構(gòu)是封裝一個函數(shù)來進(jìn)行對數(shù)據(jù)的篩選，將篩選出來的對象添加到父節(jié)點(diǎn)的子節(jié)點(diǎn)上，并且再調(diào)用一下此函數(shù)，形成遞歸，就可以實(shí)現(xiàn)數(shù)組轉(zhuǎn)樹，這樣在拿到平鋪數(shù)據(jù)時就可以得到嵌套數(shù)據(jù)了。

關(guān)于扁平數(shù)組轉(zhuǎn)樹型數(shù)組這件事

項(xiàng)目中很難避免扁平轉(zhuǎn)樹型或者樹型轉(zhuǎn)扁平這件事情，所以我們在查看到數(shù)據(jù)的時候，可以根據(jù)這個數(shù)據(jù)的規(guī)則來定義一個方法。這樣在數(shù)據(jù)規(guī)則相同的時候我們就可以調(diào)用這個方法。

準(zhǔn)備數(shù)據(jù)

const arr = [
        { id: 1, name: "萬科", pid: "" },
        { id: 11, name: "1棟", pid: 1 },
        { id: 111, name: "1單元", pid: 11 },
        { id: 12, name: "2棟", pid: 1 },
        { id: 2, name: "湯臣一品", pid: "" },
      ];

方法一：遞歸實(shí)現(xiàn)扁平數(shù)組轉(zhuǎn)換成樹型數(shù)組

封裝一個函數(shù)

function tranListToTreeData(list, rootValue) {
        const arr = [];
        list.forEach((item) => {
          if (item.pid === rootValue) {
            // 遞歸調(diào)用
            const children = tranListToTreeData(list, item.id);
            if (children.length) {
              item.children = children;
            }
            arr.push(item);
          }
        });
        return arr;
      }

調(diào)用這個函數(shù)將要匹配的規(guī)則穿進(jìn)去并打印出來

tranListToTreeData(arr, "");
   console.log(
     '[ tranListToTreeData(arr, ""); ] >',tranListToTreeData(arr, "")
);

你會發(fā)現(xiàn)你得到了一個樹型數(shù)組。

但是我們定義一個i，看一看這個函數(shù)總共運(yùn)行了多少次

var i = 0;
      function tranListToTreeData(list, rootValue) {
        const arr = [];
        list.forEach((item) => {
          if (item.pid === rootValue) {
            // 遞歸調(diào)用
            const children = tranListToTreeData(list, item.id);
            if (children.length) {
              item.children = children;
              // i++;
            }
            arr.push(item);
          }
          i++;
          console.log("[ i ] >", i);
        });
        return arr;
      }
      tranListToTreeData(arr, "");
      console.log(
        '[ tranListToTreeData(arr, ""); ] >',
        tranListToTreeData(arr, "")
      );

打印的結(jié)果最終為60次，因?yàn)檫f歸是函數(shù)嵌套函數(shù)，外面每循環(huán)一次，里面的函數(shù)都要循環(huán)一遍。我們現(xiàn)在數(shù)據(jù)還不多，要是數(shù)據(jù)多了的話是很耗性能的。下面我們來看一下對象的方法實(shí)現(xiàn)這個遞歸來優(yōu)化性能。

方法二：利用對象實(shí)現(xiàn)扁平數(shù)組轉(zhuǎn)換成樹型數(shù)組

還是那個數(shù)據(jù)

const arr = [
        { id: 1, name: "萬科", pid: "" },
        { id: 11, name: "1棟", pid: 1 },
        { id: 111, name: "1單元", pid: 11 },
        { id: 12, name: "2棟", pid: 1 },
        { id: 2, name: "湯臣一品", pid: "" },
 ];

// 1.得到一個對象
      function tranListToTreeData(list, pid) {
        var map = {};
        list.forEach((item) => {
          if (map[item.pid]) {
            map[item.pid].push(item);
          } else {
            map[item.pid] = [item];
          }
        });
        return map;
      }
      const result = tranListToTreeData(arr, "");
      console.log(result);

遍歷數(shù)據(jù)的每一項(xiàng)，有pid的話就追加到map中，沒有的話就將這條數(shù)據(jù)賦值給map對象的每一項(xiàng)的pid，最后我們就會得到如下這個對象，你會發(fā)現(xiàn)，pid相同的數(shù)據(jù)在同一個數(shù)組中。

利用第一步得到的對象對原數(shù)組進(jìn)行修改

list.forEach((item) => {
          if (map[item.pid]) {
            item.children = map[item.id];
          }
 });

看圖你會發(fā)現(xiàn)，剛剛得到的數(shù)組中都有子節(jié)點(diǎn)了

最后主需要過濾掉不需要的數(shù)組就行了

map = list.filter((item) => item.pid == pid);

現(xiàn)在可以測試一下我們這個方法需要循環(huán)多少次。

// 把扁平數(shù)組轉(zhuǎn)成樹型數(shù)組
      // 1.得到一個對象
      var i = 0;
      function tranListToTreeData(list, pid) {
        var map = {};
        list.forEach((item) => {
          if (map[item.pid]) {
            map[item.pid].push(item);
          } else {
            map[item.pid] = [item];
          }
          i++;
        });
        //2. 利用第一步得到的對象對原數(shù)組list進(jìn)行修改
        list.forEach((item) => {
          if (map[item.pid]) {
            item.children = map[item.id];
            // console.log(
            //   "[JSON.stringify( map[item.id]) ] >",
            //   JSON.stringify(map[item.id])
            // );
          }
          i++;
        });
        // 3.過濾
        map = list.filter((item) => {
          i++;
          return item.pid == pid;
        });
        console.log("[ i ] >", i);
        return map;
      }
      const result = tranListToTreeData(arr, "");
      console.log(result);```
最后我們可以看到只執(zhí)行了15次，這對性能來說，省了四分之三