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

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

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

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

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

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

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

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

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

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

下面是一個(gè)基于 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ù)接收一個(gè)數(shù)組和可選的 parentId 參數(shù)，用于指定父節(jié)點(diǎn)的 id 值。

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

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

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

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

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

const arr = [
        { id: 1, name: "萬(wàn)科", 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ù)組

封裝一個(gè)函數(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)用這個(gè)函數(shù)將要匹配的規(guī)則穿進(jìn)去并打印出來(lái)

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

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

但是我們定義一個(gè)i，看一看這個(gè)函數(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ù)多了的話是很耗性能的。下面我們來(lái)看一下對(duì)象的方法實(shí)現(xiàn)這個(gè)遞歸來(lái)優(yōu)化性能。

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

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

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

// 1.得到一個(gè)對(duì)象
      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中，沒(méi)有的話就將這條數(shù)據(jù)賦值給map對(duì)象的每一項(xiàng)的pid，最后我們就會(huì)得到如下這個(gè)對(duì)象，你會(huì)發(fā)現(xiàn)，pid相同的數(shù)據(jù)在同一個(gè)數(shù)組中。

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

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

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

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

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

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

// 把扁平數(shù)組轉(zhuǎn)成樹(shù)型數(shù)組
      // 1.得到一個(gè)對(duì)象
      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. 利用第一步得到的對(duì)象對(duì)原數(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.過(guò)濾
        map = list.filter((item) => {
          i++;
          return item.pid == pid;
        });
        console.log("[ i ] >", i);
        return map;
      }
      const result = tranListToTreeData(arr, "");
      console.log(result);```
最后我們可以看到只執(zhí)行了15次，這對(duì)性能來(lái)說(shuō)，省了四分之三